AtCoder Regular Contest #003

結果

ooo- 20th

A,B

やるだけ

C

あるセルにいるときのパラメータとして、「それまでの経路の明るさ」と「時間」があるが、
経路の明るさは移動するごとに変化しないor減少するため、時間については考えずにセルごとの
経路の明るさの最大値だけBFSでメモっておけばいいのでは、と考えた。(この辺結構怪しい)

ここでBFS、と思って実装しているが、後でSPFAというアルゴリズムであったらしいことが解った。。
(参考1)SPFAの紹介 - hogloid's memo
(参考2)Shortest Path Faster Algorithm - PEGWiki

ダイクストラとベルマンフォードの中間みたいな感じで、各ノードから到達できるノードへのコストが
改善(relaxって書いてあるのはこれだと理解しています)できる場合はqueueに積む。
既にqueueに積んである場合は積まなくてよいのだが、その部分は実装していなかった。
(ノード数が大きくないためそれでもよかったのではないかと思っている。)

到達可能な負閉路がある場合はこのアルゴリズムが止まらないので、停止しない。
これを利用して負閉路検出にも使えるようである。計算量はO(VE)でベルマンフォードと同じ。

D

10秒だし、と思ってO(nC2*n!*k)とか書いたらTLEした。ですよねー。
誤差が緩いのには気づいた(当たり前)ので適当にやればよかった。昨日のGCJから学んでいない…
あとなんとなくchokudaiさんらしいなーと思った。後で解く。