Codeforces Round #829 (Div. 1)

　Cまで三完。Dは解法はあっていたけど制限時間が厳しく通せなかった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #829 (Div. 1) DのTLEが取れない！
A 隣りにある1とｰ1で0を作る。
B xはx+1個欲しい
C 最初の（0の個数）個に1が何個あるか。一個ずつ期待値を計算してその和
D 空きマスからダイクストラしてTLE。PyPyで通している人がいたので高速化に走ったがダメだった。解法がまずい？

— titia (@titia_til) October 23, 2022

D. The Beach

　自力AC。

　ツイートした通りで、空きマスから適切にダイクストラをすれば良い。

　コンテスト後、Rustで通したが、書くのに30分以上かかっている。もう少し速く書けるようになりたいね。PyPyで通している人はいるけど、ちょっと技巧的な気もするし、それでもギリギリなので、他言語への書き換えが素早くできると良かった。

　このコンテストは、based on Moscow Team Olympiadということなので、PyPyじゃ制限が厳しい問題が出題される可能性は高いと思っていた。この問題は制約を見ればPyPyでは厳しそうと分かる。Rustで時間内に書き切る自信があればRustで書こうとしたはずなので、もうちょっと慣れて、速く書けるようになりたい。