考察
上下左右の選択は、座標系を変えると二つの独立な正負の選択になる。そこで同じ距離列に対する部分和DPを一度作り、二つの目標の選択列を別々に復元して、元の方向へ組み合わせる。
元座標では各を軸か軸のどちらか一方に使うため、両座標の選択が結び付いている。この結び付きを外すため、という45度座標変換を考える。各方向の変位は次のようになる。
ここでは二つの符号の全4組が揃っている。従って、一方の符号を決めても他方に制約は生じず、目標への到達を二つの符号和の問題へ分離できる。
とおく。側で正にする距離の和をとすると、負にする距離の和はなので、最終座標はである。側も同じ変形をすると、必要な部分和は
となる。分子のどちらかが奇数、または得られる目標のどちらかが未満・超過なら、ここで No と判定する。範囲内の整数でも、その和を作れるとは限らないのでDPで確かめる。
二次元の到達位置をそのまま管理すると、候補領域は総距離の二乗規模になる。一方、部分和ならからまでで済む。ただし、なので、真偽配列の各要素を一つずつ更新しても最大約回と重い。ここで到達集合をbitsetに詰め、64個の和を一語で更新する。
を「先頭個から選んで作れる和」のbitsetとし、を和が作れることと定義する。各行はbit からbit までを持つ。はbit だけを1にし、の順に
と更新する。右辺の前半は不採用、後半は採用して和にを加える場合を表す。どちらも更新前の行から計算するので、一つの距離を重複して使わない。またはが0なら No である。
経路を出力するため、ここでは先頭からの各段階の履歴を保存する方式を採用する。最終行だけでは、ある距離を使わずに残りの和を作れたかを判定できないからである。履歴自体は目標に依存しないので、で一つを共用できる。
一つの目標からの復元は、残りの和をとして、次の手順で行う。
- を目標またはにする。到達判定済みなので、最初はである。
- の順に、一つ前の行を調べる。1ならを使わずに残りの和を作れるので、不採用とし、は変えない。
- 0ならを採用し、とする。減算前にはで、不採用では到達できない以上、採用による遷移が必ず存在する。従って減算後もで、負の添字にはならない。
- 各位置の採否を記録しておく。全て戻ると、空の先頭部分で作れる和は0だけなので、となる。
採用・不採用の両方が可能でも、一つの経路が得られればよいので不採用を選んでよい。の復元結果を、の復元結果をとし、それぞれ採用を1、不採用を0で表す。二回目はから新たに戻り、履歴のbitを消さない。 同じを両方の部分和で採用してもよい。二つの採否は、一回の跳躍の二つの符号を表すからである。
例えば、目標なら、、、である。の到達集合はそれぞれ、、となる。
- では、側の残り6はで作れないので4を採用し、残り2にする。側の残り2は既に作れるので4を不採用にする。
- では、両方とも残り2をで作れないので2を採用し、残り0にする。
- では、両方ともなので1を不採用にする。
従って、と、異なる二列が得られる。各位置でを、、、と戻す。この例の出力は LRU となり、と目標に着く。一般の場合も長さの文字列の番目に方向を書き込み、Yes とともに出力する。
典型の発動条件
45度座標変換
二次元で各操作が軸または軸方向を選び、両座標の選択が結び付いているときに候補となる。へ写し、変換後の操作集合が二つの符号の全組合せになれば、各成分を独立に解ける。一部の符号組が欠けている問題では、この独立性は成立しない。
bitset subset sum と復元
正の整数の重みから各要素を高々一度選び、総和が数百万程度に収まるなら、到達可否をbitsetのshiftとORでまとめて更新できる。さらに選択列が必要なら各段階の履歴を残し、「直前の段階で、今の和へ既に到達できたか」を逆順に調べる。重み列が同じ複数の目標には、同じ履歴を共用できる。
問題固有の要素
45度変換後の四方向が単に候補を減らすのではなく、二符号の全直積になるため、二つの部分和を別々に解いても必ず一つの実方向へ合成できる。
別の問題へ持ち帰る視点は、多次元操作の候補集合が符号や小集合の直積になる座標系を探すこと。独立に解いてよいかは、成分の任意の組合せが元の合法な操作に戻るかで確認する。
正当性
部分和DPの各遷移は、を使わない選択と一度だけ使う選択を過不足なく表すので、は先頭個で和を作れることと同値になる。逆追跡では、処理前のを保つ。なら不採用で同じ和を残せる。偽なら遷移式のもう一方が真でなければならず、かつなので、採用してを減らせる。従って常に先頭個へ進め、最後はよりとなる。各添字を一度ずつ処理するので、得られた採否列は各距離を高々一度使い、指定した部分和を実現する。
各跳躍の方向と変換後の二符号は一対一である。から別々に復元した採否列を組み合わせても各位置で合法な一方向に戻り、変換後の終点はとなる。逆変換で元の終点もになる。反対に、合法な経路からは必ず二つの部分和が得られるので、偶奇・範囲の検査または到達判定で失敗した場合には経路は存在しない。
実装上の注意
- の偶奇・範囲をbitset参照前に検査する。目標0は空集合、目標は全要素の採用に対応し、どちらも有効である。が同値でも添字ごとに別の跳躍として扱う。
- 履歴は1 bitずつ詰めた格納を使う。1状態を1 byteで持つと約7.2 GBになり収まらない。約900 MBの履歴を関数の通常のローカル配列としてスタックに置かず、静的領域またはヒープに確保する。行全体の不要なコピーを避け、shiftやORの一時bitsetもメモリ見積りに含める。
- 64 bit語列でshiftを自作する場合は、語内の移動量0を特別扱いし、64 bitちょうどのshiftを避ける。最後の語のbit より上は範囲外として扱う。
- 逆追跡ではではなくを読む。方向は元の添字位置へ書き込む。文字列の先頭への挿入を繰り返すと、移動・コピーのため復元全体がになり得る。
省メモリ化の代替案として、個別公式解説には、距離列を前後に分割して各半分の到達集合を再計算し、目標を二つの部分和へ分けて再帰する方法がある。履歴全体を持たずに復元できるが、ここで具体化した逆追跡とは別の方式である。以下の計算量は、各段階の履歴を保存する方式について評価する。
復習の核
- 多次元の選択を独立に解く前に、変換後の候補が各成分の全組合せを含むか確認する。
- DPの復元では「今の状態が、残りの要素で実現可能」を保ちながら一段ずつ戻る。直前でも同じ和を作れれば不採用、作れなければ採用が必要になる。
- 複数の目標が同じ重み列を使うなら、到達履歴は一つでよい。目標ごとに残りの和と採否列を分ける。
計算量と制約
時間
一語を bitとし、bit からbit までの bitを格納する語数をとおく。入力・総和・目標の計算は、履歴の初期化と回のshift・OR・行保存はである。二つの目標の逆追跡は各段階で定数回のbit参照を行うので合わせて、方向列の組立てと出力も。全体でとなる。
空間
履歴はを含む行で、 bit語を個使う。shiftの一時領域は語、距離列・二つの採否列・出力文字列は合わせて領域である。全体は語、すなわち語。二つの目標に履歴を二組用意する必要はない。
制約との対応
公式制約は、、で、入力は整数。制限時間は5秒、メモリ制限は1024 MiBである。従って、最大の語数はとなり、DPは約語分の更新を行う規模になる。
最大サイズの履歴の容量は
で、約900.47 MB、約858.8 MiBである。これはbit と、各行の語境界への切上げを含む。shift用の一時bitset一つは byteで、OR結果も別に作る実装ならその分も加わる。これらと入力・出力などを含めて1024 MiBに収める。公式解説も履歴を全て保存するbitset方式を示しており、ここで補った逆追跡の不変条件・小例・語単位の見積りは、その手順を具体的に追うための説明である。
出典