考察
各階の移動可能な連結成分を一頂点へ縮約し、コイン総和c_vと、隣接する階の成分間の辺を求める。同一階内では自由に往復できるので、訪れた成分のコインを全て回収できる。下へ降りるハシゴを高々一度使った後は、上へ進むだけになる。
P_vをvから上るだけで得る最大値、Q_vをvから出発して最初は上り、出発階より上で一度だけ下りてもよい最大値とする。下りを使わない場合もQに含める。さらに上階uから下階vへ最初に下り、その後上るだけの値をR(u,v)とする。Rではuは既に訪問済みなので、再びuへ上ってもc_uを二重加算しない。
上階の全P,Qが確定した状態で、階を下へ処理する。U(v)をvの一つ上の隣接成分集合とすると、
P_v=c_v+max(0,max_{u∈U(v)}P_u)。
各辺u-vについて
R(u,v)=max(c_v+P_u, c_u+c_v+max_{w∈U(v),w≠u}P_w)。
前者はvから同じuへ戻る場合、後者は異なるwへ上る場合である。上へ進まずvで止まるc_u+c_vも前者以下なので覆われる。
Q_vはまずc_v+max(0,max_{u∈U(v)}Q_u)で初期化する。さらにv→u→zと上ってから下る全候補を考え、R(u,z)+(z=vなら0、z≠vならc_v)で更新する。z=vではRが既にc_vを含み、z≠vでは出発点vは以後訪れないので加える。
最終的なvからの答えはmax(Q_v,max_{zが一つ下の隣接成分}R(v,z))。後者を落とすと、最初の移動でハシゴを使う経路が欠ける。各最大値で除外する成分は高々一つなので、接続先ID付きの上位二件を保持すれば全辺を定数回走査できる。
典型の発動条件
連結成分縮約
発動条件: 同一領域内は自由に往復して報酬をすべて回収でき、領域外との接続関係だけが以後の選択を左右する場合。
各階の四近傍連結成分を一頂点にまとめ、数字の総和を頂点重み、上下階で接する関係を辺として扱う。
一回だけ逆向き辺を使う層状グラフ DP
発動条件: 本来は単調に層を進む DAG に、一度だけ利用できる逆向き遷移を自由な場所へ追加できる場合。
梯子の未使用・使用済みと階境界の出入口を状態にし、一段下降を挟む経路を上下の単調経路から合成する。
除外最大値の上位二件保持
発動条件: 候補集合から指定された ID と同じ候補だけを除外して最大値を求める処理が、多数の遷移で繰り返される場合。
や の値と接続先成分 ID の上位二件を保持し、一位の ID が除外対象なら二位、異なるなら一位を使う。
問題固有の要素
梯子一本が作る非単調性は任意の巡回ではなく、上階成分を出て一段下り、同じ階へ戻る迂回に限られる。
別の問題へ持ち帰る視点: 単調な層状グラフへ逆向き辺を一度だけ加える問題では、迂回の二端点が同一かどうかを状態に残すと二重計上を制御できる。
正当性
上るだけの経路は最初の上り先で分類でき、Pの遷移になる。ハシゴを最初に使う場合は、その下り先vと次の上り先wでRを分類する。階は以後増えるので既訪問成分と重なる可能性は同じ階のuだけであり、w=uの場合だけc_uを引く。最初に上る経路では、ハシゴ使用がさらに上ならQ_uを引き継ぎ、すぐに下るならR(u,z)を使う。後者で重なる可能性がある出発成分はz=vだけである。この分類は全経路を尽くし、各コインを一度だけ足す。最初に下るケースも最後の答えで合成している。
実装上の注意
- 階間の同じ成分対の辺は重複除去する。上位二件には値だけでなく相手の成分IDを持たせる。
- P_v、R(上階u,v)、Q_vの順に処理し、その後にvより上の開始点用のRを保存する。
- Q_vだけを答えにせず、最初に下るR(v,z)も比較する。コインの二重加算は階ではなく成分IDの一致で判定する。
復習の核
- 開始成分を とし、「上るだけ」は 、「最初に上り、途中で一度下りてもよい」は 、「最初に隣接する下階の成分 へ下り、その後は上るだけ」は に対応させる。 は下らない経路と、その場で止まる場合も含む。開始直後に下る経路を落とさないため、答えでは と各 を比較する。
- 途中で下る経路 で、加算済みの成分を追う。 は の一つ上、 は と同じ階にある。 では下降元 を既に数えているので、再上昇先が なら をもう一度足さない。さらに開始成分 と合成するときは、 なら が既に を含むので足さず、 のときだけ を足す。
- 除外するのは一つの成分 ID である。上位二件は異なる ID の候補を残し、値が同じでも一件にまとめない。候補が一件しかなく、それが除外対象なら除外後の候補はない。同じ成分へ戻る場合と、上階へ進めず止まる場合を別に確認する。
計算量と制約
時間
元セル V=FHW、縮約頂点 C≤V、階間distinct辺 E≤(F−1)HW。BFS縮約O(V)、辺sort重複除去O(Vlog V)、ID付き上位二件を走査保持すればDP O(C+E)、Q回答O(Q)。
空間
マス→成分、graph、境界dpで O(V+C+E+Q)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: F,H,W are integers.; 1 \leq F \leq 10; 1 \leq H,W \leq 500; S_{k,i,j} is either a digit (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) or #. (1 \leq k \leq F, 1 \leq i \leq H, 1 \leq j \leq W); Q is an integer.; 1 \leq Q \leq 10^5; G_i, A_i, B_i are integers. (1 \leq i \leq Q); 1 \leq G_i \leq F (1 \leq i \leq Q); 1 \leq A_i \leq H (1 \leq i \leq Q); 1 \leq B_i \leq W (1 \leq i \leq Q); S_{G_i, A_i, B_i} is not #. (1 \leq i \leq Q)
出典