Quiz
https://codeforces.com/contest/1180/problem/C
AC Code
https://codeforces.com/contest/1180/submission/55893151
観察
- シミュレーションしてみる
- 一番大きい値が左端に来た後は、居座る
- その後は、左端以外で周期的になる
- a, mの範囲が広いので周期性を使って途中のシミュレーションをスキップするのだな、と思う
解法
- 2n回シミュレートすればすべての状態は列挙したことになる
- 前半のn回:最大値を左端に動かす
- 後半のn回:周期に入った状態をすべて列挙する
注意点
- n-1周期でループするからといって、n-1の剰余を取ると「戻りすぎてしまう」
- 戻りすぎてしまうと、まだループに入っていない可能性がある
- n-1で剰余を取ったあとにn-1を足せばよい
m %= N-1; // これだけでは戻りすぎ m += N-1;