C++の練習を兼ねて, AtCoder Beginner Contest 173 の 問題F (Intervals on Tree) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参考に実装したところ, AC版となった.
2. 数え上げの方法が, 目から鱗で, 非常に感嘆したとともに, 本問題の奥深さを感じた
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 173 解説をご覧下さい.
■C++版プログラム(問題F/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 |
// C++(GCC 9.2.1) // 解き直し. // https://img.atcoder.jp/abc173/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--) int main(){ // 1. 入力情報. LL N, u, v, uv = 0; scanf("%lld", &N); rep(i, (int)(N - 1)){ scanf("%lld %lld", &u, &v); // 大小関係を考慮. if(u > v) swap(u, v); // 辺の出現数をカウント. // 辺 uv は, u * (N - v + 1)回分, 頂点集合 S に含まれるはず. uv += u * (N - v + 1); } // 2. 部分グラフの連結成分の個数の総和. // -> 頂点集合 S におけるすべての頂点の出現数の総和は, // 1, 4, 10, 20, 35, 56, ... と 増加するので, N * (N + 1) * (N + 2) / 6 で 計算されるはず. LL ans = N * (N + 1) * (N + 2) / 6 - uv; // 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 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 |
[入力例] 3 1 3 2 3 [出力例] 7 ※AtCoderテストケースより [入力例] 2 1 2 [出力例] 3 ※AtCoderテストケースより [入力例] 10 5 3 5 7 8 9 1 9 9 10 8 4 7 4 6 10 7 2 [出力例] 113 ※AtCoderテストケースより [入力例] 13 13 2 11 4 10 4 4 1 1 5 1 12 1 2 6 2 7 2 3 2 8 3 9 3 [出力例] 307 [入力例] 20 9 4 9 10 11 10 10 3 6 10 10 13 13 5 14 10 12 14 8 14 15 14 7 14 2 7 7 1 6 16 17 7 12 18 11 19 20 5 [出力例] 568 |
■参照サイト
AtCoder Beginner Contest 173