C++の練習を兼ねて, AtCoder Beginner Contest 251 の 問題C (Poem Online Judge) ～ 問題E (Prefix Equality) を解いてみた.
■感想.
1. 問題D, Eは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できた.
2. 問題E で, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 251 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int main(){ // 1. 入力情報. int N, score = -1, ans = 0; scanf("%d", &N); set<string> st; rep(i, N){ char c[22]; int t; scanf("%s %d", c, &t); string s(c); if(!st.count(s)){ st.insert(s); if(t > score){ score = max(score, t); ans = i + 1; } } } // 2. 出力. printf("%d\n", ans); 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 |
[入力例] 3 aaa 10 bbb 20 aaa 30 [出力例] 2 ※AtCoderテストケースより [入力例] 5 aaa 9 bbb 10 ccc 10 ddd 10 bbb 11 [出力例] 2 ※AtCoderテストケースより [入力例] 10 bb 3 ba 1 aa 4 bb 1 ba 5 aa 9 aa 2 ab 6 bb 5 ab 3 [出力例] 8 ※AtCoderテストケースより [入力例] 20 aykwsc 7 nfnmrr 19 nfnmrr 40 aykwsc 18 aykwsc 17 ytdnae 34 rdaeaa 55 nfnmrr 88 aykwsc 34 aykwsc 76 nfnmrr 55 xvafua 77 rdaeaa 100 nfnmrr 99 xvafua 11 nfnmrr 13 nfnmrr 17 xvafua 56 nfnmrr 78 xvafua 80 [出力例] 12 |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc251/editorial/3958 // 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 pb push_back int main(){ // 1. 入力情報. int W; scanf("%d", &W); // 2. 297個のおもりを用意. vi ans; repx(i, 1, 100) ans.pb(i); repex(i, 100, 10000, 100) ans.pb(i); repex(i, 10000, 1000000, 10000) ans.pb(i); // 3. 出力. puts("297"); rep(i, 297) printf("%d%s", ans[i], (i < 296) ? " " : "\n"); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
[入力例] 6 [出力例] 3 1 2 3 ※AtCoderテストケースより [入力例] 12 [出力例] 6 2 5 1 2 5 1 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 297 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 98 99 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000 3100 3200 3300 3400 3500 3600 3700 3800 3900 4000 4100 4200 4300 4400 4500 4600 4700 4800 4900 5000 5100 5200 5300 5400 5500 5600 5700 5800 5900 6000 6100 6200 6300 6400 6500 6600 6700 6800 6900 7000 7100 7200 7300 7400 7500 7600 7700 7800 7900 8000 8100 8200 8300 8400 8500 8600 8700 8800 8900 9000 9100 9200 9300 9400 9500 9600 9700 9800 9900 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 110000 120000 130000 140000 150000 160000 170000 180000 190000 200000 210000 220000 230000 240000 250000 260000 270000 280000 290000 300000 310000 320000 330000 340000 350000 360000 370000 380000 390000 400000 410000 420000 430000 440000 450000 460000 470000 480000 490000 500000 510000 520000 530000 540000 550000 560000 570000 580000 590000 600000 610000 620000 630000 640000 650000 660000 670000 680000 690000 700000 710000 720000 730000 740000 750000 760000 770000 780000 790000 800000 810000 820000 830000 840000 850000 860000 870000 880000 890000 900000 910000 920000 930000 940000 950000 960000 970000 980000 990000 |
■C++版プログラム(問題E／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 |
// 解き直し. // https://atcoder.jp/contests/abc251/editorial/3960 // 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--) LL a[303030], dp1[303030][2], dp2[303030][2]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i + 1]); // 2. dp更新. // 2-1. 行動 1 を 行わない. dp1[1][1] = 202020202020202020; repx(i, 2, N + 1){ // 行動 i を 行わない. dp1[i][0] = dp1[i - 1][1]; // 行動 i を 行う. dp1[i][1] = min(dp1[i - 1][0], dp1[i - 1][1]) + a[i]; } // 2-2. 行動 1 を 行う. dp2[1][0] = 202020202020202020; dp2[1][1] = a[1]; repx(i, 2, N + 1){ // 行動 i を 行わない. dp2[i][0] = dp2[i - 1][1]; // 行動 i を 行う. dp2[i][1] = min(dp2[i - 1][0], dp2[i - 1][1]) + a[i]; } // 3. 出力. printf("%lld\n", min(dp1[N][1], min(dp2[N][0], dp2[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 |
[入力例] 5 2 5 3 2 5 [出力例] 7 ※AtCoderテストケースより [入力例] 20 29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 [出力例] 426 ※AtCoderテストケースより [入力例] 30 30 49 56 91 84 119 106 110 74 27 111 108 120 64 47 84 110 61 75 25 119 115 86 60 32 27 120 56 65 23 [出力例] 1000 [入力例] 50 1111 5764 9932 7890 7777 1045 4763 4839 1132 3456 7777 8284 6694 214 2851 7890 7130 6349 1076 5135 3067 279 5955 6341 11126 414 9876 7777 5694 2244 6985 2998 7329 6318 6789 2659 3957 2395 3137 2250 5555 3439 4928 7662 3333 2222 4567 939 5336 6666 [出力例] 100000 |
■参照サイト
パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）