シミュレーション

概要

問題にある操作や出来事を、それが起こる順番通りに再現すること。
「今の状態」を変数として記録しておき、何かが $1$ つ起こるたびにその状態を書き換えていく。

状態としてどういう情報をどういう形で持つかを考えるのが重要となる。

コード例

左右1列に並んだマスの上を動かす

例えば、文字列 s が移動命令の順番を表しているとする。
文字 L なら左、R なら右に $1$ マス動く。
例えば "LLRLR" であれば、左に移動、左に移動、右に移動、左に移動、右に移動、という意味である。

この場合、現在位置の情報を x として持ち、文字を前から順に見ながら更新すればよい。
命令を $1$ つ確認するごとに、この x の値を更新していくことになる。

string s;
cin >> s;

int x = 0;

for (char c : s) {
  if (c == 'L') x--;
  else if (c == 'R') x++;
  // 必要ならここにさらに書く
}

あとは、問題に合わせた処理を書き足せばよい。
「最も右に行った記録は？」であれば、移動後に現在地が最も右に行った記録を更新しているか確認する。
「一番多く踏んだマスは？」であれば、各マスを踏んだ回数に今踏んだ分の情報を反映する。

使い方の応用

状態の持ち方を工夫する

シミュレーションでは、今の状態をどのようなデータで持つかが重要である。
持ち方により、更新の簡単さや計算量が大きく変わるからである。

例えば、縦横 $1000$ マスのグリッド上に $1000$ 個のコマを置く問題を考える。

全マスにコマがあるかないかを保管すると、$1000000$ マス分の情報を持つことになる。
ここで「全てのコマを $1$ つ右に動かす」場合、$1000000$ マス全て、コマがある確認する必要がある。
しかも、移動時には自身の右に別のコマがあった場合のデータ衝突にも気をつけなければならない。

一方で、全コマの位置情報（行と列）を記録してあれば、コマの個数 $\times 2 = 2000$ 個の情報だけでよい。
「全てのコマを $1$ つ右に動かす」ときも、列番号の情報 $1000$ 個だけ処理すればよく、高速に処理できる。

だが、「指定位置にコマがあるか調べる」の場合は関係が逆転する。
前者の場合はデータを $1$ つ見るだけで済むが、後者は $1000$ 個のコマ全てを確認する必要がある。

このように、同じような状況でも、操作内容や得たい情報によってデータをどう持つべきかが変わる。
愚直に書いて間に合う問題もあるが、それでダメそうな場合にはデータの持ち方を工夫すること。

イベントソート

時刻が絡む問題では、ソートを利用して、時刻順に整理して解くこともある。
シミュレーション中に追加イベントが入る可能性があれば、priority_queue を用いる場合もある。

例えば、「時刻 $2$ から $5$ まで客 X がいる」という情報があったとしよう。
この場合、時刻 $2$ に「客 X が来る」、時刻 $6$ に「客 X が帰る」というイベントを登録する。
（問題内容によっては、時刻 $5$ に「客 X が帰る」の方が適切かもしれない）
そうしてから、時刻が早い順に出来事を処理すると、シミュレーションしやすくなる。

また、実際に時刻が関係なくても、疑似的に時刻を持たせてイベントソートにすることがある。
例えば、「マス $2$ から $5$ までこうする」みたいな状況があったとしよう。
これを、$i$ 秒目に左から $i$ マス目を調べると考えると、「時刻 $2$ から $5$ までこうする」話にできる。

大量の操作をまとめて処理する

同様の操作内容が繰り返される場合、$1$ 周分をまとめて処理することで高速化できることがある。
例えば、$100$ マスで $1$ 周するすごろくを $12345$ マス進むのを、$123$ 周 $+45$ マスとして処理できる。
C問題レベル。
詳しくは「周期性」の記事参照。

また、現在の状況のみで次の状態が決まるシミュレーションでは、ダブリングを利用できる。
各状況から、$1$ 回後の状況、$2$ 回後の状況、$4$ 回後の状況、$8$ 回後の状況、などを事前に作っておく。
$13$ 回後の状況を知りたい場合に、今から $1$ 回後の状況の $4$ 回後の状況の $8$ 回後の状況を答えればよい。
E問題レベル。
詳しくは「ダブリング」の記事参照。

注意点

計算量に注意する

問題文通りに $1$ 回ずつ操作すればよいとは限らない。
$Q$ 回の操作それぞれで $N$ 個のデータを全て見ると、計算量は $O(NQ)$ になる。
$N$ と $Q$ がどちらも $2 \times 10^5$ 程度なら、$O(NQ)$ は間に合わない。

計算量的に間に合うデータの持ち方を選ぶこと。

同時更新の処理に注意

位置 A の情報が位置 B に影響を与え、同時に位置 B の情報が位置 A に影響を与えることがある。
この場合、位置 A の新しい情報が分かった時点で更新してしまうと、位置 B の更新時に困る。
next というデータに情報を作って、全部作り終わったら swap でまとめて更新するなどしたい。

添字や境界に注意する

グリッド移動や配列操作では、端の扱いでミスしやすい。

例えば、次のような点を確認する。

グリッドの外に出る可能性があるか
問題文の位置が 1-indexed か、コード上で 0-indexed に直す必要があるか
先頭や末尾の要素を特別扱いする必要があるか
データが空になる可能性があるか

コーナーケースが発生しやすいので、自作テストで確認すること。