C++の練習を兼ねて, AtCoder Beginner Contest 222 の 問題C (Swiss-System Tournament) ~ 問題D (Between Two Arrays) を解いてみた.
■感想.
1. 問題C, Dは, 方針が見えたので, AC版に到達出来たと思う.
2. 問題D で, 苦手なdpの訓練を積めたことが非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 222 解説 の 各リンク を ご覧下さい.
■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 60 61 62 63 64 65 66 67 68 69 70 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; 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 pb push_back #define a first #define b second #define all(x) x.begin(), x.end() int a[101][101]; // {グー, チョキ, パー} = {1, 2, 3}. int win[101]; // 勝数. int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, 2 * N){ char c[101]; scanf("%s", c); rep(j, M){ if(c[j] == 'G') a[i][j] = 1; if(c[j] == 'C') a[i][j] = 2; if(c[j] == 'P') a[i][j] = 3; } } // 2. ラウンドごとに勝敗を確認. vp ans; rep(i, M + 1){ // 2-1. 勝数 と プレイヤー を 保存. vp cur; rep(j, 2 * N) cur.pb({win[j], j}); // 2-2. sort. // -> 勝数が多い人ほど, 順位が高くなるように並べ替える. sort(all(cur)); // 2-3. 終了条件. if(i == M){ ans = cur; break; } // 2-4. 試合. rep(j, N){ int p = cur[j * 2 + 0].b; int q = cur[j * 2 + 1].b; int d = (3 + a[p][i] - a[q][i]) % 3; // 引き分け. if(d == 0) continue; // p が q に 勝利. if(d == 2) win[p]--; // q が p に 勝利. if(d == 1) win[q]--; } } // 3. 出力. rep(i, 2 * N) printf("%d\n", ans[i].b + 1); 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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
[入力例] 2 3 GCP PPP CCC PPC [出力例] 3 1 2 4 ※AtCoderテストケースより [入力例] 2 2 GC PG CG PP [出力例] 1 2 3 4 ※AtCoderテストケースより [入力例] 5 5 CPGPG CCCCC GGCPC PPPCP CGCPP PGGPG CGCGP GCPCC PPGPC PCGCP [出力例] 8 3 4 5 9 10 1 6 7 2 [入力例] 10 12 CPPCCPPGCGCC CPCGCGPPPCPP PGCCCGCPCGPC CPGGGPGCGGGC GCGPPPCCPPPC PGCCCCGCPCGP PCCGPPPPCGGG CGPPCCPGCPCG CCCGPGGPCCCP CCPGGPCCPCGG GCPGPGPCCGGC PCPCCGPPPCGP CCGCCCCCPCGG GGPGGGPPCGGC CGCCCCGGCGPC PGPGGPCPCPCP CCGCGCGPPCPG CCPGGGCGCCPC GGCPGCPGGPGC GGGCPPPCGGCG [出力例] 8 7 11 18 3 4 16 2 5 6 10 14 15 17 9 12 19 13 20 1 |
■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 |
// 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--) const LL MOD = 998244353; int a[3030], b[3030]; LL dp[3030][3030]; // {項番, cの値}. int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); // 2. 整数列 C の ありうる個数は? // 2-1. 初期化. repx(c, a[0], b[0] + 1) dp[0][c] = 1; rep(c, 3029){ dp[0][c + 1] += dp[0][c]; dp[0][c + 1] %= MOD; } // 2-2. dp更新. repx(i, 1, N){ // (i - 1)番目 から i番目へ. repx(c, a[i], b[i] + 1){ dp[i][c] += dp[i - 1][c]; dp[i][c] %= MOD; } // 累積和. rep(c, 3029){ dp[i][c + 1] += dp[i][c]; dp[i][c + 1] %= MOD; } } // 3. 出力. printf("%lld", dp[N - 1][b[N - 1]]); 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 |
[入力例] 2 1 1 2 3 [出力例] 5 ※AtCoderテストケースより [入力例] 3 2 2 2 2 2 2 [出力例] 1 ※AtCoderテストケースより [入力例] 10 1 2 3 4 5 6 7 8 9 10 1 4 9 16 25 36 49 64 81 100 [出力例] 978222082 ※AtCoderテストケースより [入力例] 5 0 1 5 6 7 0 3 8 9 11 [出力例] 159 [入力例] 7 0 1 2 6 10 10 14 0 1 5 7 11 15 17 [出力例] 336 [入力例] 10 1 2 5 7 11 13 15 18 18 18 2 5 9 13 14 15 18 22 25 27 [出力例] 1670080 [入力例] 25 1 2 6 10 13 13 13 16 17 18 22 23 27 29 32 35 39 42 42 42 44 48 52 56 59 2 6 8 11 15 19 21 22 26 27 31 33 33 33 33 38 41 44 46 48 52 55 59 61 61 [出力例] 494538601 |
■参照サイト
エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222)