AtCoder Beginner Contest 175 D-Moving Piece
AtCoder Beginner Contest 175 (ABC 175) D - Moving Piece についての記事です．
問題へのリンク
解法
$i \to P[i]$ にリンクがある有向グラフだと思って，連結成分 (といってもサイクルだが) ごとに考える．
ループを回ってプラスのときに，端の部分をどこにとるか... とか考えていくと，ループをまわる回数が 長さ / K だけとれるとかとれないとか-1するとか複雑なコードになってバグる．(いや，それでもバグらないように書けないといけないという話はあるけれども．) Niuezさんのツイート で教えられたのだが，iとjを固定して， iからjまでのパスのスコアの最大値を考えることにすれば簡明になる．
- 直接行く
- 直接行った後に，ループを回れるだけまわる．
の2つのうちの大きい方を取れば良い．直接行くコストは，あらかじめ累積和を2周分作っておいて，引けば良い．
