[yukicoder] No. 1242 高橋君とすごろく

2020年10月4日2020年12月12日

問題

方針

後ろから考える

マス \( x \) にいるとき、ゲームオーバーマスのマスペアが \(( x + 1, x + 6) \) または \( (x + 2, x + 5) \) または \( ( x + 3, x + 4) \) に存在するとき、ゲームオーバーになるので、マス \( x \) もまたゲームオーバーマスとなります。

マス \( x + 1, x + 6 \) にゲームオーバーマスがあるとき

このとき、マス \(x + 6, x + 1, x \) とゲームオーバーマスがあることになるので、

\[ x + 6, x + 1, x, x – 3, x – 5, x – 6, x – 8, x -9, x-10, x – 11, x – 12, \cdots \]

とゲームオーバーマスが存在することになります。

マス \( x + 2, x + 5 \) にゲームオーバーマスがあるとき

このとき、マス \(x + 5, x + 2, x \) とゲームオーバーマスがあることになるので、

\[ x + 5, x + 2, x, x – 1, x – 3, x – 4, x – 6, x -7, x-8, x – 9, x – 10, x – 11, x – 12\cdots \]

と地雷が存在することになります。

マス \( x + 3, x + 4 \) にゲームオーバーマスがあるとき

このとき、マス \(x + 4, x + 3, x \) とゲームオーバーマスがあることになるので、

\[ x + 4, x + 3, x, x – 2, x – 3, x – 5, x – 6, x -7, x-8, x – 9, x – 10, x – 11, x -12, \cdots \]

と地雷が存在することになります。

マス \( x \) にゲームオーバーマスがあるとき

このとき、マス \( x + 1, x + 3, x + 5 \) のいずれかにゲームオーバーマスがある場合、\( x – 9 \) 以降のマスが全てゲームオーバーマスとなります。したがって、\( A_i \geq 10 \) を満たす \( A_i \) に対して、

\[ A_i + 1 = A_j \vee A_i + 3 = A_j \vee  A_i + 5 = A_j\]

を満たす \( A_j \) が存在するとき、ゲームオーバーとなります。

また、マス \( 9 \) 以下のマスについてはゲームオーバーマスがマス \( 1 \) に出現するかをシミュレーションします。

コード

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

int main() {
    ll N;
    int K;
    cin >> N >> K;
    ll A[K];
    set<ll> s;
    for (int i = 0; i < K; i++) {
        cin >> A[i];
        s.insert(A[i]);
    }
    if (K == 1) {
        cout << "Yes\n";
        return 0;
    }
    for (int i = 0; i < K; i++) {
        if (A[i] >= 10) {
            if (s.count(A[i] + 5)) {
                cout << "No\n";
                return 0;
            }
            if (s.count(A[i] + 3)) {
                cout << "No\n";
                return 0;
            }
            if (s.count(A[i] + 1)) {
                cout << "No\n";
                return 0;
            } 
        }
    }
    for (int i = 20; i >= 2; i--) {
        if (s.count(i) == 0) continue;
        if (s.count(i + 5)) s.insert(i - 1);
        if (s.count(i + 3)) s.insert(i - 2);
        if (s.count(i + 1)) s.insert(i - 3);
    }
    if (s.count(1)) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
    }
    return 0;
}

参考