C++の練習を兼ねて, AtCoder Beginner Contest 183 の 問題C (Travel) ～ 問題D (Water Heater) を解いてみた.
■感想.
1. 問題C, D は, 方針が見えたので, AC版に到達できたと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 183 解説 の 各リンク を ご覧下さい.
■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 |
// 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--) #define all(x) x.begin(), x.end() #define pb push_back int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); int t[N][N]; memset(t, 0, sizeof(t)); rep(i, N) rep(j, N) scanf("%d", &t[i][j]); // 2. 全ての都市を一度ずつ訪問して, 都市 1 に 戻る. vector<int> z(N - 1); iota(all(z), 1); int ans = 0; do{ // 2-1. 先頭に, 都市 1 を 追加. vector<int> v; v.pb(0); for(auto &p : z) v.pb(p); // 2-2. 都市 v[i - 1] から 都市 v[i] に かかる移動コスト. int cost = 0; repx(i, 1, N) cost += t[v[i - 1]][v[i]]; // 2-3. 都市 z[N - 1] から 都市 1 に 戻るコスト. cost += t[v[N - 1]][0]; // 2-4. コストを評価. if(cost == K) ans++; }while(next_permutation(all(z))); // 4. 出力. 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 |
[入力例] 4 330 0 1 10 100 1 0 20 200 10 20 0 300 100 200 300 0 [出力例] 2 ※AtCoderテストケースより [入力例] 5 5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 [出力例] 24 ※AtCoderテストケースより [入力例] 4 33 0 11 15 7 11 0 2 8 15 2 0 13 7 8 13 0 [出力例] 2 [入力例] 8 55 0 1 8 13 13 12 3 8 1 0 6 10 5 15 12 4 8 6 0 9 9 10 2 4 13 10 9 0 6 3 13 2 13 5 9 6 0 8 3 3 12 15 10 3 8 0 4 3 3 12 2 13 3 4 0 5 8 4 4 2 3 3 5 0 [出力例] 208 |
■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 |
// 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[202020]; int main(){ // 1. 入力情報. int N; LL W; scanf("%d %lld", &N, &W); rep(i, N){ int s, t; LL p; scanf("%d %d %lld", &s, &t, &p); a[s] += p; a[t] -= p; } // 2. いもす法. rep(i, N) a[i + 1] += a[i]; // 3. 判定. bool ok = true; rep(i, N){ if(a[i] > W){ ok = false; break; } } // 4. 出力. printf("%s\n", ok ? "Yes" : "No"); 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 |
[入力例] 4 10 1 3 5 2 4 4 3 10 6 2 4 1 [出力例] No ※AtCoderテストケースより [入力例] 4 10 1 3 5 2 4 4 3 10 6 2 3 1 [出力例] Yes ※AtCoderテストケースより [入力例] 6 1000000000 0 200000 999999999 2 20 1 20 200 1 200 2000 1 2000 20000 1 20000 200000 1 [出力例] Yes ※AtCoderテストケースより [入力例] 30 1173038 2009 4942 1067073 2593 3627 589007 12274 23738 493565 1620 2439 49298 4721 6910 597228 10201 20240 838808 6968 10973 1044511 7170 10610 392923 4276 13437 760468 2615 8845 126674 6552 12991 201424 4087 6385 731322 6009 9169 1151498 4730 6847 44831 5061 14651 841829 3704 5006 172107 1853 8489 1173038 6041 9358 1168692 12047 22833 908901 10520 15236 780752 4622 12308 366487 11588 15241 239514 1761 9840 771877 6324 10107 343644 10551 19925 106151 7362 7829 69671 1702 7577 158023 4211 11394 763230 5556 9641 86735 9424 10066 991486 [出力例] Yes |
■参照サイト
AtCoder Beginner Contest 183