ABC294E シュミレーションを実装する問題．上下のマスが一致してるか判定しないといけない箇所は， 高々\(N_{0} + N_{1}\) 個のみ．実装上下それぞれについて，run length の情報を deque に入れておく． 取り出して，min(上下の長さ) だけ，今調べている長…

ABC295E ソートはしないで個数を数える． \(1\) から \(m\) を動く確率変数 \(x\) に対して，\(x\) の期待値は \begin{align} e_{x} & = & \sum_{i = 1}^{m} \ i \cdot p_{x = i} \\ & = & \sum_{i = 1}^{m} \ p_{x \geq i}. \end{align} \(p_{x \geq i}\) …

ABC296E 言い換えfunctional グラフが与えられる． 連結成分毎の サイクルの長さの和を求めよ．実装DFS する． 各頂点に対して，3つの状態がある． 0: 訪れてない 1: 訪れたが，まだ遷移の途中の点． 2: 訪れて，遷移が全て終わった点 気持ちとしては， 1 が…

ABC297E 小さいほうから順に構成していく． \(x\) 円が作れるとき，どの様な作り方かは無関係に \(x + a[i]\) 円が作れる． 作れる値全体を保管する set を用意すればよい．実装今調べている場所をiterator で持っておいてもよいし， 調べ終わったら set か…

ABC298E 確率DP. ゲームの終端から決めていく.実装1再帰で奥の方から決めていく． 決まった場所は答えをメモしておくことで，同じ計算を省略できる． 再帰なら，仮にゲームの遷移が複雑な場合でも可能． 実装2for でも実装できる．今居る座標を\(x\)とおけば…