ABC 266 Ex — Snuke Panic (2D)

考察

event p'=(t',x',y') から p=(t,x,y) へ移れる条件は y'≤y かつ |x−x'|+y−y'≤t−t' である。

a=t−x−y、b=t+x−y と変換すると、この条件は a'≤a、b'≤b、y'≤y の三次元dominanceになる。

棄却する候補: 時刻順に各eventから過去全eventを調べ、移動可能ならdp候補を更新する。

event対がN^2個あり、N=10万では比較できない。

採用する候補: 各eventを(a,b,y)へ写し、yでsweepしながら(a,b)prefix rectangleのdp最大値を疎な二次元BIT/segment treeで照会してpoint updateする。

移動可能な全過去eventが直交prefix領域になり、座標圧縮した二次元dominance maxへ置き換えられる。

開始状態(0,0,0)も変換後点(a,b,y)=(0,0,0)、dp=0として追加すれば、原点から直接到達可能なeventを同じ照会で扱える。

三座標が全て非減少なら変換の逆式から時刻も非減少なので、dominance順はdpの有向非巡回依存を保つ。

典型の発動条件

移動可能領域の座標変換

発動条件: 時空間の到達条件が絶対値を含む複数の線形不等式で表されるとき。

絶対値を二不等式へ分け、それぞれを新座標の大小比較へ変換する。

三次元dominance最大値DP

発動条件: 前状態から現状態への遷移可否が三座標全ての非減少で、点重み最大chainを求めるとき。

一軸でsweepし、残る二軸のprefix rectangle maximumを動的データ構造で取得する。

offline疎二次元データ構造

発動条件: point updateとprefix rectangle queryが必要だが、座標と更新点が事前に分かるとき。

外側BITの各nodeに現れる内側座標だけを集めて圧縮し、BIT on BITでmaxを持つ。

問題固有の要素

負のy方向禁止は独立な条件y'≤yとして残り、x方向の速度制限だけがa,bの二軸へ展開される。

別の問題へ持ち帰る視点: 移動制約の座標変換では、既に単調な軸を無理に混ぜずdominanceの一軸として保持する。

正当性

変換後の三座標の大小関係は、元の移動可能条件と同値である。原点も含めた過去の到達可能点から最大値を取るので、最適経路の最後の移動を必ず遷移に含む。逆に各遷移は合法であり、依存順のDPが最適値を保つ。

実装上の注意

  • y,a,bのdominanceに矛盾しない順で同一座標群を処理し、到達不能eventへ−INFからA_iを加えない。
  • 変換座標と獲得量合計はいずれも64 bit整数で保持する。

復習の核

  • 絶対値付き到達条件は符号ごとの線形不等式へ分け、全てが座標wise orderになる変数を探す。
  • 高次元dominance DPでは、一軸を処理順に消して残りをrange query構造へ載せる。

計算量と制約

時間

O(N log²N)、三次元dominance DP、圧縮二次元BIT。

空間

O(N log N)。

制約との対応

公式制約の確認範囲: Time limit: 5 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^5; 1 \leq T_i \leq 10^9; 0 \leq X_i,Y_i \leq 10^9; 1 \leq A_i \leq 10^9; The triples (T_i,X_i,Y_i) are distinct.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Snuke Panic (2D) の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: event順にactive集合を更新する

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

    主タグ: event・値順のオフライン走査

    補助タグ: 座標・値の順序保存圧縮 幾何の基本判定・配置・座標変換 区間monoid要約

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

    学習の位置

    体系上の位置: event順にactive集合を更新する

    • 値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。

    先に読む単元:

    • 疎なkeyの順序を保ってdense indexへ圧縮する — 保持すべき疎な座標をsort-uniqueして順序・等値性を添字へ写す。距離・時間差・区間長も使う場合は元座標と間隔を併せて保存する。
    • 幾何の基本判定と座標変換 — 座標と外積・距離式で向きや交差を代数判定し、凸幾何へ進む前提を作る。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 更新を単に逆順へ読む処理、答えの局所寄与だけを集計する順序交換、sort-uniqueしたkeyの添字化、および固定方向の単純scan。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題