C++の練習を兼ねて, AtCoder Grand Contest 009 の 問題A (Multiple Array) ~ 問題B (Tournament) を解いてみた.
■感想.
1. 問題B は, 方針が見えなかったので, 解説を参照して実装したところ, 何とか, AC版となった.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAGC 009 解説をご覧下さい.
■C++版プログラム(問題A/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 |
#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[101010], b[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld %lld", &a[i], &b[i]); // 2. ボタン押下回数を計算. LL ans = 0; repr(i, N - 1, 0){ LL o = a[i] + ans; LL q = o / b[i]; LL r = o % b[i]; if(r) ans += (q + 1) * b[i] - o; } // 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 |
[入力例] 3 3 5 2 7 9 4 [出力例] 7 ※AtCoderテストケースより [入力例] 7 3 1 4 1 5 9 2 6 5 3 5 8 9 7 [出力例] 22 ※AtCoderテストケースより [入力例] 15 744543377 1163468634 569628421 971725131 600757974 896465201 419534929 1228183668 13157065 555209570 1213562164 259777036 376116510 108283592 654211939 746966738 345452736 447088648 113848184 185915443 941826533 858584293 335044855 423926187 836461297 275864605 1096229572 978066684 349546551 785773384 [出力例] 5072799793 |
■C++版プログラム(問題B/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 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 101 102 103 104 105 |
// 解き直し. // https://img.atcoder.jp/agc009/editorial.pdf #include <bits/stdc++.h> using namespace std; using vvi = vector<vector<int>>; using P = pair<int, 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 a first #define b second #define pb push_back int d[101010]; // 頂点 1 からの 距離 を 保存. int dp[101010]; // 人 v に対応する頂点を根とした部分木だけに限定した場合のトーナメントの深さの最小値. int memo[101010]; // 訪問済みフラグ. // グラフを幅優先探索する. // 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. 訪問済みフラグ設定. d[s] = 0; // スタート地点は, 距離ゼロを指定. // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int u = q.front(); q.pop(); // 5. 取り出した要素を処理. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(d[e] > 0) continue; if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e); } } return; } int main(){ // 1. 入力情報. int N, a; scanf("%d", &N); vvi G(N); rep(i, N - 1){ scanf("%d", &a); a--; G[i + 1].pb(a); G[a].pb(i + 1); } // 2. 頂点 1 から 各頂点までの距離を計算. bfs(G, 0, d); // 3. 頂点 1 から 遠い順に並び替え. priority_queue<P> pq; rep(i, N) pq.push({d[i], i}); // while(!pq.empty()){ // P p = pq.top(); // pq.pop(); // printf("dist=%d v=%d\n", p.a, p.b); // } // 4. dp更新. while(!pq.empty()){ // 頂点を一つ取得. P v = pq.top(); pq.pop(); int p = v.b; // 親頂点. // 訪問済みならば, Skip. if(memo[p]) continue; memo[p] = 1; // 子頂点について, 並び替え. priority_queue<P> subPQ; for(auto &c : G[p]) subPQ.push({dp[c], c}); // 親頂点 p が, 子頂点 c と 試合を行う. int idx = 0; while(!subPQ.empty()){ P c = subPQ.top(); subPQ.pop(); if(d[p] < d[c.b]) dp[p] = max(dp[p], dp[c.b] + (++idx)); } } // rep(i, N) printf("%d ", dp[i]); // puts(""); // 5. 出力. printf("%d\n", dp[0]); 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 |
[入力例] 5 1 1 2 4 [出力例] 3 ※AtCoderテストケースより [入力例] 7 1 2 1 3 1 4 [出力例] 3 ※AtCoderテストケースより [入力例] 4 4 4 1 [出力例] 3 ※AtCoderテストケースより [入力例] 15 3 1 1 1 3 5 5 7 7 4 4 4 9 9 [出力例] 5 |
■参照サイト
AtCoder Grand Contest 009