ABC 274 F — Fishing

考察

最適なlength-A netは、捕まえるfishのうち最左のものにleft endpointを合わせても捕獲集合を減らさない。

left endpointをfish iのposition X_i+V_i tへ追従させると、fish jがnet内にいる条件は0≤(X_j−X_i)+(V_j−V_i)t≤Aで、t≥0上の一intervalになる。

棄却する候補: timeとnet positionを連続量のまま探索する。

候補が無限にあり、任意時刻ごとのfish positionsを列挙できない。

採用する候補: anchor fish iを全列挙し、各fishのnet滞在time intervalのweighted add/remove eventsをsortしてsweepする。

典型の発動条件

moving objectsの相対座標化

発動条件: moving windowを一objectへ固定すると、他objectsの所属条件がtimeの一次不等式になるとき。

fish iを静止anchorとみなし、各fish jのrelative position ΔX+ΔVtが[0,A]に入る区間を求める。

重み付きinterval event sweep

発動条件: 各対象が有効なtime rangeを一intervalで持ち、同時に有効なweight総和の最大を求めるとき。

entryで+W、exitで−Wのeventsを時刻順に処理してmaximum active weightを更新する。

問題固有の要素

net left endpointのanchorは捕獲時点の最左fishに選べるため、N anchorsで全optimal placementsを覆う。

別の問題へ持ち帰る視点: 連続位置の固定長window最適化では、optimal windowを含有objectの境界へslideして候補を離散化する。

正当性

relative velocity ΔVが0ならrelative position ΔXが[0,A]かで全時刻/emptyを判定し、ΔV≠0なら二不等式からentry/exit timesを得る。 net endpointsはinclusiveなので同じtimeにentryとexitが重なる場合、その瞬間のweightを評価するためadd eventsをremove eventsより先に処理する。 固定anchorでは捕獲weightがinterval endpointsでのみ変化し、2N eventsの最大prefix weightを求めればよい。

実装上の注意

  • rational endpointの大小はcross multiplicationで比較してfloating errorを避け、negative-time portionをt=0でclipする。
  • 同時刻eventのinclusive規約をsort tie-breakへ反映し、unbounded intervalにはremove eventを作らない。

復習の核

  • 連続なwindow位置は、最適解を失わず端点をobjectへ合わせて有限候補にする。
  • 移動体のwindow membershipはanchorとの相対位置に直し、有効time intervalのoverlapとして見る。

計算量と制約

時間

O(N² log N)、各anchorにN個の有効時刻区間をsort。

空間

O(N)、一anchorのevent。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2000; 1 \leq A \leq 10^4; 1 \leq W_i\leq 10^4; 0 \leq X_i\leq 10^4; 1 \leq V_i\leq 10^4; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

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

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

    補助タグ: 幾何の基本判定・配置・座標変換

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題