A,B問題はやるだけといった感じだった。C問題はとても典型的なdpだったが、最近になってこの手の問題がCに置かれていることに驚いた。典型９０と全くおなじ問題だったらしく、そのせいか茶diffであった。そろそろ典型９０にも触れた方よさそう。
D問題はグラフの最短距離の経路を数えるというものだった。BFSで頂点１からそれぞれの辺の最短距離を調べて、そのあと１からはじめて、次の数字のつながっているところに経路数を足していくという方法をとった。計算量について、一つの辺を見るのは高々２回だからO(M）で済むだろうと思った。ここまででおよそ３０分かかっていた。
E問題について、制約がとても小さいので何でもできるなと思った。前に解いたHanjoというdfs全探索をする問題とよく似ているなと思い、同じようにできないかといろいろ考えたが、一つの形を１回のタイミングだけで検出する方法がなかなか思いつけずに終わってしまった。
終了後すぐに、端から順番に赤を初めて置いていって、おったらそこをtrueにすればよいと気づいた。線ではなく面のような形のものも、例えば右をまず赤にして探索した後、その右をtrueにして次左を探索、というふうにすればよかった。終了後すぐに気付いて泣いた。
