C++の練習を兼ねて, AtCoder Regular Contest 143 の 問題C (Piles of Pebbles) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで勝者を判定できる点が, 非常に興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 143 解説 の 各リンク を ご覧下さい.
■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 50 51 52 53 54 55 56 57 58 59 |
// 解き直し. // https://atcoder.jp/contests/arc143/editorial/4194 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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 all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, X, Y; scanf("%d %d %d", &N, &X, &Y); vi a(N); rep(i, N) scanf("%d", &a[i]); // 2. B の 計算. vi b(N); rep(i, N) b[i] = a[i] % (X + Y); // 3. sort. sort(all(b)); // 4. B[i] が, すべて X より小さい. if(b.back() < X){ puts("Second"); return 0; } // 5. X <= Y で, ある b[i] が X 以上. if(X <= Y){ if(b.back() >= X){ puts("First"); return 0; } } // 6. X > Y. // 6-1. 先手が, X個以上の山(一つ)から, X個取り除く. b.back() -= X; // 6-2. sort. sort(all(b)); // 6-3. B[i] が, すべて Y より小さい. if(b.back() < Y){ puts("First"); return 0; } // 6-4. ある b[i] が Y 以上. puts("Second"); 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 |
[入力例] 2 1 1 3 3 [出力例] First ※AtCoderのテストケースより [入力例] 2 1 2 3 3 [出力例] Second ※AtCoderのテストケースより [入力例] 3 1 2 2 5 6 [出力例] First [入力例] 5 5 3 19 20 21 22 23 [出力例] Second [入力例] 5 5 3 16 17 18 23 24 [出力例] First [入力例] 10 7 9 37 22 21 17 49 65 82 20 18 19 [出力例] Second [入力例] 20 12 13 25 36 25 13 13 29 21 17 37 27 27 24 34 21 24 22 34 14 17 24 [出力例] First [入力例] 30 55 50 489 550 368 440 541 255 423 509 378 496 296 466 315 380 404 397 322 296 346 283 492 430 438 517 541 411 426 477 331 347 [出力例] Second [入力例] 50 2023 2020 8586 8043 4543 12629 21215 17172 4543 9086 16672 13129 12629 8586 13129 20715 16672 5043 5043 8586 21215 9086 20715 17172 5043 21215 20715 17172 21215 12629 16672 4543 12629 9086 12629 12629 20715 17172 9086 4543 9086 5043 12629 4543 12629 17172 12629 13129 21215 4543 17172 17172 [出力例] First |
■参照サイト
AtCoder Regular Contest 143