問題概要

マス $1, 2, \dots, N$ からなる双六が与えられる。マス 1 がスタート、マス $N$ 以上がゴールである。

$M$ 回サイコロを振って、 $j$ 回目には目 $D_{j}$ だけ出て、その分だけ進む。

双六のマス $i$ には「 $X_{i}$ マス進む」( $X_{i} \lt 0$ のこともある) という指示が書いてあり、サイコロを振ってそのマスに到達したら、その指示に従う。

ゴールまでにサイコロを振る回数を求めよ。

制約

$N, M \le 1000$

解法

現在いるマス pl を更新しながらシミュレーションしていけばよい。 $i$ 回目のサイコロ振りは次のように実装できる。

$i$ 回目のサイコロの目が dice[i] であるとき、pl += dice[i] と更新する
もし pl >= N ならば、反復を終了する
双六の目 pl の指示が move[pl] であるとき、pl += move[pl] と更新する
もし pl >= N ならば、反復を終了する

あとは、この反復を実装すればよい。

コード

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

int main() {
    int N, M, pl = 1;
    cin >> N >> M;
    vector<int> move(N+1), dice(M);
    for (int i = 1; i <= N; i++) cin >> move[i];
    for (int i = 0; i < M; i++) cin >> dice[i];

    for (int iter = 0; iter < M; iter++) {
        pl += dice[iter];
        if (pl >= N) {
            cout << iter+1 << endl;
            return 0;
        }
        pl += move[pl];
        if (pl >= N) {
            cout << iter+1 << endl;
            return 0;
        }
    }
}