考察
新しいマスを塗るとき、調べるのは「そのマスを右端とする窓」に3色目が入るかどうかである。直前の色以外については、最後に現れた位置が分かれば、まだ窓に残っているかを判定できる。そこで色列全体を覚えず、もう一色の最終出現位置ごとに塗り方を数える。
マスを左から順に塗る。直前の マスの色列をそのまま状態にすると、候補だけで 個あり、 では扱えない。まず色名を入れ替えても合法かどうかは変わらないと気づきたい。ただし色名を捨てるだけでは、窓内の一致・不一致の並び方を大量に覚えることになる。次に「これから塗れる色を決めるには、過去の何が必要か」を考える。
既に確定した窓が合法なら、次のマスを塗って新しく確認する窓は一つだけである。そこに残る色が1色なら、同じ色と、それ以外の 色を選べる。2色なら、その2色のどちらかしか選べない。色が窓から消えたかどうかは最終出現位置で分かり、直前色の最終位置は必ず直前のマスなので、もう一色の位置だけを持てばよい。
塗り終えた時点の状態
位置は1始まりとする。マス まで塗った直後に見る窓を
とする。ここでは両端を含む。 の間は、塗り終えた部分全体を見る。この段階でも3色は許さない。最初の マスに必ず含まれるため、3色を使った塗り方は完成形へ延ばせないからである。
合法な塗り方を、 に現れる色によって次のように分ける。
sing: が単色である塗り方の個数。
- : が2色で、直前色とは異なる「もう一色」の最終出現位置が である塗り方の個数。有効な添字は 。
色名ごとに状態を分けないが、値は具体的な色名を区別した塗り方の個数である。例えば最初のマスには 通りあるので、位置1を塗った直後は 、配列 はすべて0とする。
塗る前に期限切れを移し、色を選ぶ
の順にマス を塗る。処理の最初は、マス まで塗った直後の状態である。次の二段階を区別する。
まず、新しい窓に残る既存部分へ範囲を絞る。 新しい窓 に入る既存部分は
であり、長さは高々 である。もう一色の最終位置が なら、その色は から消える。従って のときだけ
とする。この直後、sing は まだマス を塗っていない列について、 が単色である個数を表す。塗り終えた時点の の定義から、ここで意味が切り替わる。
例えば で ABB まで塗り、位置 に別の色 C を追加する場面を考える(A・B・C は互いに異なる色名)。塗る前の窓 ABB は2色で、A の最終位置は 。しかし新しい窓に残る既存部分は BB だけなので、この1通りは から sing に移る。そこから C を選ぶと ABBC となり、二つの窓 ABB・BBC はどちらも合法である。古い窓の2色をそのまま使って「3色目は禁止」とすると、この塗り方を落としてしまう。
次に、マス の色を選ぶ。 直前と異なる色を選ぶ遷移は、いずれも新しい へまとまる。
- が単色なら、直前色以外を 通りから選べる。旧直前色が「もう一色」になり、その最終位置は となる。
- が2色なら、もう一色を選ぶ1通りだけが直前と異なる色を使う遷移である。2色の役割が交換され、やはり旧直前色の最終位置 が新しい状態になる。
従って、期限切れを移した後の sing を使って
とする。下端が上端を超える和は0である。
残る選択肢は、直前と同じ色で塗る1通りである。この場合、sing に属する列は単色のまま、既存の に属する列はもう一色の最終位置が変わらない。既存の sing と有効範囲の をそのまま残すことが、この1通りの遷移に相当する。 リセットも2倍も不要である。新しい はそれまで未使用の添字なので、これらの継続分と衝突しない。
これでマス まで塗り終わり、状態は再び に対する定義へ戻る。sing は末尾の高々 マスが単色の個数であり、列全体が単色である必要はない。期限切れの の値は配列に残してよいが、有効範囲からは除外する。
区間和を定数時間で求める
上の和を毎回走査すると、全体で 時間かかる。各 は一度作った後、同色継続によって数値が変わらないので、作成済みの値の累積和を残せる。
マス を塗る段階では まで既知なので、遷移元の区間和は
となる。新しい を求めた後に を追加する。期限切れの値も累積和には残るが、差を取ると除かれる。
最後の位置 を塗った後は、単色状態と、まだ窓に残る2色状態を足す。
sing へ移した古い項を、再び答えへ足さないことが大切である。すべての加減乗算は法998244353で行う。
典型の発動条件
色名対称性による状態圧縮
制約が色の一致・不一致だけに依存するなら、色名そのものを状態から外せないか考える。状態をまとめた後も、具体的な色の選び方の数は残す。今回は直前色を続ける1通り、単色状態から異色を選ぶ 通りとして扱う。
last occurrence DP
窓内にある種類が残っているかどうかだけが必要なら、その種類の最終出現位置で判定できる。窓を進めるときは、次の要素を追加する前後のどちらの範囲を見ているかを定める。今回は追加前の末尾 マスへ範囲を絞り、期限切れを移してから色を選ぶ。
問題固有の要素
窓内の2色のうち一方は必ず直前のマスに現れる。その最終位置は時刻から決まるため、残る一色の最終位置だけを状態にすればよい。さらに、異色を塗るとどの状態からも同じ新しい添字 へ移るため、遷移元を一つの区間和にまとめられる。
別の問題でも、最終出現位置を複数持ちたくなったら、「現在の要素から自動的に決まる位置はどれか」「更新先が共通する遷移をまとめられるか」を調べる。
正当性
マス までの塗り方が状態の定義どおりに数えられているとする。マス に関わる過去の範囲は であり、直前の窓から外れる可能性がある最終出現位置は だけである。この状態を sing へ移すと、 が単色の場合と2色の場合に、過去の塗り方を漏れなく重複なく分けられる。
単色の場合には同色1通りと異色 通り、2色の場合には直前色1通りともう一色1通りが、許される色のすべてである。同色なら状態を保ち、異色なら旧直前色の最終位置 を持つ新状態へ移る。どちらの場合も、塗り終えた窓 の定義と一致する。色名をまとめても、各具体的な列からの選択肢数は同じなので、個数に必要な多重度は失われない。
生成される列は新しい窓の制約を満たし、既に確定した窓も変わらない。逆に、合法な列から末尾1マスを取り除くと遷移元と選んだ色が一意に決まるため、漏れも二重計数もない。 の間に3色を除くことも、それらを含む最初の長さ の窓が必ず不合法になるので正しい。初期値は1マスの全 通りを数えており、以上を繰り返すと全合法彩色が数えられる。最後に sing と に残る2色状態だけを合計すれば答えとなる。
実装上の注意
- 添字 のときは期限切れの移動を行わない。負添字を読まず、累積和の左側も で切り詰める。 を用意する場合は0のままにする。
- 更新は「期限切れを
sing へ加える → 新しい を計算する → を作る」の順に行う。旧 と sing を消すと、同色継続の分を失う。
- 法を取った累積和の差は負になることがあるので正規化する。 であり、
sing と の乗算には、剰余型または十分な整数幅を使う。
- ならどの2マスも高々2色なので、答えは 。遷移でも既存の2色状態は毎回すべて期限切れとなり、区間和は空になる。移動後の
sing が直前までの総数を表すため、同色1通りと異色 通りで毎回 倍になる。
- なら異色遷移はなく、常に
sing が1、 が0で答えも1となる。
- なら、調べる窓は列全体の一つだけである。期限切れの移動は起こらず、列全体で1色または2色を使う塗り方を数える。例えば では、全27通りから3色すべてを使う6通りを除いた21通りになる。
復習の核
- 窓の制約では「次を足す前に残る範囲」を書く。
ABB に C を足せるのは、新しい窓に残るのが BB だけだからである。
- 色名を捨てても、具体的な色の選択数は捨てない。単色からの異色は 通り、2色状態での切替は1通りである。
- 配列の値を残す操作にも遷移の意味がある。今回は同色継続が1通りだから値を保てる。期限切れの値を保持することと、その値を現在の状態や答えに含めることは区別する。
計算量と制約
時間
各マスで、期限切れの移動・累積和差分による遷移・累積和の追加を定数時間で行う。配列の初期化と答えの集計を含めて 時間。
空間
最終出現位置ごとの配列 と累積和 をそれぞれ 個保持するため、 空間。
制約との対応
、。窓の色列や色名を状態にせず、最終出現位置へ圧縮することで状態の総数を に抑える。遷移元も毎回走査せず累積和で集約し、 や に比例するループをなくす。
出典