C++の練習を兼ねて, AtCoder Regular Contest 151 の 問題C (01 Game) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, Grundy数を復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 151 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
// 解き直し. // https://atcoder.jp/contests/arc151/editorial/5027 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; using vp = vector<P>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define a first #define b second int main(){ // 1. 入力情報. LL N; int M; scanf("%lld %d", &N, &M); vp v(M); rep(i, M) scanf("%lld %lld", &v[i].a, &v[i].b); // 2. Grundy数. // 2-1. どちらの端も数字と接していない. LL ans = 0; if(!M) ans ^= (N % 2); // 2-2. それ以外. if(M){ // 一方の端のみが数字と接している. if(v[0].a > 1) ans ^= (v[0].a - 1); if(v[M - 1].a < N) ans ^= (N - v[M - 1].a); rep(i, M - 1){ // 両端が異なる数字. if(v[i].b != v[i + 1].b) ans ^= 0; // 両端が同じ数字. if(v[i].b == v[i + 1].b) ans ^= 1; } } // 3. 出力. printf("%s\n", ans ? "Takahashi" : "Aoki"); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
[入力例] 7 2 2 0 4 1 [出力例] Takahashi ※AtCoderのテストケースより [入力例] 3 3 1 1 2 0 3 1 [出力例] Aoki ※AtCoderのテストケースより [入力例] 1000000000000000000 0 [出力例] Aoki ※AtCoderのテストケースより [入力例] 20 5 3 1 7 0 10 1 13 1 17 0 [出力例] Aoki [入力例] 30 10 1 1 5 1 9 0 12 0 15 1 20 1 22 0 23 1 28 1 30 0 [出力例] Aoki [入力例] 50 12 5 0 7 1 13 1 17 0 21 0 24 1 29 1 33 1 34 0 38 0 43 0 44 1 [出力例] Takahashi |
■参照サイト
AtCoder Regular Contest 151