C++の練習を兼ねて, AtCoder Beginner Contest 099 の 問題D (D – Worst Case) を解いてみた.
■感想.
1. 解答方針が見えなかったので, 解説を参照して確認した.
2. 復習出来てない問題が, まだまだ, たくさんあるので, 今後も, 少しずつ進めていきたいと思う.
本家のサイトARC094/ABC093解説をご覧下さい.
■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 |
// 解き直し. // ARC094/ABC093解説 // https://img.atcoder.jp/arc094/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. int Q; scanf("%d", &Q); // 2. 各クエリに解答. // 解説通り. for(int i = 0; i < Q; i++){ LL a, b; scanf("%llu %llu", &a, &b); if(a > b) swap(a, b); // 2-1. A = B の 場合. if(a == b){ printf("%llu\n", 2 * a - 2); continue; } // 2-2. A + 1 = B の 場合. if(a + 1 == b){ printf("%llu\n", 2 * a - 2); continue; } // 2-3. 上記以外 の 場合. if(a != b && a + 1 != b){ LL c = sqrt(a * b); if(c * c == a * b) c--; // C * (C + 1) >= A * B の 場合. if(c * (c + 1) >= a * b){ printf("%llu\n", 2 * c - 2); continue; } // C * C < A * B の 場合. if(c * c < a * b){ printf("%llu\n", 2 * c - 1); continue; } } } // 3. 後処理. return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
[入力例] 8 1 4 10 5 3 3 4 11 8 9 22 40 8 36 314159265 358979323 [出力例] 1 12 4 11 14 57 31 671644785 ※AtCoderテストケースより |
■参照サイト
AtCoder Beginner Contest 093