けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 予選 2019 B - すごろくと駒 (AOJ 0653) (6Q, 難易度 2)

JOI JOI難易度2 JOI予選・二次予選 AtCoder AOJ NoviSteps6Q シミュレーション すごろく 駒(コマ)や石やコインを扱う問題 一次元グリッド 愚直シミュレーション

シミュレーションを冷静に実装しよう！

問題概要

マス 1, 2, \dots, 2019 があって、マス 1 はスタート、マス 2019 はゴールである。 N 個のコマがあり、それぞれ X_{1}, X_{2}, \dots, X_{N} 番目にマスに置かれている。

次の M 回の操作を実行する。

  • i 回目の操作ではコマ A_{i} を動かそうとする
  • もしコマ A_{i} の置いてあるマスがゴールマスでない、かつ、その右隣のマスにコマが置かれていないならば、コマ A_{i} を右隣のマスに動かす

操作の実行後の N 個のマスの置かれた番号を答えよ。

制約

  • 1 \le N, M \le 100
  • 1 \le X_{1} \lt X_{2} \lt \dots \lt X_{N} \le 2019

考えたこと

問題文で書かれた通りにシミュレーションしましょう。ただし、一つ問題になるのは、次の点でしょう。

コマ A を右隣に動かす操作が OK かどうかを判定する

まず、コマ A がすでにゴールしているとき（ X_{A} = 2019 のとき）は動かせません。以降、コマ A はゴールしていない場合を考察します。

さて、コマの位置 X_{1}, X_{2}, \dots, X_{N} について、どれだけ操作をしても

X_{1} \lt X_{2} \lt \dots \lt X_{N}

という関係性が保たれることに注意しましょう。よって、コマ A の右側にあるコマは A+1 です。つまり、コマ A が動きたい先のマスにいる可能性のあるコマは A+1 のみです。このことに注意して、次のように整理できます。

  • X_{A+1} = X_{A} + 1 のとき：コマ A の移動先にコマ A+1 があるので、コマ A は動けない
  • X_{A+1} \gt X_{A} + 1 のとき：コマ A の移動先にはコマがないので、コマ A は動ける

これらのことに注意してシミュレーションしましょう。次のように実装できます。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M, A;
    cin >> N;
    vector<int> X(N);
    for (int i = 0; i < N; i++) cin >> X[i];

    X.push_back(2020);  // 番兵
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> A, A--;
        if (X[A+1] <= X[A] + 1) continue;
        X[A]++;
    }
    for (int i = 0; i < N; ++i) cout << X[i] << endl;
}