[yukicoder] No. 1242 高橋君とすごろく
問題
方針
後ろから考える
マス \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません