ABC 376 F — Hands on Ring (Hard)

考察

指示を一つ達成するたびに、指定された手の位置は目標位置に確定する。両手の位置を常に状態へ持つ代わりに、確定した位置を指示から復元し、もう一方の手の位置だけを残そう。さらに、一つの指示の間に両手をどう動かすかは、指定手を時計回りに運ぶか、反時計回りに運ぶかの二候補に絞れる。

指示の直後に残す位置は一つだけ

位置は問題文と同じく 1,2,…,N1,2,\ldots,N とする。指示 ii は手 HiH_i を目標 TiT_i へ運ぶものとし、番号が増える向きを時計回りと呼ぶ。

両手の位置をそのまま持つと、一層に O(N2)O(N^2) 状態がある。しかし指示 ii の直後には、手 HiH_i は必ず TiT_i にある。したがって自由なのは、もう一方の手の位置 jj だけである。同じ jj に至る履歴なら、その後に可能な操作も費用も同じなので、最小費用だけを残せる。

以下では、各指示を後述の二候補で達成する形に限って、指示 ii の直後に他方の手が jj にある最小費用を dpi[j]dp_i[j] とする。余分な移動を後へ延期できるため、この限定でも全体の最適解を失わない。正規化の理由は「正当性」で確認する。

初期位置は左手が1、右手が2である。仮想の指示 H0=L, T0=1H_0=L,\ T_0=1 を置けば、最初から同じ状態定義を使える。

dp0[2]=0,dp0[j]=∞(j≠2)dp_0[2]=0,\qquad dp_0[j]=\infty\quad(j\ne 2)

指示 i−1i-1 から指示 ii へ進むとき、まず実際の左右の位置を復元する。Hi−1=LH_{i-1}=L なら (L,R)=(Ti−1,j)(L,R)=(T_{i-1},j)、Hi−1=RH_{i-1}=R なら (L,R)=(j,Ti−1)(L,R)=(j,T_{i-1}) である。そこから、今回の指定手の位置を aa、他方の位置を bb、目標を t=Tit=T_i として取り出すと、次の表になる。

今回の指定手指定手の位置 aa他方の位置 bb
Hi=Hi−1H_i=H_{i-1}Ti−1T_{i-1}jj
Hi≠Hi−1H_i\ne H_{i-1}jjTi−1T_{i-1}

表の下段では、前の層で自由だった手が今回の指定手になる。したがって、常に jj を障害物の位置として扱ってはいけない。

一方向の費用と到着位置を距離で求める

現在の位置 a,ba,b と目標 tt が決まったら、方向 d∈{+1,−1}d\in\{+1,-1\} を選ぶ。d=+1d=+1 が時計回り、d=−1d=-1 が反時計回りである。位置の正規化と、その方向へ進む距離を次で定義する。ここで  mod N\bmod N は、負の値に対しても 0,1,…,N−10,1,\ldots,N-1 の剰余を返すものとする。

pos⁡(x)=1+((x−1) mod N),Dd(x,y)=(d(y−x)) mod N.\begin{aligned} \operatorname{pos}(x)&=1+((x-1)\bmod N),\\ D_d(x,y)&=(d(y-x))\bmod N. \end{aligned}

指定手は、その方向へ m=Dd(a,t)m=D_d(a,t) 歩進めば目標へ着く。途中で踏む位置の集合を、始点を除き終点を含む弧 (a,t](a,t] と書く。他方の手がこの弧にある条件は、次の不等式で判定できる。

0<Dd(a,b)≤m0<D_d(a,b)\leq m

手は重ならないため a≠ba\ne b である。終点も含めるので、b=tb=t の場合も「途中で塞がる」と判定する。一方、a=ta=t なら m=0m=0 で弧は空になり、動かす必要はない。

弧が塞がらなければ指定手だけを動かす。塞がるなら、他方の手を同じ向きに目標の一つ先まで動かして、指定手の通り道を空ける。「押す」とは、接触した二つの手を同時に動かす操作ではない。必要なときに先に他方の手を一歩進め、空いた位置へ指定手を進めるという、合法な操作の繰り返しである。

この方向の追加費用を cc、終了後の他方の手の位置を b′b' とすると、二つの場合を次のように評価できる。

弧の状態追加費用 cc他方の位置 b′b'
b∉(a,t]b\notin(a,t]mmbb
b∈(a,t]b\in(a,t]m+Dd(b,t)+1m+D_d(b,t)+1pos⁡(t+d)\operatorname{pos}(t+d)

押す場合、他方の手は bb から tt まで進み、さらに一歩進む。そのため費用に Dd(b,t)+1D_d(b,t)+1 が加わる。到着位置だけを変えて、この移動費を足し忘れないようにしよう。

例えば N=5N=5、左手が1、右手が2にあり、指示が「左手を3へ」なら、二方向は次のようになる。

  • 時計回りでは右手が弧の中にある。左手は 1→2→31\to2\to3 の2歩、右手は 2→3→42\to3\to4 の2歩で、計4回。終了位置は (L,R)=(3,4)(L,R)=(3,4) になる。
  • 反時計回りでは右手を避けて左手を 1→5→4→31\to5\to4\to3 と3歩動かせる。費用は3回、終了位置は (L,R)=(3,2)(L,R)=(3,2) になる。

この時点では反時計回りが安いが、残る右手の位置が違うので、費用4の候補も捨てない。例えば次の指示が「右手を4へ」なら、時計回りの候補は追加操作なしで達成できる。

二候補を次の層へ渡す

各指示の前に次配列をすべて ∞\infty にする。有限な dpi−1[j]dp_{i-1}[j] ごとに指定手と他方の位置を復元し、両方向について上の c,b′c,b' を求め、次を更新する。

dpi[b′]←min⁡(dpi[b′], dpi−1[j]+c)dp_i[b']\gets\min\bigl(dp_i[b'],\ dp_{i-1}[j]+c\bigr)

終了時には今回の指定手が TiT_i に固定されるため、次の添字は、押したかどうかを反映した他方の位置 b′b' である。一層の全状態を処理してから配列を交換する。これを指示順に繰り返し、最後は他方の手の位置に条件がないので、答えは次の最小値になる。

min⁡1≤j≤NdpQ[j]\min_{1\leq j\leq N}dp_Q[j]

各状態から二方向を定数時間で評価できるので、全体は O(NQ)O(NQ) 時間となる。

典型の発動条件

一方が固定される状態圧縮 DP

発動条件: 各操作後に一要素の位置が命令で確定し、他方だけ自由なとき。

二体の位置状態を自由側の一次元へ圧縮する。

問題固有の要素

自由に両手を動かせても最適経路は、障害を動かさないか最小限だけ一緒に押すかの二形に正規化できる。

別の問題へ持ち帰る視点: 操作後に必ず確定する情報を DP 添字へ残さず、次段の文脈として外に出す。

正当性

指示の直後に指定手の位置は確定している。他方の手の位置も同じなら両手の配置が一致し、将来の合法な操作と費用は過去の動かし方に依存しない。従って同じ状態へ来る候補では最小費用だけを保持してよい。

一つの指示では、指定手を目標へ運ぶ向きを決めて考える。その弧を他方の手が塞がなければ、指定手だけを動かせる。塞ぐなら、手を追い越せないので、他方の手を進行方向へ弧の外まで退避させる必要がある。最寄りの退避先は目標の一歩先であり、指定手の Dd(a,t)D_d(a,t) 歩と他方の Dd(b,t)+1D_d(b,t)+1 歩で実現できる。指定手が他方の手にぶつかる直前に、他方の手を一歩先へ動かすことを繰り返せば、衝突せずに実現できる。

指定手の往復や余分な周回は、今回の目標到達には不要である。また、他方の手を通り道の確保に必要な位置より先へ動かす操作は、今は行わず、後の指示でその移動が必要になる直前に行えばよい。操作回数は増えず、将来不要なら削除できる。最後の指示の後に備える移動も不要なので、全体最適解の一つは、各指示を二方向の最小移動形だけで達成するように正規化できる。

DPはこの二候補をそれぞれ正しい費用と終了位置で次の層へ渡す。初期配置から始めて全指示を処理するため、最後の層の最小値が全体の最小操作回数である。

実装上の注意

  • 位置は1始まりで統一する。剰余が負になり得る言語では、非負の剰余を返すよう補正する。例えば pos⁡(0)=N\operatorname{pos}(0)=N、pos⁡(N+1)=1\operatorname{pos}(N+1)=1 である。
  • 目標が他方の位置と一致する b=tb=t では、その手を一歩退避させる。弧の判定を厳密不等号だけにすると、この場合を見落とす。
  • 指定手が既に目標にある a=ta=t では、両方向とも費用0、他方の位置はそのままである。同じ候補を二度更新しても最小値は変わらない。
  • 指定手が切り替わったら a,ba,b を入れ替えてから距離を計算する。更新先は旧添字 jj とは限らない。
  • 遷移元と次配列は分け、次配列は指示ごとに初期化する。∞\infty の状態からは遷移せず、無限大への加算によるオーバーフローを避ける。

復習の核

  • 操作後に必ず確定する位置を状態の添字から外し、必要になったら指示から復元する。
  • 円環の「途中にあるか」は、方向を固定した距離で判定する。目標にある障害物も含めるので、弧は (a,t](a,t] である。
  • 次の状態が異なるなら、直近の移動費が大きい候補も残す。押す費用と、押した後に自由となる手の位置を組で求めよう。

計算量と制約

時間

各指示で次配列の初期化と NN 状態の走査を行う。各状態の二方向の距離・衝突判定・更新はいずれも定数時間で、全体は O(NQ)O(NQ)。最後の最小値の走査は O(N)O(N) である。

空間

直前と次の二層の配列だけを保持すれば、作業領域は O(N)O(N)。指示を逐次読み込む場合は全体でも O(N)O(N)、全指示を保存する場合は O(N+Q)O(N+Q) である。

制約との対応

公式制約は 3≤N≤30003\leq N\leq3000、1≤Q≤30001\leq Q\leq3000、1≤Ti≤N1\leq T_i\leq N、Hi∈{L,R}H_i\in\{L,R\} である。最大で NQ=9×106NQ=9\times10^6 状態、それぞれ二方向を調べる。円環上の一歩ずつの移動を実際にシミュレーションせず、距離式で定数時間にまとめることが必要となる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Hands on Ring (Hard) の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DPの最小十分状態

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

      学習の位置

      体系上の位置: 最小十分状態からDPを設計する

      • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

      この解説で扱わないこと:

      • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題