2021-03-08 AtCoderチャレンジ供養会場: AtCoder Grand Contest 052 A - Long Common Subsequence 競技プログラミング AtCoder コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 779 (記事作成時点) 供養 解法 0 を $N$ 個、1 を $N$ 個、0 を $1$ 個の順に並べた01列は任意の $S_{i} + S_{i}$ の部分文字列となる $N$ 個目の 0 の出現位置を $j$ とすると、$j + 1 \le k \lt + 2N$ の間に必ず $N$ 個の 1 がある 任意の連続した $2N$ 個の区間において 0 の数と 1 の数はそれぞれ $N$ である $j \le 2N$ より $k \lt j + 2N \le 4N$ なので、$j + 2N$ に 0 が存在する 実装 テストケースあたりの計算量は $O(N)$ 公式解説 躓いた点 01列の性質に気付かなかった
