https://codeforces.com/contest/1674
E. Breaking the Wall
難しいのは隣り合う2つの壁を壊すパターンだと思うが、3分探索で提出したらACした。
正当性があるのかはすこし疑問があるが参考まで。
片方の2で割る回数を、整数の3分探索で調べて、合計手数のminを求める。
調べる数を右左両方を試した。
停止しないのでループ回数を固定する。
G. Remove Directed Edges
トポロジカルソートして使う辺をDPで試す。
ある頂点Pにたどり着くときのスコアは、頂点Pに入ってくる辺のうちスコアの最大値+1になる。(+1は頂点Pが一つ足されるスコア)。
ただし、頂点Pに入ってくる辺が出てくる側の頂点Qについて、頂点Qの出自数が1の場合、この辺は使えないので除外する必要がある。
グラフを作るときに辺を逆にしたグラフを作っておいて、頂点Pに入ってくる辺の出発点の頂点Qを求められるようにした。