C++の練習を兼ねて, AtCoder Beginner Contest 067 の 問題C (Splitting Pile) ~ 問題D (Fennec VS. Snuke) を解いてみた.
■感想.
1. 問題C, D ともに, 解説を確認して, ようやくAC版となった.
※問題C は, 問題文を誤読(カードの配分についての区切りが, 複数ありうると誤認)していたことも判明した(汗).
2. 問題D で, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAtCoder Beginner Contest 067 解説をご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/arc078/editorial.pdf #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], x[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); LL X = 0; rep(i, N){ scanf("%lld", &a[i]); x[i + 1] = x[i] + a[i]; X += a[i]; } // 2. |X - 2 * x[i]| を 評価. LL ans = 202020202020202020; rep(i, N - 1) ans = min(ans, abs(X - 2 * x[i + 1])); // 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 |
[入力例] 6 1 2 3 4 5 6 [出力例] 1 ※AtCoderテストケースより [入力例] 2 10 -10 [出力例] 20 ※AtCoderテストケースより [入力例] 6 1 3 4 7 8 9 [出力例] 2 [入力例] 20 3 14 15 9 26 53 58 97 9 32 3 84 62 6 43 38 32 79 50 2 [出力例] 77 |
■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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
// コメント修正して, 再提出. // 解き直し. // https://img.atcoder.jp/arc078/editorial.pdf // 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 d1[101010]; // 頂点 1 から各頂点への最短距離を保存. int dn[202020]; // 頂点 N から各頂点への最短距離を保存. // https://ja.wikipedia.org/wiki/幅優先探索 // ※bfsの動作確認用. // @param G: グラフ. // @param s: グラフの探索開始頂点. // @param d: 探索開始地点からの距離. // @return: 特に無し. void bfs(vvi &G, int s, int* d){ // 1. 空のキュー. queue<int> q; // 2. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 3. キューから取り出す. int u = q.front(); q.pop(); // 4. 取り出した要素を処理. for(auto &e : G[u]){ // 5. 訪問済であれば, 処理をスキップ. if(d[e]) continue; if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e); } } return; } int main(){ // 1. 入力情報. int N, a, b; scanf("%d", &N); vvi G(N); rep(i, N - 1){ scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); } // 2. 頂点 1, N から 各頂点への距離を保存. bfs(G, 0, d1); bfs(G, N - 1, dn); // 3. 黒, 白のマスの個数を評価. int black = 0; rep(i, N) if(d1[i] <= dn[i]) black++; // 4. 出力. printf("%s\n", (black > N / 2) ? "Fennec" : "Snuke"); 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 |
[入力例] 7 3 6 1 2 3 1 7 4 5 7 1 4 [出力例] Fennec ※AtCoderテストケースより [入力例] 4 1 4 4 2 2 3 [出力例] Snuke ※AtCoderテストケースより [入力例] 9 1 2 7 3 3 2 5 1 8 1 4 6 6 9 6 1 [出力例] Fennec [入力例] 10 9 10 10 8 1 10 2 1 3 2 2 4 8 7 7 6 7 5 [出力例] Snuke |
■参照サイト
AtCoder Beginner Contest 067