C. Valeriy and Deque

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;