■176F - Brave CHAIN
dp
O(n^3)は明らかにTLEする。一回の操作毎に更新する部分は高々しれているので
更新箇所だけメモしておいて、後で更新分だけ更新すれば良い。
xy+abc->???と遷移させる中で
xy+aaa->xy
aa+abc->bc
aa+abb->bb
bb+aab->aa
が+1されるケース。このあたりを丁寧に遷移させる。
■177F - I hate Shortest Path Problem
遅延セグ木
区間最小値と区間更新ができればいい
■178F - Contrast
絶対に無理な条件は一瞬でわかる、同じ要素の合計数がn+1以上あるケース
それ以外が全て構築できれば嬉しい。
実装的なことも考えるとrotateしてそれで成立すれば楽。
サンプルで考えると行けそうな気がする。
立式してして証明すると可能なのでそれが答え。
■179F - Simplified Reversi
縦横をそれぞれに見て
一点取得と区間更新ができれば良い
つまり遅延セグ木。
■180F - Unbranched
余事象 + dp
最大値がLは扱いにくいので
最大値がL以下から最大値がL-1以下を除けば良い.
また、すべての頂点の次数が2以下は、各連結成分はパスかサイクルのどちらか
dp[i][j]:=最大サイズの条件を満たした上でのi頂点j辺のグラフの個数。
注意するのは、まだ連結成分が定まっていない頂点の中で最も番号の小さい頂点を採用すること
こうしないと重複が発生する。
