C++の練習を兼ねて, AtCoder Beginner Contest 026 の 問題D (D – 高橋君ボール1号) を解いてみた.
■感想.
1. とりあえず, 解説見る前に, AC版となったので良かったと思う.
2. 誤差を小さくするために, 試行錯誤した気がする, あと, 検算も行って, 誤差も確認してみた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 026解説をご覧下さい.
■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 56 57 58 59 60 61 |
#include <bits/stdc++.h> using namespace std; #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 pb push_back #define all(x) x.begin(), x.end() const double INF = 123456789.0; const double PI = acos(-1); // 近似値計算を行う. // @param A: 与えられた定数. // @param B: 与えられた定数. // @param C: 与えられた定数. // @param v: x1 - x2 の絶対値 が 最小となる差分を抽出するときの初期値. // @param t0: x1 - x2 の絶対値 が 最小となる時刻を抽出するときの初期値. // @param t1: チェック開始の時刻. // @param t2: チェック終了の時刻. // @param dt: 時刻の増分. // @param ret: f(t) = 100 の候補となる時刻 t を 返却. double approximation(double A, double B, double C, double v, double t0, double t1, double t2, double dt){ double mValue = v; double ret = t0; for(double t = t1; t <= t2; t += dt){ double x1 = (100.0 - A * t) / B; double x2 = sin(C * t * PI); double dx = abs(x1 - x2); if(mValue > dx) mValue = dx, ret = t; } return ret; } int main(){ // 1. 入力情報. double A, B, C; scanf("%lf %lf %lf", &A, &B, &C); // 2. t の 範囲. // sin が -1.0 ～ 1.0 を取り得るので, // (100.0 - B) / A ～ t ～ (100.0 + B) / A にあると見る. // (100.0 - A * t) / B と sin(C * t * PI) を 比較していく. double minT = (100.0 - B) / A - 1.0; double maxT = (100.0 + B) / A + 1.0; // 3. 求めたいタイミング t を 計算. // 3-1. 0.0001 刻みでチェック. double ans = approximation(A, B, C, INF, INF, minT, maxT, 0.0001); // 3-2. 0.0000001 刻みでチェック. ans = approximation(A, B, C, INF, INF, ans - 0.00005, ans + 0.00005, 0.0000001); // 3-3. 0.0000000001 刻みでチェック. ans = approximation(A, B, C, INF, INF, ans - 0.00000005, ans + 0.00000005, 0.0000000001); // 4. 出力. printf("%.12lf\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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
[入力例] 1 1 1 [出力例] 100 ※AtCoderテストケースより 但し, 上記のプログラムでは, 以下の内容が出力される. 99.999999999964 [入力例] 53 82 49 [出力例] 1.63372043395339 ※AtCoderテストケースより 但し, 上記のプログラムでは, 以下の内容が出力される. 3.339022245712 [検算] f(t) = A * t + B * sin(C * t * π) = 53 * 3.339022245712 + 82 * sin(49 * 3.339022245712 * pi) = 99.999999846272120472542354537431751869090678235828794219312798 [入力例] 2 5 11 [出力例] 47.500000000035 [検算] f(t) = A * t + B * sin(C * t * π) = 2 * 47.500000000035 + 5 * sin(11 * 47.500000000035 * pi) = 100.00000000006999999634269471912132454725400665944316198321531 [入力例] 73 97 53 [出力例] 2.409696528411 [検算] f(t) = A * t + B * sin(C * t * π) = 73 * 2.409696528411 + 97 * sin(53 * 2.409696528411 * pi) = 99.999999755111031414900657374160299818922779168874946453733136 [入力例] 83 93 62 [出力例] 0.950437075697 [検算] f(t) = A * t + B * sin(C * t * π) = 83 * 0.950437075697 + 93 * sin(62 * 0.950437075697 * pi) = 99.999999284483012827002351221307941250368079227798607124455658 [入力例] 3 5 7 [出力例] 34.166666666637 [検算] f(t) = A * t + B * sin(C * t * π) = 3 * 34.166666666637 + 5 * sin(7 * 34.166666666637 * pi) = 100.00000000273599251032683314745965551798528853209778735756501 [入力例] 97 86 75 [出力例] 0.356330212207 [検算] f(t) = A * t + B * sin(C * t * π) = 97 * 0.356330212207 + 86 * sin(75 * 0.356330212207 * pi) = 99.999999783042160771603891862182801369863813784100760331134612 [入力例] 37 91 58 [出力例] 0.320343316043 [検算] f(t) = A * t + B * sin(C * t * π) = 37 * 0.320343316043 + 91 * sin(58 * 0.320343316043 * pi) = 100.00000002495890247903533712021585220833944974624376986519264 |