H - 東京大学プログラミングコンテスト

2014/3/2 東京大学プログラミングコンテスト2013
H: Asteroids2
原案: 岩田
解答: 岩田，大坂
解説: 大坂
1
問題概要

𝑁 × 𝑁の格子があり，座標 𝑥𝑘 , 𝑦𝑘 に惑星がある（𝑀個）
縦方向𝑥には高々攻撃力𝑝𝑥 のレーザーを発射できる
 横方向𝑦には高々攻撃力𝑞𝑦 のレーザーを発射できる


小惑星は𝑎𝑘 以上𝑏𝑘 以下の攻撃を受けると安全に破壊でき
る

全ての小惑星を安全に破壊できるか？
格子のサイズ: 𝑁 ≤ 103
 惑星の数: 𝑀 ≤ 105

2
例
𝑝1 = 1
𝑞1 = 3
𝑝2 = 2
3~5
𝑞2 = 4 3~4 6~6
入力例
0 2
1
3
4 4 6
割り当て例
3
解法
とりあえずLPにしてみる
𝑒𝑖 =(縦方向 𝑥 = 𝑖 の攻撃力)
𝑓𝑖 =(横方向 𝑦 = 𝑖 の攻撃力)
 0 ≤ 𝑒𝑖 ≤ 𝑝𝑖
←最短路になりそうなやつ

0 ≤ 𝑓𝑖 ≤ 𝑞𝑖

𝑎𝑘 ≤ 𝑒𝑥𝑘 + 𝑓𝑦𝑘 ≤ 𝑏𝑘
𝑓𝑖′ = −𝑓𝑖 とすると後半の不等式は
 𝑓𝑦′𝑘 − 𝑒𝑥𝑘 ≤ −𝑎𝑘

𝑒𝑥𝑘 − 𝑓𝑦′𝑘 ≤ 𝑏𝑘
4
解法
変数𝑍を導入すると前半の不等式は
 𝑍 − 𝑒𝑖 ≤ 0
 𝑒𝑖 − 𝑍 ≤ 𝑝𝑖
 𝑍 − 𝑓𝑖 ≤ 0
 𝑓𝑖 − 𝑍 ≤ 𝑞𝑖
お？:
全て2変数の差の不等式になったので最短路
𝑥 − 𝑦 ≤ 𝑤を重み𝑤の辺 𝑦, 𝑥
負閉路があったらNG
変数の数: 2𝑛 + 1
制約式の数: 4𝑛 + 2𝑚
Bellman-Fordで𝑂 𝑛𝑚 （途中で打ち切ると速い）
5
結果







First Accepted (Onsite)
◊ ຣസ‫ں‬ƙᘓ（ひとり）(76:59)
First Accepted (Online)
◊ ຣസ‫ں‬ƙᘓ（ひとり）(76:59)
Total Submission: 52
Accepted: 6
Accepted / Total: 12%
Trying: 14
Trying / Total: 27%
6

Download Report