JOI 予選 2010 B - すごろく (AOJ 0544) (6Q, 難易度 3)

すごろくを題材にした問題。すごろくの各マスには「oo マス進む」などの指示がある。これを上手に管理しよう。

• 問題へのリンク

問題概要

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

回サイコロを振って、 回目には目 だけ出て、その分だけ進む。

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

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

制約

• 

解法

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

---

• 回目のサイコロの目が 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;
        }
    }
}