E - Shiritori 3しりとりのルールから，最初の3文字と最後の3文字が重要になる．それらを頂点として，高橋辞書に登録された文字列を辺とみたグラフを考える． ゲーム理論の問題では，・ルールに従った移動を辺で表して，現在の局面を頂点で表す・勝敗が決ま…

E - Sugoroku 4 確率dp. を と書く． に対して， とする． for を回すとき，移動した回数 を一番外側に持ってくることに注意． dp では，すでに正しく求まっている計算を利用して次を求めるため． 回目を求めるには， 回目が正しく求まっている必要がある． …

F - Erase Subarrays 残す場所をo, 消す場所をx と考えて，ox 列を作る． 連続する x のブロックの個数を数えるが，それは ox が連続している場所の個数と一致． ただし，形式的にの前にo があるものと考える． としてdp. typedef long long ll; const ll IN…

D - Equal Cut 4つに分割する，つまり境目は3か所． 3つの場合は，真ん中を全探索して残りを高速に求めるケースが多く，今回もそれ． 分割する場所を左から l, i, r とおいて，i を全探索． 2分探索で，残りの2か所を求める． ・なるべく均等に分割するのが…

D - Built? 余分に辺を追加する必要はないから，最小全域木を求めればよい． このままだと辺の本数がO(N^2)であるから，辺を減らすことを考える． 隣同士の辺しか使う必要がないため，辺の本数がO(N)となって間に合う． 実装は，tupleを用いて <x,y,index> , <y,x,index> を lex or</y,x,index></x,y,index>…

ABC282D atcoder.jp DFSで連結成分ごとに計算する． 与えられたグラフに対して，すべての連結成分が2部グラフになっている必要がある．なぜなら，辺を追加して2部グラフなら，追加する前に2部グラフになっている必要があるため． DFSにより，2部グラフか判定…