C++の練習を兼ねて, AtCoder Regular Contest 109 の 問題A (Hands) ～ 問題B (log) を解いてみた.
■感想.
1. 問題A は, 規則性が見つかったので, AC版に到達できたと思う.
2. 問題B は, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 109 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報. int a, b, x, y; scanf("%d %d %d %d", &a, &b, &x, &y); // 2. 建物 A から 建物 B へ 移動. int dif = abs(a - b) - (a > b); printf("%d\n", min(x + dif * y, (2 * dif + 1) * x)); 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 |
[入力例] 2 1 1 5 [出力例] 1 ※AtCoderのテストケースより [入力例] 1 2 100 1 [出力例] 101 ※AtCoderのテストケースより [入力例] 1 100 1 100 [出力例] 199 ※AtCoderのテストケースより [入力例] 2 3 4 5 [出力例] 9 [入力例] 60 20 5 3 [出力例] 122 [入力例] 75 25 1 4 [出力例] 99 [入力例] 18 98 3 2 [出力例] 163 [入力例] 94 72 2 5 [出力例] 86 |
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; int main(){ // 1. 入力情報. LL n; scanf("%lld", &n); // 2. 最小コストは？ // -> 二分探索で確認してみる. LL l = 0, h = (LL)sqrt(2 * n + 2) + 1, m, e, en = 2 * n + 2; while(l + 1 < h){ m = (h + l) >> 1; e = m * (m + 1); if(e > en) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 3. 出力. printf("%lld\n", n - l + 1LL); 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 |
[入力例] 4 [出力例] 3 ※AtCoderのテストケースより [入力例] 109109109109109109 [出力例] 109109108641970782 ※AtCoderのテストケースより [入力例] 1 [出力例] 1 [入力例] 2 [出力例] 1 [入力例] 7 [出力例] 5 [出力例] 1234567890 [出力例] 1234518202 [出力例] 2020112992110202 [出力例] 2020112928547432 |
■参照サイト
AtCoder Regular Contest 109