[AtCoder] ARC 110 B – Many 110

2020年12月12日

問題

方針

\( N \geq 4 \) について考えます。\( S \) に \( T \) が含まれる場合、\( T \) は、

\[ T = \begin{cases}
110110110 \cdots \\
101101101 \cdots \\
011011011 \cdots
\end{cases}\]

のどれかである必要があります。これらは、\( 110, 101, 011\) のどれかの文字列を繰り返してできる文字列です。\( T \) が\( 101 \) の繰り返しからなる場合は、\( S \) の先頭の \( 1 \) を削り、\( S = 101101 \cdots \) とします、また、\( T \) が \( 011 \) の繰り返しからなる場合は、\( S \) の先頭の \( 11 \) を削り、\( S = 011011\cdots \) とします。\( T \) が \( 110 \) からなる場合は \( S \) はそのままとします。

ここで、\( S \) の文字列の長さを \( n \) とします。例えば、\( T \) が \( 110 \) からなる場合は、\( n = 3 \times 10^{10}\) です。\( T \) が \( S \) の部分文字列である場合、\( S \) の \( i \) から \( j \) までの部分文字列を \( S(i, j) \) とすると、

\[ T = S(3k + 1, 3k + N) \ (0 \leq k)\]

となるので、答えは

\[ \left \lfloor \dfrac{n – N}{3} \right \rfloor + 1\]

となります。

[追記]

ここで、\( T = S(3k + 1, 3k + N)\) を満たす最大の \( k \) を考えます。上記の議論から、\( k = 0 \) は満たします。

\begin{eqnarray}
3k + N &\leq& n\\
k &\leq&  \dfrac{n – N}{3}
\end{eqnarray}

となります。したがって、\( k \) の取りえる値は、

\[ k = 0, 1, \cdots , \left \lfloor \dfrac{n – N}{3} \right \rfloor\]

となります。

なぜ、\( T = S(3k + 1, k + N) \) を満たすのかを考えます。ここでは、\( T = S(1, N) \) となるような \( S \) に調整していることに注意します。\( S \) は \( 3 \) 文字の文字列の繰り返しで構成されているので、整数 \( t, k \) について、

\[ S(3k + 1, 3k + N) = S(3t + 1, 3t + N) \]

を満たします。これは、\( S \) の長さ \( N \) の部分文字列、\( S(i, i + N) \) と等しい部分文字列は、

\[ i \bmod 3 = j \bmod 3 \]

を満たす \( j \) について、\( S(i, i + N) = S(j, j + N) \) となっていることからも分かります。このことから、\( T = S(3k + 1, 3k + N)\) を満たす最大の \( k \) を求めます。

コード

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

int main() {
    int N;
    string T;
    cin >> N >> T;
    ll n = (ll)1e10;
    if (N <= 3) {
        if (N == 1) {
            if (T[0] == '1') {
                cout << 2 * n << "\n";
            } else {
                cout << n << "\n";
            }
        } else if (N == 2) {
            if (T == "11") {
                cout << n << "\n";
            } else if (T == "10") {
                cout << n << "\n";
            } else if (T == "01") {
                cout << n - 1 << "\n";
            } else {
                cout << "0\n";
            }
        } else {
            if (T == "110") {
                cout << n << "\n";
            } else if (T == "101") {
                cout << n - 1 << "\n";
            } else if (T == "011") {
                cout << n - 1 << "\n";
            } else {
                cout << "0\n";
            }
        }
        return 0;
    }
    string m[3] = {"110", "101", "011"};
    int idx = -1;
    for (int i = 0; i < 3; i++) {
        bool flag = true;
        for (int j = 0; j + 2 < N; j += 3) {
            if (m[i][0] != T[j] || m[i][1] != T[j + 1] || m[i][2] != T[j + 2]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            if (N % 3 == 1) {
                if (T[N - 1] == m[i][0]) {
                    idx = i;
                    break;
                }
            } else if (N % 3 == 2) {
                if (T[N - 2] == m[i][0] && T[N - 1] == m[i][1]) {
                    idx = i;
                    break;
                }
            } else {
                idx = i;
                break;
            }
        }
    }
    if (idx == -1) {
        cout << "0\n";
    } else {
        ll a = 3 * n - idx;
        cout << (a - N) / 3 + 1 << "\n";
    }

    return 0;
}