けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 122 B - ATCoder (200 点)

E8君問題集第3問!

問題へのリンク

問題概要

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

制約

  •  1 \le N \le 10

考えたこと

 N が小さいので、全部調べても間に合う。連続する部分列は  N(N+1)/2 個ある。

それぞれについて、調べるのに  O(N) かかるので、全部で  O(N^{3}) となる。

#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" 以外の文字が最初に出てくるところまでの長さを求める

という風にする。こうすると  O(N^{2}) に改良される。

#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;
}

さらに工夫!!!

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

AAABBBBBBCAABCCC

といった文字列を、

A3B6C1A2B1C3

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

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

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

計算量は  O(N)

#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;
}