C++の練習を兼ねて, AtCoder Beginner Contest 054 の 問題C (One-stroke Path) ～ 問題D (Mixing Experiment) を解いてみた.
■感想.
1. 問題D の テストケース(subtask_1_09.txt) で, WA版 となったものの, 原因を特定して修正したところ, AC版 に到達できた.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAtCoder Beginner Contest 054 解説をご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #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 N, M; scanf("%d %d", &N, &M); vvi G(N); rep(i, M){ int a, b; scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); } // 2. 経路探索. // -> 頂点番号が, 1桁である場合の探索(※2桁以上は, 成立しない) int ans = 0; function<void(int, string, int)> dfs = [&](int s, string route, int N) { // 2-1. 終了条件. if(route.size() == N){ ans++; return; } // 2-2. 次の頂点へ. int l = route.size(); for(auto &u : G[s]){ // すでに訪問済みか確認. bool ok = true; rep(i, l) if((route[i] - '0') == u) ok = false; // 未訪問の場合. if(!ok) continue; string nr = route + to_string(u); dfs(u, nr, N); } }; dfs(0, "0", N); // 3. 出力. 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 |
[入力例] 3 3 1 2 1 3 2 3 [出力例] 2 ※AtCoderテストケースより [入力例] 7 7 1 3 2 7 3 4 4 5 4 6 5 6 6 7 [出力例] 1 ※AtCoderテストケースより [入力例] 5 7 1 3 2 4 1 5 2 3 3 5 4 5 1 2 [出力例] 6 |
■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 50 51 52 53 54 55 |
// コメント, ロジックを修正して再提出. // 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--) const int INF = 2020202020; int dp[404][404]; // タイプA が a[g], タイプB が b[g] の 場合における 最小価格[円] を 保存. int main() { // 1. 入力情報取得. int N, Ma, Mb; scanf("%d %d %d", &N, &Ma, &Mb); // 2. dp更新. rep(i, N){ int ca, cb, cc; scanf("%d %d %d", &ca, &cb, &cc); repr(a, 403, 0){ repr(b, 403, 0){ int na = a + ca; int nb = b + cb; if(na > 403 || nb > 403) continue; if(na == ca && nb == cb){ // 同じ組み合わせが含まれる場合があるので注意(※以下のロジックを追加). // -> subtask_1_09.txt における 5 4 73 と 5 4 7 if(dp[na][nb]) dp[na][nb] = min(dp[na][nb], cc); else dp[na][nb] = cc; } if(dp[a][b]){ if(dp[na][nb]) dp[na][nb] = min(dp[na][nb], dp[a][b] + cc); else dp[na][nb] = dp[a][b] + cc; } } } } // 3. 物質C を 生成するための最小予算は？ int ans = INF; rep(i, N + 1){ int a = Ma * i; int b = Mb * i; if(a > 400 || b > 400) break; if(dp[a][b]) ans = min(ans, dp[a][b]); } // 4. 出力. if(ans == INF) ans = -1; 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 |
[入力例] 3 1 1 1 2 1 2 1 2 3 3 10 [出力例] 3 ※AtCoderテストケースより [入力例] 1 1 10 10 10 10 [出力例] -1 ※AtCoderテストケースより [入力例] 17 5 7 3 1 96 5 6 55 5 12 25 3 5 39 12 12 96 10 8 9 4 4 93 3 2 68 7 11 10 11 6 3 7 10 96 7 8 29 7 11 86 2 10 4 11 3 97 9 2 5 5 11 84 [出力例] 116 |
■参照サイト
AtCoder Beginner Contest 054