Codeforces Round #800 (Div. 1)

　Cまで三完と思いきや、Cがシステムテストで落ちて二完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #800 (Div. 1) pretestはCまで。
A 累積和を取ったとき途中で0以下になっちゃダメ。また、sum(A)=0
B 木DP
C ゴールからダイクストラ。遷移は二つ。その道以外全部ブロックするか、どの道を進んだとしても最低x歩で行ける、か。
E 小さい数字からセグ木でやるのかと思ったがWA。

— titia (@titia_til) June 16, 2022

C. Keshi in Search of AmShZ

　自力AC。

　解法ツイートで「どの道を進んだとしても最低x歩で行ける」と書いたけどこれじゃ考察不足。ダイクストラで今までに見た辺の行き先は、今見ている辺の行き先よりDPの値が小さい（もしくは同じ）なのだから、ブロックしなくてもOK。それ以外を除外したときに、歩数が小さくなるかどうか考えればOK。

　これは、コンテスト中も頭をよぎったのだけど、なぜか必要ない気がして考えずに提出してしまった。pretestでWAが出てたら気付けてACできた気がするので悔しい～。