ABC061 D - Score Attack

問題
提出コード1
提出コード2
提出コード1は愚直にメモ化再帰をしたものです。実装に2時間以上かかっているのでお話にならないです…
提出コード2は解説PDFと同じものになります。ベルマンフォード法を使ったことがなかったので実装しました。

解法

提出コード1は、dp[i] = i番目の頂点からNにいくために得ることができる得点の最大値、としてメモ化再帰を行います。閉路を見つける部分が特にとてもバグらせやすいので、想定解を使用するべきです。
提出コード2は、ベルマンフォード法になります。
辺のコストをすべて-1倍、すなわち正負反転させると、これは最短経路を求める問題と同じになります。最後にまた-1をかけてあげれば答えになります。
負の閉路が含まれるので、ダイクストラ法を使うことができないため、ベルマンフォード法を適用します。これによりで解くことができます。ベルマンフォード法は、すごく簡単に言うと、全ての辺について見ていき、スタート地点から辺の始点までの最短距離と辺のコストを利用して、スタート地点から辺の終点までの最短距離を更新していく、というものです。全ての辺をみても更新がされなかった場合終了になります。
閉路判定は、更新がN回目も行われた場合、存在することになります。

さて、この問題にはコーナーケースがあります。負の閉路を利用したときに、Nまでたどり着くことができないパターンです。
提出コード1では、負の閉路を見つけた際に、そこからNまでたどり着くことができるかを幅優先探索で調べることで解決しました。これまた実装が後者より重いです。
提出コード2では、N回目の更新がN番目の頂点で起こった場合はその負の閉路を利用できる、と判定するだけでよいです。