C++の練習を兼ねて, AtCoder Beginner Contest 297 の 問題C (PC on the Table) ~ 問題E (Kth Takoyaki Set) を解いてみた.
■感想.
1. 問題C ~ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 297 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; #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 H, W; scanf("%d %d", &H, &W); vs v; rep(i, H){ char c[202]; scanf("%s", c); string s(c); v.pb(s); } // 2. 操作. rep(i, H){ rep(j, W - 1){ if(v[i][j + 0] == 'T' && v[i][j + 1] == 'T'){ v[i][j + 0] = 'P'; v[i][j + 1] = 'C'; } } } // 3. 出力. rep(i, H) printf("%s\n", v[i].c_str()); 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 |
[入力例] 2 3 TTT T.T [出力例] PCT T.T ※AtCoderテストケースより [入力例] 3 5 TTT.. .TTT. TTTTT [出力例] PCT.. .PCT. PCTPC ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. PCT.. .PCT. PCPCT [入力例] 5 10 TT..TTTT.. ..TTTTTTT. TTTTT..TTT .T.TTTTT.T .TT..T..TT [出力例] PC..PCPC.. ..PCPCPCT. PCPCT..PCT .T.PCPCT.T .PC..T..PC |
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; #define a first #define b second int main(){ // 1. 入力情報. LL A, B; scanf("%lld %lld", &A, &B); // 2. 操作. LL ans = 0; queue<P> Q; Q.push({A, B}); while(!Q.empty()){ // キューから取り出す. P u = Q.front(); Q.pop(); // 大小関係の調整. if(u.a < u.b) swap(u.a, u.b); // カウント. LL q = u.a / u.b; LL r = u.a % u.b; ans += q; // 終了条件. if(r == 0){ --ans; break; } // 更新. u.a -= q * u.b; // 追加. Q.push({u.a, u.b}); } // 3. 出力. printf("%lld\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 |
[入力例] 3 8 [出力例] 4 ※AtCoderテストケースより [入力例] 1234567890 1234567890 [出力例] 0 ※AtCoderテストケースより [入力例] 1597 987 [出力例] 15 ※AtCoderテストケースより [入力例] 3141592 6535897 [出力例] 48 [入力例] 20230409 20230423 [出力例] 1445036 [入力例] 1234567890987654321 7 [出力例] 176366841569664902 |
■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 |
// 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[11]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); set<LL> st; rep(i, N){ scanf("%d", &a[i]); st.insert(a[i]); } // 2. 操作. LL ans = 0; while(K){ // 先頭要素. ans = *st.begin(); st.erase(st.begin()); // 追加. rep(i, N) st.insert(ans + a[i]); // サイズ調整. while(st.size() > K) st.erase(--(st.end())); // デクリメント. --K; } // 3. 出力. printf("%lld\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 |
[入力例] 4 6 20 25 30 100 [出力例] 50 ※AtCoderテストケースより [入力例] 2 10 2 1 [出力例] 10 ※AtCoderテストケースより [入力例] 10 200000 955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872 [出力例] 5705443819 ※AtCoderテストケースより [入力例] 5 123 314 159 265 358 979 [出力例] 1432 [入力例] 10 200000 333 1023 135 777 890 395 256 1234 321 999 [出力例] 201259 [入力例] 10 200000 598249 506436 1006871 522097 887419 682270 723768 608731 485561 195325 [出力例] 5953502 |
■参照サイト
AtCoder Beginner Contest 297