双六 (Sugoroku) [IOI/JOI 第17回日本情報オリンピック 予選 B]

https://atcoder.jp/contests/joi2018yo/tasks/joi2018_yo_b

解法

https://atcoder.jp/contests/joi2018yo/submissions/8137027
サイコロの面を小さい方から全て試してみて、クリア可能になったらそれを返す。
サイコロの面がd個であるとすると、ゴールから幅優先探索で到達可能性を判定すればいい。

int N, A[105];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N + 1) cin >> A[i];

    rep(d, 1, 102) {
        vector<int> vis(N + 2, 0);
        queue<int> que;
        que.push(N + 1);
        while (!que.empty()) {
            int q = que.front(); que.pop();

            if (q == 0) {
                printf("%d\n", d);
                return;
            }

            if (vis[q]) continue;
            vis[q] = 1;

            rep(i, 1, d + 1) {
                int nx = q - i;
                if (nx < 0) continue;
                if (vis[nx]) continue;
                if (A[nx]) continue;
                que.push(nx);
            }
        }
    }
}