F - ARC Stamp Editorial
by 
square1001
いよいよ最終問題「ARC Stamp」の解説です。みなさん、コンテストは楽しめましたでしょうか？
解説の目次
最初の 1 節では、本問題だけでなく競技プログラミングの多くの問題で使われる「後ろから考える」テクニックについて紹介します。
次に 2 節では、本問題「ARC Stamp」を解く鍵となる「文字列 \(T\) の分解」のアイデアを導きます。
そして 3 節では、動的計画法 (DP) を使った解法を紹介します。
4 節には「解法のまとめ」を書きました。その後の 5 節に、本問題の解答例 (C++) を載せています。なお、急いで解説を読みたい人は、4 節「解法のまとめ」を読んでください。
1. 「後ろから考える」テクニック
競技プログラミングでよく使われる考察テクニックの 1 つとして「後ろから考える」が挙げられます。これは、どんなものなのでしょうか？まず、次の問題を考えてみましょう。
最初、整数 $x$ が $0$ にセットされています。次のいずれかの操作を $120$ 回以内行って、$x = N$ にしてください。ただし、$1 \leq N \leq 10^{18}$ とします。 （出典：AtCoder Beginner Contest 216 C - Many Balls）
- 操作 A：$x$ を $x+1$ に変える
- 操作 B：$x$ を $2x$ に変える
この問題は、操作を前から考えるのではなく、後ろから考えて「\(N\) から始めて \(0\) にする」という逆操作を見てみると、問題は次のようになります。
最初 $x = N$ です。次のいずれかの操作を $120$ 回以内行って、$x = 0$ にしてください。
- 操作 A：$x$ を $x-1$ に変える
- 操作 B：$x$ が偶数のとき、$x/2$ に変える
見通しが立ちやすくなりましたね。少ない操作回数でやりたいので、\(x\) が偶数のとき操作 B を行い、\(x\) が奇数のときに操作 A を行うことにしましょう。すると、\(120\) 手以内で \(x = 0\) になります。最後に操作の順番を逆転させれば、これが答えになります。
では、別の問題を見てみましょう。
長さ \(N\) の文字列 \(S\) があり、最初 \(S\) =
***...**です。以下の操作を繰り返して、文字列 \(S\) を文字列 \(T\)（すべてA,R,C）に一致させられるか判定してください。操作 \(S\) の連続する 3 文字を選び、これを
ARCに書き換える。
この問題も「後ろから考える」テクニックで解くことができます。
ある場所を ARC に書き換えるという操作の逆は「元々 ARC が書かれていた場所を何でもいい 3 文字に書き換える」操作になります。なので、「何でもいい文字」を ? で表して後ろから考えると、問題は次のようになります。
長さ \(N\) の文字列 \(T\) が与えられます。次の操作を何回か行って、\(T\) を
???...??の形にできるか判定してください。操作 \(T\) の連続する \(3\) 文字が
ARC,AR?,A?C,?RC,A??,?R?,??C,???のいずれかのものを選び、これを???に書き換える。
操作を行うことによって「今までできた操作ができなくなる」ことはなく、可能な操作がどんどん開放されていく感じになります。なので、この操作ができなくなるまで繰り返して ???...?? の形にできれば答えは Yes、A, R, C がどこかで残れば答えは No になります。
このように、操作を後ろから考えることで解法の見通しが一気に立ちやすくなることがあります。2 つ目に紹介した問題は、今回の問題設定とかなり似ていることに気づきましたでしょうか？
2-1. 文字列 \(T\) が作れるのは、どんな文字列 \(S\) から？
まずは、具体的な例を考えてみましょう。例えば、\(T\) = ARARCCC は、1 回の操作、2 回の操作、3 回の操作をもってどのような文字列 \(S\) から作れるか考えてみましょう。
先ほど 1 節で述べた例のように、後ろから考えると分かりやすいです。
1 回操作の場合
文字列 ARARCCC になる直前の操作として、「\(3, 4, 5\) 文字目を ARC に変えること」だけが可能です。
これは、直前の文字列が AR???CC（? は A, R, C のどれでもよいことを表す）ならできます。
2 回操作の場合
AR???CC になる直前の操作として、次の 3 通りが可能です。
- \(1, 2, 3\) 文字目を
ARCに変える。直前の文字列が?????CCならできる。 - \(3, 4, 5\) 文字目を
ARCに変える。直前の文字列がAR???CCならできる。 - \(4, 5, 6\) 文字目を
ARCに変える。直前の文字列がAR????Cならできる。
だから、2 回の操作をもって文字列 \(T\) を作れるのは、\(S\) が ?????CC または AR????C の形のときです。
3 回操作の場合
先ほどと同様に考えると、3 回の操作ををもって文字列 \(T\) を作れるのは \(S\) が ??????C または AR????? の形のときです。
これを図で表すと、次のようになります。青色の区間は「ARC に書き換えた場所」を表しています。
このように、文字列 \(S\) は、文字列 \(T\) を ARC の場所を中心に ? で支配して作っていくイメージになります。
具体例をいくつか挙げてみます。
AR?????からARARCCCを作るのに 3 回の操作が必要なのは、ARARCCC→AR???CC→AR????C→AR?????と支配に 3 ステップかかるからです。????????からAARCRARCを作るのに 4 回の操作が必要なのは、AARCRARC→A???RARC→A???R???→????R???→????????と支配に 4 ステップかかるからです。
2-2. どのように “?” で支配していくか？
先ほど「文字列 \(S\) は、文字列 \(T\) を ARC の場所を中心に ? で支配して作っていくイメージになります」と書きましたが、具体的な支配がどのような仕組みになっているか整理してみましょう。
- 無から支配を作るためには、
ARC→???とするしかない。 - 支配を左に広げるためには、次の 2 通りの方法がある。
A??...??→???...??（左のAを支配する）AR??...??→????...??（左のARを支配する）
- 支配を右に広げるためには、次の 2 通りの方法がある。
??...??C→??...???（右のCを支配する）??...??RC→??...????（右のRCを支配する）
- 2 つの支配地を以下のようにつなげることもできる。
??...??R??...??→??...?????...??（真ん中のRを支配する）
この 6 種類の「支配拡大」がある理由は、??? に変えられるところは ARC, AR?, A?C, ?RC, A??, ?R?, ??C, ??? のいずれかであり、??? → ??? は意味がなく、A?C は絶対に現れることがないからです。
2-3. 文字列 \(T\) の分解
まず、先ほど扱った \(T\) = ARARCCC の場合を見てみましょう。このとき、
ARARCCC→AR???CC→?????CC→??????C→???????ARARCCC→AR???CC→AR????C→AR?????→???????
といったように、\(T\) を ? で支配していく順番は何通りもあります。
しかし、1 ステップで ? で支配する（文字列 \(T\) 上の）区間は定まっていて、文字列 \(T\) を [AR][ARC][C][C] と分解したときに、1 つの [] 内を一挙に支配するようになっています。先ほどの例では、次のようになります。
[AR][ARC][C][C]→[AR][???][C][C]→[??][???][C][C]→[??][???][?][C]→[??][???][?][?][AR][ARC][C][C]→[AR][???][C][C]→[AR][???][?][C]→[AR][???][?][?]→[??][???][?][?]
もう少し例を見てみましょう。
- \(T\) =
ARCRCCRARCの場合：[ARC][RC][C][R][ARC]と分解される - \(T\) =
RARCCRRARCの場合：[R][ARC][C][RR][ARC]と分解される（左のRと真ん中のRRは絶対に支配できないので、[X][ARC][C][X][ARC]と表すことにします） - \(T\) =
AARARCRARRACの場合：[A][AR][ARC][RARRAC]=[A][AR][ARC][X]と分解される - \(T\) =
ARCARCARCの場合：[ARC][ARC][ARC]と分解される（しかし、[ARC]同士の支配は干渉しないので、間に[X]を置いても結果は変わらないので、実装しやすいように[ARC][X][ARC][X][ARC]と表すことにします） - \(T\) =
CARCCAARCAの場合：[C][ARC][C][A][ARC][A]=[X][ARC][C][X][A][ARC][X]と分解される
実は、一般の文字列 \(T\) に対しても、1 ステップで拡大できる支配地を表現する「分解」が一意に定まるのです。この「分解」は、文字列 \(T\) からできる限り ? で支配していく操作の過程として、計算量 \(O(|T|)\) で求められます。
すると、1 ステップの支配は次のように単純化できます。
[ARC]を支配する- 支配地から左に
[A]または[AR]があれば、これを支配する - 支配地から右に
[C]または[RC]があれば、これを支配する [R]が支配地に囲まれていれば、これを支配する[X]は絶対に支配できない
したがって、次のような重要な性質が成り立ちます。ただし、分解で出てくる [ARC], [A], [AR], [C], [RC] または [X] のひとつひとつを「節」ということにします。
性質 支配するのにかかる最小の操作回数は、支配する節の数と同じである
つまり、「\(K\) 回以内の操作で作れる文字列 \(S\) を数える」という問題は、\(K\) 個以内の節を支配して作れる文字列を数えるものとして解くことができます。このアイデアが、3 節で述べる動的計画法 (DP) による解法 につながります。
3. 動的計画法 (DP) による解法
ステップ 2 で得た「文字列 \(T\) の分解」のアイデアをもとに、この問題の動的計画法 (DP) による解法を設計してみましょう。
文字列 \(T\) の「分解」を左から順に \(v_1, v_2, \dots, v_M\) とします（\(M\) は節の個数）。ただし、\(v_i\) は [ARC], [A], [AR], [C], [RC], [X] のいずれかです。
さて、「? で支配するかどうか」、そして支配する場合はもとの（\(S\) 中の）文字列を何にするか、を左の節から順に決めていくことを考えます。このとき、DP に必要な情報は次の 3 つの状態 \((pos, conq, flag)\) です。
- 現在どの節まで決めたか \(pos\)（\(v_1, v_2, \dots, v_{pos}\) まで決めたことを表す）
- 現在までに何個の節を支配したか \(conq\)
- 節 \(pos, pos+1\) を両方支配するかを表す真偽値 \(flag\)（両方支配するなら 1、片方でも支配しないなら 0）
3 つ目の変数 \(flag\) の設定の仕方は実装によりますが、本解説では実装を単純化するため「\(v_{pos}, v_{pos+1}\) を両方支配するかどうか」を記録することにします。
すると、状態 \((pos, conq, flag)\) から、節 \(v_{pos+1}\) の「もとの文字列」を決める際に、次のような規則で状態が遷移することが分かります。（少し複雑ですが、整理すれば分かります）
- \(v_{pos+1}\) =
[ARC]のとき- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq, 0)\)：\(1\) 通り（支配しない）
- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq+1, 1)\)：\(27\) 通り（節 \(v_{pos+1}\) から支配し、もとの 3 文字は好きなように設定可能）
- 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 0)\)：\(27\) 通り（節 \(v_{pos+1}\) まで支配し、もとの 3 文字は好きなように設定可能）
- 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 1)\)：\(27\) 通り（節 \(v_{pos+1}\) を支配し、もとの 3 文字は好きなように設定可能）
- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq+1, 0)\)：\(26\) 通り（節 \(v_{pos+1}\) だけ支配し、周りの節は支配しない。もとの 3 文字は
ARC以外なら好きなように設定可能）
- \(v_{pos+1}\) =
[A]のとき- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq, 0)\)：\(1\) 通り（支配しない）
- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq+1, 1)\)：\(2\) 通り（この節から支配する。
AからR,Cに変えれば操作が無駄にならない） - 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 1)\)：\(3\) 通り（節 \(v_{pos+1}\) を支配する。もとの 1 文字は好きなように設定可能）
- \(v_{pos+1}\) =
[AR]のとき- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq, 0)\)：\(1\) 通り（支配しない）
- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq+1, 1)\)：\(8\) 通り（この節から支配する。
ARからそれ以外に変えれば操作が無駄にならない） - 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 1)\)：\(9\) 通り（節 \(v_{pos+1}\) を支配する。もとの 2 文字は好きなように設定可能）
- \(v_{pos+1}\) =
[C]のとき- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq, 0)\)：\(1\) 通り（支配しない）
- 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 0)\)：\(2\) 通り（この節まで支配する。
CからA,Rに変えれば操作が無駄にならない） - 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 1)\)：\(3\) 通り（節 \(v_{pos+1}\) を支配する。もとの 1 文字は好きなように設定可能）
- \(v_{pos+1}\) =
[RC]のとき- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq, 0)\)：\(1\) 通り（支配しない）
- 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 0)\)：\(8\) 通り（この節まで支配する。
RCからそれ以外に変えれば操作が無駄にならない） - 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 1)\)：\(9\) 通り（節 \(v_{pos+1}\) を支配する。もとの 2 文字は好きなように設定可能）
- \(v_{pos+1}\) =
[R]のとき- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq, 0)\)：\(1\) 通り（支配しない）
- 状態 \((pos, conq, 1)\) → 状態 \((pos+1, conq+1, 1)\)：\(2\) 通り（節 \(v_{pos+1}\) を支配する。
RからA,Cに変えれば操作が無駄にならない）
- \(v_{pos+1}\) =
[X]のとき- 状態 \((pos, conq, 0)\) → 状態 \((pos+1, conq, 0)\)：\(1\) 通り（支配しない。それ以外の選択肢はない）
\(dp[pos][conq][flag]\) には、状態 \((pos, conq, flag)\) になるような文字列 \(S\)（の \(|v_1| + |v_2| + \cdots + |v_{pos}|\) 文字目まで）が何通りあるかを記録します。
初期状態として最初 \(dp[0][0][0] = 1\) にセットし、上の状態遷移にしたがって \(dp[pos][conq][flag]\) を順々に求めていきます。最終的には \(dp[M][conq][0]\) が「必要最小の操作回数が \(conq\) であるような文字列 \(S\) が何通りか」を表します。したがって、答えは \(dp[M][0][0] + dp[M][1][0] + \cdots + dp[M][K][0]\) となります。
この DP は、操作回数の無駄なく、過不足なく数え上げることができます。DP の状態数が \(O(MK)\) 通りあるので、全体計算量は \(O(MK)\) となります。
4. 解法のまとめ
簡潔にまとめると、この問題は次のような方針で解けます。
- 最後の操作から順に後ろから考えて、「文字列 \(T\) から始めて \(K\) 回以内の操作を行ったときに得られる文字列 \(S\) は何通りか」という問題を解く
- 例えば、\(T\) =
ARARCCCとき、文字列 \(S\) としてあり得るのは 1 回の操作のときAR???CC（\(27\) 通り）、2 回の操作のとき?????CCまたはAR????Cと表せるもの（\(297\) 通り） - このように、操作を行うごとに
?が支配する領域を拡大させていくことを考える
- 例えば、\(T\) =
[A or AR]...[A or AR][ARC][C or RC]...[C or RC]の形の文字列をサブセクションとすると、文字列 \(T\) は[操作で変えられない部分][サブセクション][R or 操作で変えられない部分][サブセクション][R or 操作で変えられない部分]...[サブセクション][操作で変えられない部分]という形で一意的に分解できる[]で囲まれたパーツを「節」ということにする。- 例えば \(T\) =
ARARCCCは[AR][ARC][C][C]と分解できる
- すると、1 回の操作 ＝ 1 つの節を支配すること、になる
- つまり、最小の操作回数 ＝ 支配する必要がある節の数、となる
- 文字列 \(T\) を節に「分解」した後、\(dp[pos][conq][flag]\) =（前から \(pos\) 個目の節まで決めて、その時点で \(conq\) 個の節を支配し、「節 \(pos, pos+1\) を両方
?で支配するか」の真偽値が \(flag\) のときの文字列 \(S\) が何通りか）を求めていく - この DP は計算量 \(O(|T| \cdot K)\) で求められる
よって、この問題は全体計算量 \(O(|T| \cdot K)\) で解けます。なお、\(K \geq |T|\) の場合に \(K = |T|\) とみなしても結果は同じなので、全体計算量 \(O(|T| \cdot \min(|T|, K))\) で解けます。
5. 実装例 (C++)
この問題の C++ による実装例は次の通りです：
posted:
last update: