C++の練習を兼ねて, AtCoder Regular Contest 028 の 問題A (A – 小石を取るゲーム) ～ 問題B (B – 特別賞) を解いてみた.
■感想.
1. 実装に苦労したものの, 問題A, B ともに, AC版となったので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 028 解説をご覧下さい.
■C++版プログラム(問題A／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報. int N, A, B; scanf("%d %d %d", &N, &A, &B); // 2. 小石を取っていく. int res = N % (A + B); bool ans = (res > 0 && res <= A); // 3. 出力. printf("%s\n", ans ? "Ant" : "Bug"); 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 |
[入力例] 5 1 2 [出力例] Bug ※AtCoderのテストケースより [入力例] 10 3 4 [出力例] Ant ※AtCoderのテストケースより [入力例] 1 1 1 [出力例] Ant [入力例] 2 1 1 [出力例] Bug [入力例] 314 15 9 [出力例] Ant [入力例] 2718 28 182 [出力例] Bug [入力例] 14142 13 562 [出力例] Ant [入力例] 1202056 903 159 [出力例] Bug |
■C++版プログラム(問題B／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 |
// C++14 (GCC 5.4.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, 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 pb push_back #define a first #define b second int x[101010]; // {順位, 年齢} int main(){ // 1. 入力情報. int N, K; priority_queue<P> pq1; priority_queue<P, vector<P>, greater<P> > pq2; scanf("%d %d", &N, &K); rep(i, N){ scanf("%d", &x[i]); if(i < K - 1) pq1.push({x[i], i + 1}); // (K - 1)番目までの{年齢, 順位} } // 2. K番目に若い人は？ rep(i, N - K + 1){ // 2-1. 順位が, (i + K)位 の 参加者情報を取得. P cur = {x[i - 1 + K], i + K}; pq1.push(cur); // 2-2. 取り出す. P p, q; int rank = 0; if(pq1.size() > K){ p = pq1.top(); // (K + 1)番目 pq1.pop(); // pq1 から 削除. pq2.push(p); // pq2 へ 移動. p = pq1.top(); // K番目 q = pq2.top(); // (K + 1)番目 if(p.a > q.a){ rank = q.b; pq1.pop(); // pq1 から 削除. pq2.pop(); // pq2 から 削除. pq1.push(q); // pq1 へ 追加. pq2.push(p); // pq2 へ 追加. // printf("1. p.a=%d p.b=%d q.a=%d q.b=%d\n", p.a, p.b, q.a, q.b); }else{ rank = p.b; // printf("2. p.a=%d p.b=%d q.a=%d q.b=%d\n", p.a, p.b, q.a, q.b); } }else{ p = pq1.top(); // K番目 rank = p.b; // printf("3. p.a=%d p.b=%d\n", p.a, p.b); } // 2-3. 出力. printf("%d\n", rank); } 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 71 72 |
[入力例] 5 2 4 5 3 1 2 [出力例] 2 1 3 5 ※AtCoderのテストケースより [入力例] 3 1 2 3 1 [出力例] 1 1 3 ※AtCoderのテストケースより [入力例] 20 5 2 16 6 10 1 9 13 4 8 12 19 5 17 11 20 7 18 14 3 15 [出力例] 2 4 4 6 9 9 9 3 3 3 3 3 3 3 12 12 [入力例] 30 7 15 18 22 2 16 28 6 23 10 1 26 9 25 13 4 30 8 12 27 19 5 29 17 11 21 20 7 24 14 3 [出力例] 6 8 3 2 2 5 5 1 14 14 9 9 9 9 12 12 12 12 12 12 17 17 17 27 |
■参照サイト
AtCoder Regular Contest 028