C++の練習を兼ねて, AtCoder Beginner Contest 034 の 問題C(経路) ~ 問題D (食塩水) を解いてみた.
■感想.
1. 問題C は, AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid) と類似しているように見えたので, この問題の解答をベースに, 対応した.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.
※例えば, テストケース s1.txt の WA回避対応で, 小数第10桁までを出力するように修正している.
本家のサイトAtCoder Beginner Contest 034 解説をご覧下さい.
■C++版プログラム(問題C/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 |
// AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid) // -> 上記問題をベースに対応. #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) typedef long long LL; const LL MOD = 1e9 + 7; // Fermat's little theorem を 適用するため, 大きな冪乗の計算ができるようにする. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL inverse(LL a, LL b){ LL t = 1; while(b) { if(b & 1) t = (t * a) % MOD; a *= a; a %= MOD; b >>= 1; } return t % MOD; } int main() { // 1. 入力情報取得. LL W, H; cin >> W >> H; // 2. 経路数 (H + W - 2)! ÷ (H - 1)! ÷ (W - 1)! を 計算. // 2-1. 0 ≦ x ≦ H + W - 2 の x!(MOD版) を 計算. LL LIMIT = H + W - 2; LL FAC[LIMIT + 1] = {}; FAC[0] = 1; FOR(i, 1, LIMIT + 1) FAC[i] = i * FAC[i - 1] % MOD; // 2-2. 0 ≦ x ≦ H + W - 2 の x!(MOD版)の逆元 を 計算. LL INV[LIMIT + 1] = {}; FOR(i, 0, LIMIT + 1) INV[i] = inverse(FAC[i], MOD - 2) % MOD; // 2-3. 経路数を計算. LL ans = 0LL; ans = FAC[H + W - 2]; ans *= INV[H - 1]; ans %= MOD; ans *= INV[W - 1]; ans %= MOD; // 3. 出力 ~ 後処理. cout << ans << endl; return 0; } |
■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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
// 解き直し. // AtCoder Beginner Contest 034 解説. // https://www.slideshare.net/chokudai/abc034 #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) typedef long long LL; struct solution { LL w; // 食塩水(グラム). LL p; // 濃度(パーセント). double c; // 計算上の濃度から過不足する食塩量(グラム). }; // 指定した濃度の食塩水が作成可能であるかを確認. // @param v: 食塩水の入った容器. // @param x: 指定した濃度. // @param K: 選択する容器数. // @return: // true: 指定した濃度の食塩水を作ることが可能である. // false: 指定した濃度の食塩水を作ることが不可能である. bool check(vector<solution> v, double x, LL K) { // 食塩の過不足を確認, FOR(i, 0, v.size()) v[i].c = v[i].w * (v[i].p - x) / 100; // 過不足する食塩量で, 降順sort. sort(v.begin(), v.end(), [](const solution& x, const solution& y) {return x.c > y.c;}); // 容器を, K個選択して, 食塩水を作ってみる. double wTotal = 0.0; // 食塩水の総量. double sTotal = 0.0; // 食塩の総量. FOR(i, 0, K) wTotal += v[i].w, sTotal += v[i].w * v[i].p; double ret = sTotal * 1.0 / wTotal; // cout << ret << endl; // 指定した濃度の食塩水を作ることが 可能 か 不可能か? if(ret >= x) return true; else return false; } int main() { // 1. 入力情報取得. LL N, K; cin >> N >> K; vector<solution> v; // 食塩水に関する情報. FOR(i, 0, N) { LL w, p; cin >> w >> p; solution s; s.w = w; s.p = p; s.c = 0.0; v.push_back(s); } // 2. 解説通り. // -> 2分法使う. int counter = 0; double lower = 0.0; // 食塩水濃度の下限. double upper = 100.0; // 食塩水濃度の上限. double ans = 0.0; // 最終的に求めたい食塩水の濃度. while(counter < 50) { ans = (lower + upper) / 2; if(check(v, ans, K)) lower = ans; else upper = ans; counter++; } // 4. 出力 ~ 後処理. // s1.txt の WA回避対応. // -> AtCoderテストケース(25.000000000)より, 小数第10桁までで出力するように修正. cout << fixed; cout << setprecision(10) << ans << endl; 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 |
[入力例] 3 2 100 15 300 20 200 30 [出力例] 25.0000000000 ※AtCoderテストケースより [入力例] 3 2 100 60 300 25 200 30 [出力例] 40.0000000000 [入力例] 6 3 100 30 200 20 300 50 400 40 500 15 600 25 [出力例] 42.5000000000 ※(300, 5), (400, 40), (100, 30) を 選択すると, 42.5000000000% を実現できる. [入力例] 10 4 100 60 200 30 300 40 400 45 500 40 600 50 700 30 800 25 900 20 1000 35 [出力例] 47.1428571429 ※(100, 60), (300, 40), (400, 45), (600, 50) を 選択すると, 47.1428571429% を実現できる. [入力例] 1 1 1 0 [出力例] 0.0000000000 -> 仮に, 小数点以下10桁指定しないと, 7.88861e-29 のように出力される. -> このように, 0 と出力されないので, s1.txt で, WA判定されたと推測した. |
■参照サイト
AtCoder Beginner Contest 034