問題ページ 考えたこと 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番目も左に消えることに気がつく 単調性があるので…

問題ページ 考えたこと gcd=gと決め打つと長さの期待値が割と簡単に求まる気がする 長さnの確率は (gの倍数の確率)^(n-1) * (gの倍数以外の確率) っぽい g=2,3 の両方で 6, 6, 6, 6,…, 1みたいなのを重複して数えてる 約数系包除で数えられそう 期待値をちゃ…