attack

A: ATTACK THE MOLES
原案：高橋 / 解説：保坂
問題概要
• もぐらたたきをする
• もぐらは N 匹いる．時刻 Ti で位置 Xi に現れ，叩ける
(その時刻でその位置に手が存在する) と Pi 点獲得
• 手は 2 本あり，左手は右手より左になければならない
• 得点を最大化
• N <= 3,000
注目点
• 左手と右手の位置関係の制約は無視して解いてもよい
• 交差するような移動があっても左右の手を入れ替えて考えればよ
い
• 「ちょうど同じ位置にいてはいけない」という制約は「もぐらを
両手で叩いても 1 回しか得点に加算しない」という制約に置き換
えられる
• 入力を Ti の値でソートすれば，もぐら 2 匹の組に対して
「同じ手で両方叩けるならばどちらを先に叩かなければ
ならないか」が定まる
• Xi でソートされているのは釣りです
• XLeft, XRight を時刻 0 得点 0 のもぐらと考えるのが楽
遅い解法
• dp[i, j] := (片方の手がもぐら i，片方の手がもぐら j を最
後に叩いた状態での，得られている得点の最大値)
• dp[i, j] は以下の最大値
• dp[i, k] + Pj (もぐら k を叩いてからもぐら j を叩ける)
• dp[k, j] + Pi (もぐら k を叩いてからもぐら i を叩ける)
• ただし i = j のときは Pi を加算しないことに注意
• O(N3)
高速化
• i > j のときは dp[i, j] = dp[j, i] として求めることにする
• dp[i, j] (i <= j) は以下の最大値
• dp[i, k] + Pj (もぐら k を叩いてからもぐら j を叩ける)
• ただし i = j のときは Pi を加算しない
• 「もぐら k を叩いてからもぐら j を叩ける」ようなもぐ
ら k たちの中での dp[i, k] の最大値を高速に拾いたい
高速化
•
•
•
•
もぐら k を叩いてからもぐら j を叩けるための条件
|Xj - Xk|<= V (Tj - Tk)
⇔ Xj - Xk <= V (Tj - Tk) and -(Xj - Xk) <= V (Tj - Tk)
⇔ V Tk - Xk <= V Tj - Xj and V Tk + Xk <= V Tj + Xj
• 各もぐらに関して，(V Ti - Xi, V Ti + Xi) という値が重要
高速化
• dp[i, *] を計算する段階で，
• dp[i, j] (i <= j) を計算するために，座標が [0, V Tj - Xj] × [0, V Tj +
Xj] の範囲にある点に書いてある値のうち最大のものをとる
• dp[i, j] を計算したら，座標 (V Tj - Xj, V Tj + Xj) の点に dp[i, j] と
書き込む
• これらを扱うデータ構造があればよい
• 2 次元 Binary Indexed Tree (Fenwick Tree) を使えば各
操作 O((log N)2)，定数倍も軽い
• 全体で O(N2 (log N)2)
• 上手い二分木を作れば O(N2 log N) も可能？
別解
• 最小費用流による方法
• もぐら i に対して 2 つの頂点 INi と OUTi を作る
• INi から OUTi へ容量 1，コスト -Pi の辺を張る
• もぐら i を叩いてからもぐら j を叩くことができる場合，
OUTi から INj へ容量 1，コスト 0 の辺を張る
• 始点と終点も自然につけ，流量 2 を流す
別解
• 最小費用流の計算量評価
• 負辺を解消するための Bellman-Ford
• O(N3)
• 最短路反復 (反復といっても 2 回) のための Dijkstra
• O(N2 log N) あるいは O(N2)
• 実は，負辺のグラフでのトポロジカル順序 (つまり，も
ぐらの出現が早い順) に処理すれば Bellman-Ford の
ループが 1 回で終わる
• 全体で O(N2 log N) あるいは O(N2)
結果
•
•
•
•
•
正解 / 提出： 2 / 57
提出チーム： 9
正解チーム： 2
最初の提出： yukim (00:13)
最初の正解： -Dint=char (03:05)

Download Report