はてなの使い方の練習
考えたこと
- 初期位置や速度が同じ人がいないので、開始時点の順序と終了時点の順序が決まる (以後開始時点の座標でソートしてあたらしい順序にする)
- 順列の上と下を同じ数字どうし結ぶと、その交点で2人がぶつかる
- 高橋君\(i\)を青木君にしたとき、どこまでの高橋君が青木君になるか?
\(i\)番目の高橋君を変更したとき、「初期位置が\(i\)より後ろで、最終的な位置が最大のもの」と「初期位置が\(i\)より前で、最終的な位置が最小のもの」を求めると、最終的な位置がその間の高橋は全員青木になることがわかる (理由 : その2人は青木に必ずなる。それ以外の場合、その人に関する線分は必ず青木に必ずなる線分と交差する)
この問題はセグ木なり累積minなりで解くことができ、結局「\(N\)個の区間を用いて全体を被覆する方法は何通りか?」という問題に帰着できる
あとは区間を終点ソートして\(dp[i]=被覆されていない最後のマスが i である通り数\)というDPをセグ木上で行えば解ける
感想
4時間くらいかけて丁寧に整理したら解けた。
