AtCoder ABC 122 B - ATCoder (灰色, 200 点)

E8君問題集第3問！

問題へのリンク

問題概要

長さ の文字列 が与えられる。 の連続する部分列であって、'A', 'C', 'G', 'T' のみからなる部分の長さの最大値を求めよ。

制約

• 

考えたこと

が小さいので、全部調べても間に合う。連続する部分列は 個ある。

それぞれについて、調べるのに かかるので、全部で となる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    string S;
    cin >> S;
    int res = 0;
    for (int i = 0; i < S.size(); ++i) {
        for (int j = i+1; j <= S.size(); ++j) {
            bool ok = true;
            for (int k = i; k < j; ++k) {
                if (S[k] != 'A' && S[k] != 'G' && S[k] != 'C' && S[k] != 'T')
                    ok = false;
            }
            if (ok) chmax(res, j-i);
        }
    }
    cout << res << endl;
}

少しだけ工夫

先ほどのは

• 全区間について
• 区間の文字をなめていく

という方法だった。少し考えると区間の文字をなめる部分で、同じことを何度も繰り返す無駄がある。そこで、こういう風にしてみよう。

• 区間の左端を固定する
• そこから見ていって、"AGCT" 以外の文字が最初に出てくるところまでの長さを求める

という風にする。こうすると に改良される。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    string S;
    cin >> S;
    int res = 0;
    for (int i = 0; i < S.size(); ++i) {
        int j;
        for (j = i; j < S.size(); ++j) {
            if (S[j] != 'A' && S[j] != 'G' && S[j] != 'T' && S[j] != 'C')
                break;
        }
        chmax(res, j - i);
    }
    cout << res << endl;
}

さらに工夫！！！

さらにもう一工夫して、 にすることもできる。ランレングス圧縮に近いことをすればよい。ランレングス圧縮とは

AAABBBBBBCAABCCC

といった文字列を、

A3B6C1A2B1C3

といったように、「連続する同じ文字」を圧縮して表現する方法のことだ。今回は

• A, G, C, T を同一視
• それ以外を同一視

する感じでランレングス圧縮する。そして、A, G, C, T の部分の長さの最大値を答えれば OK。ランレングス圧縮は簡単にできる。C 問題ではめちゃくちゃよく出てくる。

計算量は 。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

bool isAGCT(char c) {
    return (c == 'A' || c == 'G' || c == 'C' || c == 'T');
}

int main() {
    string S;
    cin >> S;
    int res = 0;
    for (int i = 0; i < S.size();) {
        int j = i;
        while (j < S.size() && isAGCT(S[i]) == isAGCT(S[j])) ++j;
        if (isAGCT(S[i])) chmax(res, j - i);
        i = j;
    }
    cout << res << endl;
}