AtCoder Beginner Contest 319

　Eまで五完。黄色に戻れず悲しい。

　Gは大量ペナを出したが22:40ちょうどに通った。あと一秒早ければ黄色に戻れたのに……。

コンテストへのリンク

F - Fighter Takahashi 

　bit DPだという解法ツイートを（たまたま）見てAC。

　bit DPだと分かれば特に難しいところはない。ただ、実装は大変。

G - Counting Shortest Paths

　コンテスト中考えていた（そして、22:40ちょうどにACした）解法は嘘解法だと思ったが、改めて考えるとそうでもないのかも？

　Nが小さい場合は普通にやらうとして、Nが大きい場合。

　startとgoalからBFSしていくと、それぞれstartからi歩でいける頂点Q、goalからj歩でいける頂点Q2が得られる。len(Q)*len(Q2)がMより大きいとき、必ずそこは一歩でいけるので、len(Q)*len(Q2)から、「Q中の頂点からQ2中の頂点へ辺が引かれているもの」を引けば良い。

　これで上手くいかないのは、ちゃんとDPしなくてはいけない場合、つまり、ある頂点を通る最短経路が二つ以上存在する場合だけれど、そういうのはNが小さい場合でないと起こらないんじゃないだろうか？

　ちゃんと考えるとよく分からなくなってきた。やはり正しい解法で解きましょう。