ABC 464 G — Celester 2

考察

一文字の反転は、その文字の左右にある境界を同時に変える。そこで隣の文字と異なるかどうかを表す差分列へ移す。さらに、最終的に反転する文字を連続区間にまとめると、変わる差分は各区間の両端だけになる。この対応から、嬉しさを増やす最小費用を「隣り合う 0 を、同じ 0 を使わずに組にする問題」へ帰着する。

固定端を足して RS の個数を差分へ移す

元の長さを NN とし、文字列の前に固定した S、後ろに固定した R を一文字ずつ足す。付加後の文字を x0,x1,…,xN+1x_0,x_1,\ldots,x_{N+1} と書き、変更できるのは元の文字に当たる x1,…,xNx_1,\ldots,x_N だけとする。

x0=Sx_0=\texttt{S} から xN+1=Rx_{N+1}=\texttt{R} へ進むので、S→R の遷移は R→S より一つ多い。付加した両端には RS が生じないため、元の嬉しさを aa、異なる文字が隣り合う箇所の総数を bb とすると、

b=(a+1)+a=2a+1,a=b−12b=(a+1)+a=2a+1,\qquad a=\frac{b-1}{2}

となる。この関係は操作後も成り立つ。したがって、嬉しさを 1 増やすことは、異なる文字の境界を 2 個増やすことに等しい。

境界番号を 0 始まりとして、0≤i≤N0\le i\le N に対して差分 did_i を定める。xi=xi+1x_i=x_{i+1} なら 0、異なれば 1 とする。文字 xix_i の反転で変わるのは di−1,did_{i-1},d_i の二つだけで、どちらも反転する。例えば元の文字列が SS なら、固定端込みの SSSR の差分は 001 である。元の一文字目を反転すると SRSR、差分は 111 となり、最初の二つの差分だけが 00→11 と変わる。

操作順よりも、最後に反転した文字集合を見る

全ての反転集合を試すと 2N2^N 通りあり、N≤106N\le 10^6 には間に合わない。一方、同じ文字を二回反転すれば元に戻るので、最小費用を考える際は各文字を高々一回だけ反転すればよい。

反転する文字が連続区間 [l,r][l,r] をなすとき、内部の差分は二回ずつ反転されて元に戻る。残る変化は dl−1,drd_{l-1},d_r の反転だけで、費用は区間長 r−l+1r-l+1 である。差分の両端を p=l−1,q=rp=l-1,q=r と書けば、費用は距離 q−pq-p になる。

初期状態で両端が 00 の区間なら 1 の数が 2 増え、嬉しさが 1 増える。増やさない区間を除き、残った区間を内部の隣接する 0 二つまで縮められることを「正当性」で示す。このため、探すべきものは元の差分列で隣り合う 0 の組だけとなる。

隣り合う 0 の距離を辺の重みにする

初期差分の 0 の個数を mm とし、その位置を昇順に z0,z1,…,zm−1z_0,z_1,\ldots,z_{m-1} と置き、隣接距離を

Dj=zj+1−zj(0≤j<m−1)D_j=z_{j+1}-z_j\qquad(0\le j<m-1)

とする。組 (zj,zj+1)(z_j,z_{j+1}) を選ぶ費用は DjD_j。隣接する二要素 Dj,Dj+1D_j,D_{j+1} は同じ 0 の位置 zj+1z_{j+1} を使うため、同時には選べない。それ以外の組どうしは競合しない。各 0 を頂点、隣接する 0 の組を辺としたパス上で、端点を共有しない辺集合、すなわちマッチングを選ぶ問題になった。

嬉しさを初期値から少なくとも tt 増やす最小反転回数を ctc_t とする。これは DD から隣接しない tt 要素を選ぶ最小和に等しい。c0=0c_0=0 であり、選べる組の最大数は K=⌊m/2⌋K=\lfloor m/2\rfloor である。

この全ての個数に対する最小費用は、主単元の縮約証明を使って求める。現在の最小重みの辺を取り出し、その重みを累積費用へ加える。左右に辺があるなら、左・中央・右の三辺を取り除いて、

Dleft+Dright−DcenterD_{\mathrm{left}}+D_{\mathrm{right}}-D_{\mathrm{center}}

という重みの補正辺に置き換える。端なら、選んだ辺と存在する隣辺だけを取り除く。現在の最小辺を min-heap、現在の隣接関係を双方向リンクで管理し、t=1,…,Kt=1,\ldots,K 回目までの累積費用を ctc_t として記録する。補正辺は以前の選択を左右二辺へ置き換える余地を表すので、最初に選んだ組を永久に固定するわけではない。

最小費用の列から、予算ごとの回答へ戻す

ctc_t は必要な嬉しさを固定したときの最小費用である。問題が求めるのは予算 kk ごとの最大値なので、

ans⁡[k]=a+max⁡{t∣0≤t≤K, ct≤k}(0≤k≤N)\operatorname{ans}[k]=a+\max\{t\mid 0\le t\le K,\ c_t\le k\} \qquad(0\le k\le N)

へ変換する。t=0t=0 で始め、kk を 0 から順に増やし、t<Kt<K かつ ct+1≤kc_{t+1}\le k の間だけポインタ tt を進めれば、全予算の回答を追加 O(N)O(N) 時間で得られる。

例えば元の文字列が SR なら、固定端込みでは SSRR、差分は 010、0 の位置は 0 と 2 である。初期嬉しさは a=0a=0、最小費用の列は c=[0,2]c=[0,2] だが、予算 k=0,1,2k=0,1,2 に対する出力は [0,0,1][0,0,1] となる。最小費用の列をそのまま出力しないことに注意する。

典型の発動条件

文字flipの境界差分化

隣接文字の一致・不一致や遷移数を最適化したいとき、文字そのものから境界へ視点を移す。一文字の操作は隣接二差分、連続区間の反転は区間両端の差分だけを変える。端の扱いを固定すれば、目的量と差分の個数の関係も揃えやすい。

path matchingのcontraction貪欲

列から隣接しない所定個数の要素を最小和で選ぶとき、パスの辺を選ぶマッチングへ移せる。最小辺の選択後に両隣との補正縮約を行えば、各選択個数の最適値を順に得られる。単に軽い辺を順に確定して隣辺を消すだけでは、後の個数に対する最適解を失う。

問題固有の要素

嬉しさが数えるのは RS だけだが、固定した S と R を両端へ足すと、全ての異符号境界の個数から嬉しさを復元できる。この変換で左右の向きの違いを吸収してから、0 の組を消す問題へ進む。

もう一つの着目点は、操作回数が「高々」であること。増加に役立たない反転区間を除いてよいため、予算以下で目標を達成する操作を、同じ増加量の隣接 0 の組へ正規化できる。

正当性

まず、同じ文字への反転は偶奇だけが最終状態を決め、操作順にも依存しない。したがって、任意の操作列を「最終的に奇数回反転された文字だけを一回ずつ反転する」形へ、回数を増やさずに直せる。

その文字集合を極大な連続区間に分ける。一つの区間 [l,r][l,r] は、初期差分の dl−1,drd_{l-1},d_r だけを反転する。別の区間との間には未反転の文字が少なくとも一つあるので、区間どうしは差分の端点を共有しない。従って、それぞれの区間による 1 の個数の増減を独立に足せる。

初期差分の両端反転後の両端1 の個数の増減
0011+2
01 または 1010 または 010
1100−2

高々 kk 回で嬉しさを少なくとも tt 増やす操作を考える。00 以外の区間を丸ごと除けば、費用は減り、最終的な嬉しさは減らない。残った 00 の区間数は少なくとも tt なので、必要ならそこから tt 区間だけを残せる。これで費用を増やさず、嬉しさをちょうど tt 増やす操作を得る。t=0t=0 なら全区間を除けばよい。

次に、残った一つの区間の差分端点を p<qp<q とする。両端は初期状態で 0 なので、閉区間 [p,q][p,q] には少なくとも二つの 0 がある。その中で隣り合う二つを zj,zj+1z_j,z_{j+1} と選び、反転する文字区間を [zj+1,zj+1][z_j+1,z_{j+1}] へ縮める。この区間は元の [p+1,q][p+1,q] に含まれ、費用は zj+1−zj≤q−pz_{j+1}-z_j\le q-p。新たな両端も 00 なので、嬉しさの増加は 1 のままである。

この縮小を各区間で独立に行っても、元から分離していた区間が重なったり、同じ 0 を使ったりすることはない。従って、任意の目標達成操作から、費用が元以下の tt 組の隣接 0 を得られる。「組が交差しない」と言うだけでなく、各区間の内側へ縮めることで、途中に未使用の 0 を挟む組も不要だと分かる。

逆に、DD の隣接しない tt 要素を選んだとする。各辺 (zj,zj+1)(z_j,z_{j+1}) に対し、文字 xzj+1,…,xzj+1x_{z_j+1},\ldots,x_{z_{j+1}} を一回ずつ反転する。端点を共有しない辺に対応する文字区間は互いに分離しており、各区間が独立に 1 の個数を 2 増やす。さらに 0≤zj<zj+1≤N0\le z_j<z_{j+1}\le N なので、反転範囲は必ず x1,…,xNx_1,\ldots,x_N に収まり、固定した x0,xN+1x_0,x_{N+1} を変更しない。よって辺の重みの総和回で嬉しさをちょうど tt 増やせる。

以上の両方向の対応から、嬉しさを少なくとも tt 増やす最小費用 ctc_t は、パス上の tt 辺マッチングの最小重みに等しい。公式解説は操作を左から順に並べ、11→00 を行う操作を省けることから 0 の組への帰着を示す。ここでは、同じ操作の可換性を使い、最終反転集合の連続区間から、隣接する 0 に限定できることと固定端での合法性まで示した。

マッチング以降は主単元の費用保存対応を用いる。パス GG の tt 辺マッチングの最小重みを OPT⁡G(t)\operatorname{OPT}_G(t) と書く。最小辺を ii、その重みを wiw_i、縮約後のパスを G′G' とすると、実行可能な辺数 t≥1t\ge1 について、

OPT⁡G(t)=wi+OPT⁡G′(t−1)\operatorname{OPT}_G(t)=w_i+\operatorname{OPT}_{G'}(t-1)

が成立する。従って、縮約時に取り出す重みを累積すれば全ての ctc_t が得られる。元の距離は正であり、最小辺を用いる補正重みも正なので、ctc_t は狭義に増加する。最後に ct≤kc_t\le k を満たす最大の tt を選ぶことで、予算内で達成できる最大の増加量を選べる。初期嬉しさ a=(b−1)/2a=(b-1)/2 を加えた ans⁡[k]\operatorname{ans}[k] が求める答えである。

実装上の注意

  • 固定端の文字は反転できないが、差分の位置 0 と NN は通常の候補に含める。例えば端点 0 の組なら、文字 1 から始まる合法な反転区間になる。
  • m<2m<2 なら辺はなく、K=0K=0。全ての予算に初期嬉しさを出す。全交互の文字列でも、それ以上増やせるとは限らない。
  • heap には現在の重みと辺 ID を入れる。削除した辺の要素が後から取り出されたら捨てる(stale entry)。内部縮約で新しい辺 ID を発行し、元の三辺を無効化すれば、同じ ID の重み更新と古い要素を混同しない。ID を再利用するなら版番号等で現在の要素かどうかも判定する。
  • 左右の隣辺は、元の配列の添字ではなく、現在生きている辺の双方向リンクから取得する。両隣がある場合だけ三辺を補正辺へ置き換え、外側のリンクをつなぎ直す。端の辺ならその辺と存在する隣辺を削除するだけで、補正辺は作らない。リンク用番兵を重み 0 の実辺として扱わない。
  • 縮約は K=⌊m/2⌋K=\lfloor m/2\rfloor 回まで。予算への変換では t<Kt<K を確かめてから次の費用を参照し、k=Nk=N でも配列の外へ進めない。操作は高々 kk 回なので、余った予算を使い切る必要はない。

復習の核

操作の途中を追うのが難しいときは、同じ場所への操作が打ち消せるかを調べ、最終的に変更する集合を見る。本問では、その集合の連続区間が「差分の両端だけを変える操作」になり、増やさない区間の除去と区間の縮小から、隣接 0 のマッチングまで導ける。

縮約貪欲では、最小辺を永久に固定するのではなく、両隣へ置き換える費用を補正辺に残す。三辺の重みが (2,1,2)(2,1,2) なら、最小費用は一辺で 1、二辺で 1+(2+2−1)=41+(2+2-1)=4 となることを再現し、最後に費用の列を予算ごとの最大値へ戻す。

計算量と制約

時間

一テストケースの文字列長を NN とする。差分と距離列の構築は O(N)O(N)。辺の初期数と縮約回数 KK はともに O(N)O(N) で、各回の辺の追加・削除は定数個である。古い heap 要素も各要素につき一回しか取り出さないため、縮約全体は O((N+K)log⁡N)=O(Nlog⁡N)O((N+K)\log N)=O(N\log N)。予算への変換と N+1N+1 個の出力を含めても O(Nlog⁡N)O(N\log N) である。

空間

差分、0 の位置、辺の重み・生存情報・双方向リンク、heap、最小費用列と回答に O(N)O(N)。新しい辺 ID を使っても、追加される辺は縮約一回につき高々一本なので O(N)O(N) に収まる。

制約との対応

公式制約は 1≤T≤1041\le T\le10^4、2≤N≤1062\le N\le10^6、一入力内の NN の総和が 10610^6 以下。文字列は S と R だけからなる。各ケースを順に処理すれば、全体の時間は O(∑Nlog⁡N)O(\sum N\log N)、空間は最大のケースの長さに対して線形である。時間制限は 3 秒、メモリ制限は 1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Celester 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: path matchingのheap縮約greedy

主題
  • path matchingのheap縮約greedy: 重み付きpathの最小k-matchingについて、最小edge採用後の補正縮約を証明し、heapと双方向linkで全cardinalityの最適値を求められる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: path matchingのheap縮約greedy

    補助タグ: 貪欲法と交換論

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: path matchingのheap縮約greedy

    • 重み付きpathの最小k-matchingについて、最小edge採用後の補正縮約を証明し、heapと双方向linkで全cardinalityの最適値を求められる。

    先に読む単元:

    • 交換論から選択順を導く — 局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。
    • priority queue・best-first列挙 — 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題