C++の練習を兼ねて, AtCoder Regular Contest 105 の 問題D (Let’s Play Nim) を解いてみた.
■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参考に実装したところ, 何とかAC版に到達できた.
2. Nim の 復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 105 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題D/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 |
// 解き直し. // https://atcoder.jp/contests/arc105/editorial/171 // C++(GCC 9.2.1) #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--) #define a first #define b second int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. 各テストケースを確認. rep(i, T){ // 2-1. テストパターン. int N; scanf("%d", &N); LL a; map<LL, int> m; rep(j, N){ scanf("%lld", &a); m[a]++; } // 2-2. N が 奇数. if(N & 1) puts("Second"); // 2-3. N が 偶数. if(!(N & 1)){ // 任意の整数 n について n 個のコインが入った袋の偶奇をチェック. LL e = 0; for(auto &p : m) if(!(p.b & 1)) e++; // 任意の整数 n について n 個のコインが入った袋が偶数個ある場合(後手必勝). if(m.size() == e) puts("Second"); // それ以外. if(m.size() != e) puts("First"); } } 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 |
[入力例] 3 1 10 2 1 2 21 476523737 103976339 266993 706803678 802362985 892644371 953855359 196462821 817301757 409460796 773943961 488763959 405483423 616934516 710762957 239829390 55474813 818352359 312280585 185800870 255245162 [出力例] Second First Second ※AtCoderのテストケースより [入力例] 5 3 1 2 3 6 3 3 5 5 7 7 4 1 1 1 5 10 11 11 11 11 12 12 12 23 23 23 16 1 2 3 4 5 6 1 2 3 4 5 6 7 7 7 7 [出力例] Second Second First First Second |
■参照サイト
AtCoder Regular Contest 105