C++の練習を兼ねて, AtCoder Beginner Contest 279 の 問題C (RANDOM) ~ 問題D (Freefall) を解いてみた.
■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D は, 桁数オーバーフローを回避する訓練が積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 279 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #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 int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); vector<string> S, T; rep(i, H){ char c[W + 1]; scanf("%s", c); string s(c); S.pb(s); } rep(i, H){ char c[W + 1]; scanf("%s", c); string t(c); T.pb(t); } // 2. 列情報保存. map<string, int> ms, mt; rep(j, W){ string sCur, tCur; rep(i, H){ sCur.pb(S[i][j]); tCur.pb(T[i][j]); } ++ms[sCur]; ++mt[tCur]; } // 3. 出力. printf("%s\n", (ms == mt) ? "Yes" : "No"); 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 |
[入力例] 3 4 ##.# ##.. #... .### ..## ...# [出力例] Yes ※AtCoderテストケースより [入力例] 3 3 #.# .#. #.# ##. ##. .#. [出力例] No ※AtCoderテストケースより [入力例] 2 1 # . # . [出力例] Yes ※AtCoderテストケースより [入力例] 8 7 #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. ....### ####... ....### ####... ....### ####... ....### ####... [出力例] Yes ※AtCoderテストケースより |
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) int main(){ // 1. 入力情報. LL A, B; scanf("%lld %lld", &A, &B); // 2. g を t 増やすと仮定. // -> t は A / (2 * B) の (2 / 3)乗 - 1 と思われる. LL x = 0; rep(i, 1010101){ if((LL)i * (LL)i * (LL)i > A / (2 * B)){ x = i; break; } } // 3. 最小値は? // 区間[(x - 1) * (x - 1), x * x] で 考えてみる. double ans = 2020202020202020202.0; rep(i, 2 * (int)x + 2){ LL t = (x - 1) * (x - 1) + i - 1; ans = min(ans, (double)A / sqrt(t + 1) + (double)(B * t)); } // 4. 出力. printf("%.10lf\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 |
[入力例] 10 1 [出力例] 7.7735026919 ※AtCoderテストケースより [入力例] 5 10 [出力例] 5.0000000000 ※AtCoderテストケースより [入力例] 1000000000000000000 100 [出力例] 8772053214538.5976562500 ※AtCoderテストケースより [入力例] 2022 5 [出力例] 511.7701391582 [入力例] 20221130 11 [出力例] 311951.5299304323 [入力例] 123456789012345678 55 [出力例] 1781963505917.5668945312 |
■参照サイト
トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)