[AtCoder] ARC 110 B – Many 110
問題
方針
\( 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; }
ディスカッション
コメント一覧
はじめまして. TsubaMukkuと申します.
丁寧な解説をありがとうございます.
差し支えなければ, ぜひ一点質問させていただきたい点がございます.
解説文の最後の箇所にもありますが, (a – N) / 3 + 1が答えになりますよね. (解説本文ではfloor functionを用いている.)
なぜ (a – N) / 3 + 1となるのか, という点が私にはどうしてもわかりませんでした.
この点をもう少し解説いただけると幸いです.
コメントありがとうございます。
一応追記にも書きましたが、ここで、S の部分文字列に T が初めて現れた箇所を、S の i から i + N までの部分文字列とします。次に現れるのは、i + 3, i + 3 + N の部分文字列となるので、
i + 3k + N <= n を満たすような k の最大値を考えた時に、(a - N) / 3 + 1 のような式が現れます。