考察
初期向きが+xで毎回90度回転するため、1,3,5,…回目は必ずy軸、2,4,6,…回目は必ずx軸の正負どちらかへ進む。
各step直前の向きに関係なく次axisの正負はL/Rの選択で自由に選べるので、odd stepのsigned sum=Yとeven stepのsigned sum=Xを独立に解ける。
各axisの項数は最大40で、符号2^40全列挙は大きいが半分ずつなら各2^20に収まる。
採用する候補: odd/evenの2つのsigned-sum問題をmeet-in-the-middleで復元し、desired方向列をL/Rへ変換する。
棄却する候補: N回のL/R列2^N通りをsimulationする。
N≤80で指数が大きすぎる。
棄却する候補: 到達可能座標をsum幅のboolean DPで管理する。
A_i総和が最大8×10^8で、座標幅に比例する配列を持てない。
odd indexのA列をtarget Y、even index列をtarget Xとしてsolveする。solveは列を半分に分け、各halfの全maskで+/- sumを列挙し、一方をhash mapへ保存して補数pairを探し、各項のsignを返す。どちらか失敗ならNo。成功時、各iのtarget directionをoddなら±y、evenなら±xに設定し、初期direction +xから左回転で一致すればL、そうでなければRを出してdirectionを更新する。
典型の発動条件
meet-in-the-middle
発動条件: 40項程度のbinary選択で値域が大きく通常DPを使えないとき。
前後半の候補sumを列挙して補数を辞書検索する。
直交axisの独立化
発動条件: 90度turnを毎step行い、移動axisがparityで固定されるとき。
odd stepをy、even stepをxのsigned sumへ分ける。
抽象解から操作列への復元
発動条件: DPで絶対方向を決めた後に相対turnを出力するとき。
current directionとの差±1からL/Rを選ぶ。
問題固有の要素
rotation列は前stepの向きへ依存して見えるが、axisが交互なので各stepの正負方向は独立に選べ、依存は最後のL/R復号だけに残る。
別の問題へ持ち帰る視点: 相対操作が絡む構成問題では、まず絶対状態列を独立に設計し、隣接差から操作へ戻せないか考える。
正当性
signed sum B_iの前半全maskをsum→mask辞書へ入れ、後半sum tに対してtarget-tが辞書にあれば符号列を復元できる。 odd/evenで得た符号は実際の絶対方向を指定し、現在方向からその方向へ+90度ならL、−90度ならRと一意に変換できる。 座標依存を2本の1次元問題へ分離し、判定だけでなく各stepの符号maskも復元できる。
実装上の注意
- 入力の1-index odd/evenと0-index array parityを取り違えず、最初のstepはy方向である。
- sumは最大8×10^8程度で符号付き64bitを使い、hash mapには同じsumのmaskを1つ保持すればよい。
- 方向を0:+x,1:+y,2:-x,3:-y等で持ち、mod 4の負値を正規化する。
復習の核
- 最初のL/Rが±yを選ぶことと、次の±x signが現在向きから必ずどちらか一回転で得られることを4方向tableで確認する。
計算量と制約
時間
期待O(2^{ceil(N/4)}+N)、odd/evenそれぞれを半分に分けhash join。平衡mapなら追加log列挙数。
空間
O(2^{ceil(N/4)}+N)。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 80; 1 \leq A_i \leq 10^7; -10^9\leq X,Y \leq 10^9; All input values are integers.
出典