ARC104 Bの解答

ARC 104 B問題 DNA Sequenceの解答を書きます。

問題はこちらから。

B - DNA Sequence

Difficulty：410 （茶色）

長さ n の 'A', 'T', 'C', 'G'で構成される文字列 t が与えられます。
s の連続する空でない部分文字列 t であり、t と相補的であるような、t を並び替えた文字列の個数を求めます。このとき、t が同一でも、s の開始位置が異なれば、異なる文字列とします。
また、長さの等しい t1, t2 が相補的とは t1, t2の i 文字目の組み合わせが('A'と'T')または（'C'と'G'）のいずれかであることを指します。

問題を簡単に言うとこんな感じです。

私は問題文の理解に時間がかかりました。結局のところ、なんか文字列があり、その文字列のa→t,c→g(逆も)に置き換わった文字列は、はじめの文字列の文字を入れ替えて作れますか？ということ。
そのため、入れ替えた文字列が作れる部分文字列 s の条件は

sに含まれる
a の数 = tの数
c の数 = gの数

となります。したがって、s に含まれる各文字の個数を数え上げて、条件を満たすものの数を求めていきます。

ただし、計算量の観点から

n <= 5000

なので、O(n^3)だと間に合いません（様々な方のコメントを見るにC++で実装の工夫次第では間に合う？、私は間に合いませんでした）。そのため、少し数え上げの高速化をしましょう。

私は累積和を用いて、元の文字列 t の i 番目までに登場する各文字の数を配列 va, vt, vc, vg に保存してきました。そうすれば、i 番目から j 番目までの文字列により作られた部分文字列 sij に含まれる各文字数は

sij に含まれる a の数 = va[j] - va[i-1]

でfor文を回すことなく求まります。実装において、i-1があるので、1インデックスから始め、va[0]には 0 を入れておくとシンプルに書けます。

実装です。

#include <bits/stdc++.h> 
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main()
{
	int n;
	string s;
	cin >> n >> s;
	int ls = s.length();
	vector<int> a(ls+1,0);
	vector<int> t(ls+1,0);
	vector<int> g(ls+1,0);
	vector<int> c(ls+1,0);
	int suma = 0;
	int sumt = 0;
	int sumc = 0;
	int sumg = 0;

	rep(i, ls) {
		char ch = s[i];
		if (ch == 'A') ++suma;
		else if (ch == 'T') ++sumt;
		else if (ch == 'C') ++sumc;
		else ++sumg;
		a[i + 1] = suma;
		t[i + 1] = sumt;
		c[i + 1] = sumc;
		g[i + 1] = sumg;
	}
	int ans = 0;
	for(int li = 1; li < ls+1;++li){
		for (int j = 1; j <= ls - li + 1; ++j) {
			int e = j + li - 1;
			if (a[e] - a[j - 1] != t[e] - t[j - 1]) continue;
			if (c[e] - c[j - 1] != g[e] - g[j - 1]) continue;
			++ans;
		}
	}
	cout << ans << endl;
	return 0;
}

上記の説明を、そのまま書いたような感じです。

「実際に必要なのは、累積和でなくaとt、cとgの差なので a が出たら +1, t が出たら -1 とする数を持っておけば、情報を減らすことができます。不必要な情報は削ったほうがいい」

ということを、公式の解説で言ってました。確かに。

あと、別の解法としてはdpでも、解けるそうですね。

余談ですが、a, t, c, gってDNAの塩基配列のことみたいですね。言われてみれば問題名が物語っていました。完全に専門外なので、理解が大変でした。医学生とか生物系の方はすんなりと問題文が読めるものなのでしょうか。