C++の練習を兼ねて, AtCoder Beginner Contest 172 の 問題F (Unfair Nim) を解いてみた.
■感想.
1. 解答方針が, 全く見えなかったので, 解説を参考に実装したところ 何とかAC版となった.
2. bit を 計算する時, 1 でなく, 1LL を 使うとか, S = a + b のチェックなど, 考慮事項も多く, いろいろ苦労したように思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 172 解説をご覧下さい.
■C++版プログラム(問題F／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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
// C++ (GCC 9.2.1) // 解き直し. // https://img.atcoder.jp/abc172/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) LL A[333]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &A[i]); // 2. 解説通り. // 2-1. S, X を 設定. LL S = A[0] + A[1], X = 0LL; repx(i, 2, N) X ^= A[i]; // 2-2. D を 設定. LL D = (S - X) / 2LL; // printf("S=%lld X=%lld D=%lld\n", S, X, D); // 2-3. D が 非負整数で無い, または, D と X の 共通ビットがある, // または, D が A[0] よりも大きい場合. if(D < 0LL || (D & X) != 0LL || D > A[0]){ puts("-1"); return 0; } // 2-4. Y を 設定. LL Y = 0LL, a = D; repr(i, 40, 0){ LL bit = 1LL << i; // printf("bit=%lld (X & bit)=%lld X=%lld Y=%lld (X + Y)=%lld\n", bit, (X & bit), X, Y, X + Y); if(X & bit){ LL c = D ^ (Y | bit); // printf("c=%lld\n", c); if(c <= A[0]) Y |= bit, X -= bit, a = D ^ Y; } } // 2-5. S = a + b が成立しているかのチェック. // -> n2_03 などへの対策. // ex. // 2 // 5 6 // -> S = 11, a + b = 10 の ように 差分が出る場合がある. LL b = D ^ X; // printf("a=%lld b=%lld (a + b)=%lld\n", a, b, a + b); if(S != a + b){ puts("-1"); return 0; } // 2-6. a < A[0] であるかのチェック. // -> sample_03 などへの対策. if(a == 0){ puts("-1"); return 0; } // 3. 出力. printf("%lld\n", A[0] - a); 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 |
[入力例] 2 5 3 [出力例] 1 ※AtCoderテストケースより [入力例] 2 3 5 [出力例] -1 ※AtCoderテストケースより [入力例] 3 1 1 2 [出力例] -1 ※AtCoderテストケースより [入力例] 8 10 9 8 7 6 5 4 3 [出力例] 3 ※AtCoderテストケースより [入力例] 3 4294967297 8589934593 12884901890 [出力例] 1 ※AtCoderテストケースより [入力例] 10 192 210 39 247 115 265 70 299 85 250 [出力例] 3 [入力例] 15 321 92 304 214 1 298 69 321 220 298 186 233 189 320 192 [出力例] 10 |
■参照サイト
AtCoder Beginner Contest 172