問題リンク
問題概要
数直線上にN体のロボットがいる。i番目のロボットは座標\(X_i\)にいて、起動させると正の方向に\(D_i\)動いた後、取り除かれる。
動いている途中に他のロボットに接触すると、そのロボットも起動する。
いくつかのロボットを起動した後、最終的に残っているロボットの組み合わせは何通りか。
解法
座標の昇順にソートした後、番号が大きい方(座標が大きい方)から次のDPをする。
\(dp[i][0]\) = i番目のロボットを起動しないときの、iより右のロボットの組み合わせの総数
\(dp[i][1]\) = i番目のロボットを起動したときの、iより右のロボットの組み合わせの総数
\(dp[N-1][0] = dp[N-1] = 1\)と初期化。
まず、i番目のロボットを起動しない場合、この時右のロボットには影響を及ぼさないから\(dp[i][0] = dp[i+1][0]+dp[i+1][1]\)である。
i番目のロボットを起動した場合を考える。
他のロボットに接触しない場合は\(dp[i][1] = dp[i][0]\) でよい。
他のロボットに接触する場合、影響を及ぼして起動される最も番号が大きいロボットをhとすると、iからhまでのロボットも全て起動されるから、この間のロボットは無視して良い。よってhを起動したときのhより右の組み合わせ総数に等しくなるので、\(dp[i][1] = dp[h][1]\) としてよい。
hを効率よく求めるために、segtreeを使う。
segtree[i]を、「i番目のロボットを起動したときに、連鎖して起動される最も右のロボットの番号」としてdpと一緒に更新していく。
i番目の要素を更新するには、まずi番目のロボットが直接触れるロボットの右端を二分探索で求めて、その間のsegtree[i]の最大値をとればよい。
最終的な答えは\(dp[0][0]+dp[0][1]\)となる。
提出
https://atcoder.jp/contests/abc158/submissions/10622750
感想
色んな要素が出てきて面白かった。
