[AtCoder] 第二回全国統一プログラミング王決定戦本戦 B – NIKKEI String
問題
方針
\( n = |S| \) とします。\( S_3 , \ S_4 \) を固定して考えます。\( S \) の \( i \) 文字目から \( j \) 文字目までの部分文字列を \( S(i, j) \) \( (0 \leq i \leq j \leq n – 1)\)とします。このとき、
\begin{eqnarray}
S_3 &=& S(i, j)\\
S_4 &=& S(i + j + 1, i + 2j + 1)
\end{eqnarray}
と表現できます。また、制約は、\( 1 \leq i \leq n – 4 \wedge 0 \leq i + 2j +1\leq n – 3 \) です。次に、\( S_2, \ S_6 \) について探索を行います。これは、\( S_2, \ S_6 \) の末尾から先頭に向かって走査していくことで実現可能です。尺取り法のように文字列を伸ばしていく感じだと思います。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { string S; cin >> S; int n = S.length(); int ans = 0; for (int i = 2; i < n - 3; i++) { for (int j = 0; i + 2 * j + 1 <= n - 3; j++) { // s3(i, i+j), s4(i+j+1, i+2j+1) string s3 = S.substr(i, j + 1); string s4 = S.substr(i + j + 1, j + 1); if (s3 != s4) continue; for (int k = 0; k < n; k++) { if (i - 1 - k <= 0) break; if (n - k - 1 <= i + 2 * j + 2) break; if (S[i - 1 - k] != S[n - k - 1]) break; ans++; } } } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません