経理のAI仕訳帳

AtCoder公開

AIで解説 AtCoder攻略　シミュレーション

読了 約9分 たびすけ
AtCoder攻略のシミュレーションを状態更新の時系列で説明する図

シミュレーションページの位置づけ

項目内容
必修度必修
学習目安入門〜標準
前提入力・条件分岐・ループ
対象問題92問（推定値あり89問、未算出3問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安difficulty推定値問題数
入門difficulty < 044
標準0〜79929
標準〜発展800〜11997
発展1200以上9
未算出—3

操作を一つずつ実行するだけの問題でも、更新の順番を一つ間違えると別の状態になります。制約が小さいときは、複雑なアルゴリズムを探す前に、問題文の操作をそのままコードへ写します。

状態を変数へ分解する

シミュレーションでは、次の操作に必要な情報だけを状態として持ちます。盤面なら現在位置と向き、在庫なら残量、時刻表なら現在時刻と次のイベントです。状態を一つの大きな文字列へ詰め込むより、更新する値を列挙した方が境界を確認しやすくなります。

操作を一回ずつ書く

操作の入力を読み、条件を判定し、状態を更新し、必要なら答えを記録します。この順番をループの中で固定すると、入力を先読みしたり、更新を二重に適用したりする事故を避けられます。

position = 0
score = 0

for command in commands:
    if command == 'L':
        position -= 1
    elif command == 'R':
        position += 1
    if 0 <= position < N:
        score += values[position]

この例では、移動後の位置を採点しています。移動前を採点する問題なら、条件判定の位置を入れ替えます。

更新順序を表にする

複数の値が同時に変わる操作は、変数を直接上書きしない方が安全です。古い値を使う更新と、新しい値を使う更新を分けます。

操作先に読む値更新後に使う値
移動してから判定現在位置移動後の位置
体力を減らしてから回復現在体力減少後の体力
キューから取り出して追加取り出した要素追加後のキュー

同じ時刻のイベントを処理する問題では、イベントの順番が入力に明記されているか確認します。順番が決まっていなければ、先に全イベントを並べ替える必要があります。

グリッドを歩く

上下左右の移動は、方向ベクトルを配列へまとめます。境界外と障害物を同じ判定で弾くと、分岐が増えません。

directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
for dr, dc in directions:
    next_row = row + dr
    next_col = col + dc
    if not (0 <= next_row < H and 0 <= next_col < W):
        continue
    if grid[next_row][next_col] == '#':
        continue
    row, col = next_row, next_col

訪問済みのマスを再び歩けるかどうかで、単純シミュレーションとBFSが分かれます。同じ状態へ戻る可能性があるなら、訪問済み集合や周期検出が必要です。

シミュレーションを別のアルゴリズムへ切り替える境界

操作回数がN回程度なら、O(N)の直接実装で十分です。しかし、時刻が大きい、同じ操作が繰り返される、最短距離を求める、といった条件が入ると別の道具が必要になります。

シミュレーションで状態を更新するでつまずきやすい境界

  • ループ回数と時刻の意味を区別する。
  • 更新前の値を使う条件を、更新後に上書きしない。
  • 端点に到達した直後に停止するか、次の操作を試すかを決める。
  • 状態を初期化し忘れない。テストケースごとに新しい状態を作る。

シミュレーションで状態を更新するで先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

シミュレーションで状態を更新するの練習問題

最初は、操作回数がそのまま制約に収まる問題を選びます。その後、周期やグリッドの境界を含む問題へ進みます。

まず解く

問題公式解説出題意図difficulty
ABC281 A Count Down公式解説Print N down to zero, one value per line.-1303
ABC294 A Filter公式解説偶数だけを順番どおりに抽出して出力する。-1166
ABC391 A Lucky Direction公式解説Map each compass direction to its opposite and print the result.-1092
ABC429 A Too Many Requests公式解説公式Editorialの方針を request rate simulation として整理する。-1091
ABC412 A Task Failed Successfully公式解説公式Editorialの方針を task failure simulation として整理する。-1084

次に解く

問題公式解説出題意図difficulty
ABC431 A Robot Balance公式解説公式Editorialの方針を robot balance simulation として整理する。-1080
ABC284 A Sequence of Strings公式解説Print the N input strings in reverse order.-1072
ABC469 A Train Car公式解説Move the train car and output its resulting label.-1026
ABC293 A Swap Odd and Even公式解説文字列の奇数位置と偶数位置をペアごとに交換する。-998
ABC206 B Savings公式解説Add successive daily savings until the cumulative amount reaches S.-946

挑戦問題

問題公式解説出題意図difficulty
ABC450 A 3,2,1,GO公式解説Simulate the 3,2,1,GO sequence and print the final state.-929
ABC460 A Mod While Positive公式解説Repeatedly apply modulo while the value remains positive.-914
ABC278 A Shift公式解説Drop the first K elements and append K zeros to the sequence.-872
ABC356 A Subsegment Reverse公式解説Official editorial intent is classified as reverse subsegment.-842
ABC401 B Unauthorized公式解説公式Editorialの方針を login state simulation として整理する。-807

解けなかった問題では、最終状態だけでなく、操作一回後の状態を紙に書きます。一回の更新が正しければ、同じ処理を繰り返す部分は機械的に検証できます。

シミュレーションの次に読むページ

BFS・Dijkstraで最短距離を求める、スタックとキューで順序を処理する、累積和で区間と差を数える

関連記事