AtCoder Beginner Contest 175 D – Moving Piece を解いた記録
問題
\(1, 2, \dots, N\)の番号がついた\(N\)マスのマス目があり，マス\(i\)には整数\(C_i\)が書かれている．
また，\(1, 2, \dots, N\)の順列\(P_1, P_2, \dots, P_N\)がある．
次のゲームを行う．スコア0からスタートするとき，ゲーム終了時のスコアの最大値を求めよ．
- 好きなマスを選んでコマを置き，\(1\)回以上\(K\)回以下の任意の回数だけ次の操作を行う．
- コマがマス\(i\)にあるとき，\(P_i\)に移動させる．このとき，スコアに\(C_{P_i}\)が加算される．
制約
- \(2 \leq N \leq 5000\)
- \(1 \leq K \leq 10^9\)
- \(1 \leq P \leq N\)
- \(P_i \neq i\)
- \(-10^9 \leq C_i\leq 10^9\)
- 入力は全て整数
解法
各マスを始点とした場合について，移動回数を\(1\)から\(K\)まで変化させて愚直にスコアを計算したら明らかに間に合いません．
しかし，十分な回数だけ移動を繰り返したら（1周して）始点のマスに戻ってくるのも直感的に明らかだとおもいます．この性質をうまく利用したいですね．
入力例を見れば分かる通り，コマの移動経路は必ずしもただ1つの円というわけではありません．移動経路はこの図のようないくつかの閉路（サイクル）で構成されています．
どのマスにコマを置いたとしても，コマは常に始点のマスが属する閉路の上のみを移動します．よって，各閉路についてスコアの最大値を求めたあと，最大値の最大値を出力すればよいです．
あるマスが属する閉路を見つけたいときは，あるマスを始点とし，始点のマスに戻ってくるまで次のマスへの移動を繰り返せばよいです．
閉路が求まったあとは閉路を1周したときのスコアを計算しますが，これはやるだけですね．
次に，閉路上で始点と終点の組み合わせを全部試してスコアを計算しましょう．
マスの数\(N\)は\(2 \leq N \leq 5000\)ですから，計算量\(O(N^2)\)でも十分間に合います．
実際には移動回数の上限が\(K\)と閉路の長さのうち小さい方となる点には注意しましょう．
始点と終点の組み合わせを全部試すとき，まだ移動できる回数が残っていてなおかつ閉路を1周したときのスコアが正の場合は，残っている移動回数で閉路を回れるだけ回ってスコアを稼ぎます．
以上の計算を行えば，ある閉路についてのスコアの最大値が求まります．この操作を全ての閉路に対して行えば，答えにたどり着けるでしょう．
実装例
感想
AtCoder Beginner Contest175で，AtCoderでの私のコンテスト参加回数（ratedのみ）は50回に到達しました．
直近のコンテストではレートが若干溶かしましたが，ABC175では再びレーティングの最高値を更新できたので良かったです．