ABC 326 F — Robot Rotation

考察

初期向きが+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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Robot Rotation の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: meet-in-the-middle・半分全列挙

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

    主タグ: meet-in-the-middle・半分全列挙

    補助タグ: 構成解・witness復元

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

    学習の位置

    体系上の位置: meet-in-the-middle・半分全列挙

    • 探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題