考察
一文字の反転は、その文字の左右にある境界を同時に変える。そこで隣の文字と異なるかどうかを表す差分列へ移す。さらに、最終的に反転する文字を連続区間にまとめると、変わる差分は各区間の両端だけになる。この対応から、嬉しさを増やす最小費用を「隣り合う 0 を、同じ 0 を使わずに組にする問題」へ帰着する。
固定端を足して RS の個数を差分へ移す
元の長さを とし、文字列の前に固定した S、後ろに固定した R を一文字ずつ足す。付加後の文字を と書き、変更できるのは元の文字に当たる だけとする。
から へ進むので、S→R の遷移は R→S より一つ多い。付加した両端には RS が生じないため、元の嬉しさを 、異なる文字が隣り合う箇所の総数を とすると、
となる。この関係は操作後も成り立つ。したがって、嬉しさを 1 増やすことは、異なる文字の境界を 2 個増やすことに等しい。
境界番号を 0 始まりとして、 に対して差分 を定める。 なら 0、異なれば 1 とする。文字 の反転で変わるのは の二つだけで、どちらも反転する。例えば元の文字列が SS なら、固定端込みの SSSR の差分は 001 である。元の一文字目を反転すると SRSR、差分は 111 となり、最初の二つの差分だけが 00→11 と変わる。
操作順よりも、最後に反転した文字集合を見る
全ての反転集合を試すと 通りあり、 には間に合わない。一方、同じ文字を二回反転すれば元に戻るので、最小費用を考える際は各文字を高々一回だけ反転すればよい。
反転する文字が連続区間 をなすとき、内部の差分は二回ずつ反転されて元に戻る。残る変化は の反転だけで、費用は区間長 である。差分の両端を と書けば、費用は距離 になる。
初期状態で両端が 00 の区間なら 1 の数が 2 増え、嬉しさが 1 増える。増やさない区間を除き、残った区間を内部の隣接する 0 二つまで縮められることを「正当性」で示す。このため、探すべきものは元の差分列で隣り合う 0 の組だけとなる。
隣り合う 0 の距離を辺の重みにする
初期差分の 0 の個数を とし、その位置を昇順に と置き、隣接距離を
とする。組 を選ぶ費用は 。隣接する二要素 は同じ 0 の位置 を使うため、同時には選べない。それ以外の組どうしは競合しない。各 0 を頂点、隣接する 0 の組を辺としたパス上で、端点を共有しない辺集合、すなわちマッチングを選ぶ問題になった。
嬉しさを初期値から少なくとも 増やす最小反転回数を とする。これは から隣接しない 要素を選ぶ最小和に等しい。 であり、選べる組の最大数は である。
この全ての個数に対する最小費用は、主単元の縮約証明を使って求める。現在の最小重みの辺を取り出し、その重みを累積費用へ加える。左右に辺があるなら、左・中央・右の三辺を取り除いて、
という重みの補正辺に置き換える。端なら、選んだ辺と存在する隣辺だけを取り除く。現在の最小辺を min-heap、現在の隣接関係を双方向リンクで管理し、 回目までの累積費用を として記録する。補正辺は以前の選択を左右二辺へ置き換える余地を表すので、最初に選んだ組を永久に固定するわけではない。
最小費用の列から、予算ごとの回答へ戻す
は必要な嬉しさを固定したときの最小費用である。問題が求めるのは予算 ごとの最大値なので、
へ変換する。 で始め、 を 0 から順に増やし、 かつ の間だけポインタ を進めれば、全予算の回答を追加 時間で得られる。
例えば元の文字列が SR なら、固定端込みでは SSRR、差分は 010、0 の位置は 0 と 2 である。初期嬉しさは 、最小費用の列は だが、予算 に対する出力は となる。最小費用の列をそのまま出力しないことに注意する。
典型の発動条件
文字flipの境界差分化
隣接文字の一致・不一致や遷移数を最適化したいとき、文字そのものから境界へ視点を移す。一文字の操作は隣接二差分、連続区間の反転は区間両端の差分だけを変える。端の扱いを固定すれば、目的量と差分の個数の関係も揃えやすい。
path matchingのcontraction貪欲
列から隣接しない所定個数の要素を最小和で選ぶとき、パスの辺を選ぶマッチングへ移せる。最小辺の選択後に両隣との補正縮約を行えば、各選択個数の最適値を順に得られる。単に軽い辺を順に確定して隣辺を消すだけでは、後の個数に対する最適解を失う。
問題固有の要素
嬉しさが数えるのは RS だけだが、固定した S と R を両端へ足すと、全ての異符号境界の個数から嬉しさを復元できる。この変換で左右の向きの違いを吸収してから、0 の組を消す問題へ進む。
もう一つの着目点は、操作回数が「高々」であること。増加に役立たない反転区間を除いてよいため、予算以下で目標を達成する操作を、同じ増加量の隣接 0 の組へ正規化できる。
正当性
まず、同じ文字への反転は偶奇だけが最終状態を決め、操作順にも依存しない。したがって、任意の操作列を「最終的に奇数回反転された文字だけを一回ずつ反転する」形へ、回数を増やさずに直せる。
その文字集合を極大な連続区間に分ける。一つの区間 は、初期差分の だけを反転する。別の区間との間には未反転の文字が少なくとも一つあるので、区間どうしは差分の端点を共有しない。従って、それぞれの区間による 1 の個数の増減を独立に足せる。
高々 回で嬉しさを少なくとも 増やす操作を考える。00 以外の区間を丸ごと除けば、費用は減り、最終的な嬉しさは減らない。残った 00 の区間数は少なくとも なので、必要ならそこから 区間だけを残せる。これで費用を増やさず、嬉しさをちょうど 増やす操作を得る。 なら全区間を除けばよい。
次に、残った一つの区間の差分端点を とする。両端は初期状態で 0 なので、閉区間 には少なくとも二つの 0 がある。その中で隣り合う二つを と選び、反転する文字区間を へ縮める。この区間は元の に含まれ、費用は 。新たな両端も 00 なので、嬉しさの増加は 1 のままである。
この縮小を各区間で独立に行っても、元から分離していた区間が重なったり、同じ 0 を使ったりすることはない。従って、任意の目標達成操作から、費用が元以下の 組の隣接 0 を得られる。「組が交差しない」と言うだけでなく、各区間の内側へ縮めることで、途中に未使用の 0 を挟む組も不要だと分かる。
逆に、 の隣接しない 要素を選んだとする。各辺 に対し、文字 を一回ずつ反転する。端点を共有しない辺に対応する文字区間は互いに分離しており、各区間が独立に 1 の個数を 2 増やす。さらに なので、反転範囲は必ず に収まり、固定した を変更しない。よって辺の重みの総和回で嬉しさをちょうど 増やせる。
以上の両方向の対応から、嬉しさを少なくとも 増やす最小費用 は、パス上の 辺マッチングの最小重みに等しい。公式解説は操作を左から順に並べ、11→00 を行う操作を省けることから 0 の組への帰着を示す。ここでは、同じ操作の可換性を使い、最終反転集合の連続区間から、隣接する 0 に限定できることと固定端での合法性まで示した。
マッチング以降は主単元の費用保存対応を用いる。パス の 辺マッチングの最小重みを と書く。最小辺を 、その重みを 、縮約後のパスを とすると、実行可能な辺数 について、
が成立する。従って、縮約時に取り出す重みを累積すれば全ての が得られる。元の距離は正であり、最小辺を用いる補正重みも正なので、 は狭義に増加する。最後に を満たす最大の を選ぶことで、予算内で達成できる最大の増加量を選べる。初期嬉しさ を加えた が求める答えである。
実装上の注意
- 固定端の文字は反転できないが、差分の位置 0 と は通常の候補に含める。例えば端点 0 の組なら、文字 1 から始まる合法な反転区間になる。
- なら辺はなく、。全ての予算に初期嬉しさを出す。全交互の文字列でも、それ以上増やせるとは限らない。
- heap には現在の重みと辺 ID を入れる。削除した辺の要素が後から取り出されたら捨てる(stale entry)。内部縮約で新しい辺 ID を発行し、元の三辺を無効化すれば、同じ ID の重み更新と古い要素を混同しない。ID を再利用するなら版番号等で現在の要素かどうかも判定する。
- 左右の隣辺は、元の配列の添字ではなく、現在生きている辺の双方向リンクから取得する。両隣がある場合だけ三辺を補正辺へ置き換え、外側のリンクをつなぎ直す。端の辺ならその辺と存在する隣辺を削除するだけで、補正辺は作らない。リンク用番兵を重み 0 の実辺として扱わない。
- 縮約は 回まで。予算への変換では を確かめてから次の費用を参照し、 でも配列の外へ進めない。操作は高々 回なので、余った予算を使い切る必要はない。
復習の核
操作の途中を追うのが難しいときは、同じ場所への操作が打ち消せるかを調べ、最終的に変更する集合を見る。本問では、その集合の連続区間が「差分の両端だけを変える操作」になり、増やさない区間の除去と区間の縮小から、隣接 0 のマッチングまで導ける。
縮約貪欲では、最小辺を永久に固定するのではなく、両隣へ置き換える費用を補正辺に残す。三辺の重みが なら、最小費用は一辺で 1、二辺で となることを再現し、最後に費用の列を予算ごとの最大値へ戻す。
計算量と制約
時間
一テストケースの文字列長を とする。差分と距離列の構築は 。辺の初期数と縮約回数 はともに で、各回の辺の追加・削除は定数個である。古い heap 要素も各要素につき一回しか取り出さないため、縮約全体は 。予算への変換と 個の出力を含めても である。
空間
差分、0 の位置、辺の重み・生存情報・双方向リンク、heap、最小費用列と回答に 。新しい辺 ID を使っても、追加される辺は縮約一回につき高々一本なので に収まる。
制約との対応
公式制約は 、、一入力内の の総和が 以下。文字列は S と R だけからなる。各ケースを順に処理すれば、全体の時間は 、空間は最大のケースの長さに対して線形である。時間制限は 3 秒、メモリ制限は 1024 MiB。
出典