問題ページ 考えたこと i回目までに両方ある/白しかない/黒しかない確率をそれぞれ求めたい これがわかればi回目の答えは (両方ある確率)/2 + (黒しかない確率) になるので解ける 黒しかないを知るには黒がj個あるがわかるとよさそう dp[i番目][黒がj個] = …

問題ページ 考えたこと sの順列でX%s_1%s_2%s_3…を求める 制約を見るとDPをしてくださいと言っている dp[i番目][modがj]みたいなの 挿入DP？みたいな感じになりそうだけど遷移がやばそう ここでmodの性質を思い出すとmod xをしたあとにmod y(y >= x)をしても…

問題ページ 考えたこと i番目にいた人が消える条件は何か？で考えるけどまともな形にならない 方針転換して二分探索をすることにする 消える人数を固定したところで何も嬉しくない i番目が左に消えるときi-1番目も左に消えることに気がつく 単調性があるので…