A: Attack the Moles 原案：高橋 / 解説：保坂.

Presentation on theme: "A: Attack the Moles 原案：高橋 / 解説：保坂."— Presentation transcript:

1 A: Attack the Moles 原案：高橋 / 解説：保坂

2 問題概要 もぐらたたきをする もぐらは N 匹いる．時刻 Ti で位置 Xi に現れ，叩ける (その時刻でその位置に手が存在する) と Pi 点獲得 手は 2 本あり，左手は右手より左になければならない 得点を最大化 N <= 3,000

3 注目点 左手と右手の位置関係の制約は無視して解いてもよい
交差するような移動があっても左右の手を入れ替えて考えればよい 「ちょうど同じ位置にいてはいけない」という制約は「もぐらを両手で叩いても 1 回しか得点に加算しない」という制約に置き換えられる 入力を Ti の値でソートすれば，もぐら 2 匹の組に対して「同じ手で両方叩けるならばどちらを先に叩かなければならないか」が定まる Xi でソートされているのは釣りです XLeft, XRight を時刻 0 得点 0 のもぐらと考えるのが楽

4 遅い解法 dp[i, j] := (片方の手がもぐら i，片方の手がもぐら j を最後に叩いた状態での，得られている得点の最大値)
dp[i, k] + Pj (もぐら k を叩いてからもぐら j を叩ける) dp[k, j] + Pi (もぐら k を叩いてからもぐら i を叩ける) ただし i = j のときは Pi を加算しないことに注意 O(N3)

5 高速化 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] の最大値を高速に拾いたい

6 高速化 もぐら 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) という値が重要

7 高速化 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) も可能？

8 別解 最小費用流による方法 もぐら i に対して 2 つの頂点 INi と OUTi を作る
INi から OUTi へ容量 1，コスト -Pi の辺を張る もぐら i を叩いてからもぐら j を叩くことができる場合，OUTi から INj へ容量 1，コスト 0 の辺を張る 始点と終点も自然につけ，流量 2 を流す

9 別解 最小費用流の計算量評価 負辺を解消するための Bellman-Ford
O(N3) 最短路反復 (反復といっても 2 回) のための Dijkstra O(N2 log N) あるいは O(N2) 実は，負辺のグラフでのトポロジカル順序 (つまり，もぐらの出現が早い順) に処理すれば Bellman-Ford のループが 1 回で終わる 全体で O(N2 log N) あるいは O(N2)

10 結果 正解 / 提出： 2 / 57 提出チーム： 9 正解チーム： 2 最初の提出： yukim (00:13)
最初の正解： -Dint=char (03:05)