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

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

AtCoder ARC 110 B - Many 110 (茶色, 400 点)

本番 14 分かけたのは反省。

問題概要

"110" という文字列を 10000000000 個連結してできる文字列を  S とする。

長さ  N の文字列  T が与えられる。 S の中に  T が連続する部分文字列としていくつ含まれるかを求めよ。

制約

  •  1 \le N \le 2 \times 10^{5}

考えたこと

こういう、端の処理が慎重を要するタイプの問題、実はめっちゃ苦手なのです...

とりあえず  V = 10000000000 とする。 T は左右両端の端の部分を除くと "110" の繰り返しになっていなければならない。僕は両端から削る方針でやった。

まずは次の処理をする。

  • T = "1" は例外的、答えは  2V となる
  • T = "0", "11" の場合は、答えは  V となる
  • T の最初の 1 文字が "0" の場合は、それを除去して、 S からも最初の "110" を除去する ( V をデクリメントする)。
  • T の最初の 2 文字が "10" の場合は、それを除去して、 S からも最初の "110" を除去する ( V をデクリメントする)。

そうすると、 T は "110110...110" という形になるはず ( = "", "1", "11")。ならなければ答えは 0。そして末尾の * が空文字でないならば、それを除去して、 S からも最後の "110" を除去する ( V をデクリメントする)。

この段階で  T の "110" の繰り返し数を  a としたとき、答えは  V-a+1 となる ( a = 1 のとき  V 個になることを想像するとわかりやすい)。

計算量は  O(N)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string T;
    cin >> N >> T;
    auto solve = [&]() -> long long {
        long long V = 10000000000LL;
        if (T == "0") return V;
        else if (T == "1") return V * 2;

        if (T.size() >= 1 && T.substr(0, 1) == "0") T = T.substr(1), --V;
        else if (T.size() >= 2 && T.substr(0, 2) == "10") T = T.substr(2), --V;
        if (T.size() % 3 == 1) {
            if (T.substr(T.size()-1) != "1") return 0;
            T = T.substr(0, T.size()-1);
            --V;
        }
        else if (T.size() % 3 == 2) {
            if (T.substr(T.size()-2) != "11") return 0;
            T = T.substr(0, T.size()-2);
            --V;
        }
        for (int i = 0; i < T.size(); i += 3) if (T.substr(i, 3) != "110") return 0;
        return V - T.size()/3 + 1;
    };
    cout << solve() << endl;
}

別解:開始位置を全探索

もう少し明快なロジックがありそう。 S は周期 3 なので、 S における  T の開始位置を 3 通り全探索してしまうという考え方もできる。if 文で書くより for 文を回して探索できるなら、そっちの方がいい。

 S の 0 文字目、1 文字目、2 文字目からマッチングさせていって、もしマッチするならば、 S 中の費やした "110" のブロック数を  a とすると、

result += V - a + 1;

というように、答えに加算していけばよい。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S = "110", T;
    cin >> N >> T;
    auto solve = [&]() -> long long {
        long long V = 10000000000LL;
        if (T == "0") return V;
        else if (T == "1") return V * 2;

        long long res = 0;
        for (int i = 0; i < 3; ++i) {
            long long a = (T.size() + i + 2) / 3;
            long long add = V - a + 1;

            bool ok = true;
            for (int j = 0; j < T.size(); ++j) {
                if (T[j] != S[(j+i)%3]) ok = false;
            }
            if (ok) res += add;
        }
        return res;
    };
    cout << solve() << endl;
}