トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

E tatyamさんのSortedSetをお借りしてシミュレーション。
F スタートとゴールから順に駒を動かしていく。(行きの燃料, 帰りに最低必要な燃料)におけるお金を持つDP。最小値でDPテーブルを更新すべきところをそのまま更新するミスをして1ペナ+20分。このミスがなければ130位くらいでした。悲しい。

— titia (@titia_til) September 16, 2023

G - Slot Strategy 2 (Hard)

　解説放送を見てAC。コンテスト中フローじゃないかとは思ったけど、二部マッチングに帰着できると気付いていなかったので何も惜しくなかった。

・各数字について考え、二分探索するとフロー（二部マッチング）になる。

・時刻の個数が問題だが、各リールについて高々N個だけ考えて良い。

　一つ目は思いつくべき内容で、それを思い付いていなかったのはいけない。二つ目は難しいが、計算量を落とそうと試行錯誤していれば思いつくかもしれない。

　なお、二分探索のNGをN-1と設定してWAをくらった。0秒後から始まるので、NG=N-2と設定しなくてはいけない。機械的にNG=-1とかしていれば問題ないが、下限を見積もろうとするとやってしまいやすいミスかと思う。