Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2)

　Cまで三完。DとEはできなくてはいけない問題だったよう。

コンテストへのリンク

コンテスト後のツイート

D mod degでダイクストラを書いたけどWA。
E 右上と左下の組を考えればDPできると思ったがRE。

— titia (@titia_til) July 19, 2025

E. Greedy Grid Counting

　コンテスト中書いていた方針でAC。

　実装ミスがあったためデバッグは結構大変だったけど、コンテスト中考えていたことは正しかった。

　右上と左下のマスをペアで見ると、「左回りルートが右回りルートをいくつ上回っているか？」（これが0未満になるとダメ）が分かり、この値を持ってDPできる。

　この値は高々kなので、計算量はn*k*kで収まる。

　累積和を使えば計算量がn*kに落とせるはず……などと考えたのが時間を食った原因か（実際落とせるはず）。ただ、そのときは状態数がkより大きくなる（n*kになるのでは？）と思っていたから考えてしまったのだけど。