C++の練習を兼ねて, AtCoder Beginner Contest 019 の 問題C (C – 高橋くんと魔法の箱) ～ 問題D (D – 高橋くんと木の直径) を解いてみた.
■感想.
1. C問題は, 2で割れる場合に, ひたすら割っていくことに気付けたので, AC版に到達出来た.
2. D問題は, 木の直径についての性質を復習出来たので, 良かったと思う, 但し, 入出力が, 特殊なパターンだったので, 慣れるまで苦労した.
本家のサイトAtCoder Beginner Contest 019 解説 をご覧下さい.
■C++版プログラム(問題C／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<int, int> m; for(int i = 0; i < N; i++){ int a; scanf("%d", &a); while(a % 2 == 0) a >>= 1; m[a]++; } // 2. 出力 ～ 後処理. printf("%d\n", m.size()); 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 |
[入力例] 3 1 2 3 [出力例] 2 ※AtCoderテストケースより [入力例] 4 2 4 8 16 [出力例] 1 ※AtCoderテストケースより [入力例] 4 2 3 5 7 [出力例] 4 ※AtCoderテストケースより [入力例] 100 950 369 38 887 498 212 660 1081 233 662 1233 161 733 362 813 1077 489 119 1130 412 855 973 324 1066 1037 1116 321 900 573 322 621 784 794 305 591 719 154 352 836 1148 476 949 1215 39 751 286 410 814 64 539 1058 872 98 926 759 121 934 988 1032 656 350 10 19 1096 483 663 581 600 525 90 216 1099 1084 988 708 403 818 498 978 613 849 1077 869 433 32 837 288 1204 128 873 675 591 611 1180 419 963 73 524 824 489 [出力例] 87 |
■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 |
#include <bits/stdc++.h> using namespace std; int main() { // 1. 入力情報取得. int N; scanf("%d", &N); // 2. 頂点 1 と 頂点 2 ～ 頂点 N の 各距離 を 質問. // -> 頂点 u で 最大距離 du を 取得. int dist = 0; int u = 0, du = 0; for(int i = 2; i <= N; i++){ printf("? %d %d\n", 1, i); fflush(stdout); scanf("%d", &dist); if(du < dist) du = dist, u = i; } // 3. 頂点 u と 頂点 2 ～ 頂点 N (※頂点 u は 除く)の 各距離 を 質問. // -> 頂点 v で 最大距離 dv を 取得. int v = 0, dv = 0; // N = 2 の ケース がありうるので, i = 1 からスタートさせる形に修正. // ※テストケース subtask0_0.txt 等 で, WA となるため. // for(int i = 2; i <= N; i++){ for(int i = 1; i <= N; i++){ if(u == i) continue; printf("? %d %d\n", u, i); fflush(stdout); scanf("%d", &dist); if(dv < dist) dv = dist, v = i; } // 4. 木の直径を, dv で, 出力. printf("! %d", dv); return 0; } |
■参照サイト
AtCoder Beginner Contest 019