C++の練習を兼ねて, AtCoder Beginner Contest 178 の 問題D (Redistribution) ~ 問題E (Dist Max) を解いてみた.
■感想.
1. 問題D は, 規則性を抽出することが出来たので, AC版に到達することが出来たと思う.
2. 問題E は, 過去問の解説E – へんなコンパスをヒントにして, 解答することが出来た.
※ 後日, 過去問(E – へんなコンパス) の 実装にも, 挑戦してみたいと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト
AtCoder Beginner Contest 178 (D – Redistribution)解説
AtCoder Beginner Contest 178 (E – Dist Max)解説
をご覧下さい.
■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 |
// 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--) const LL MOD = 1e9 + 7; LL ans[2020]; int main(){ // 1. 入力情報取得. int S; scanf("%d", &S); // 2. 数列を更新. // ex. // ① すべての項が 1 以上 の 場合. // 1 -> 2 -> 4 -> 8 -> 16 -> ... // ② すべての項が 2 以上 の 場合(Fibonacci数列に見える). // 0 -> 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> ... // ③ すべての項が 3 以上 の 場合(Fibonacci数列と異なるが似ている数列に見える). // 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 3 -> 4 -> 6 -> 9 -> 13 -> 19 -> ... ans[0] = 0; ans[1] = 0; ans[2] = 1; ans[3] = 1; repx(i, 4, S) ans[i] = ans[i - 2] + ans[i - 3] + ans[i - 4], ans[i] %= MOD; // 3. 出力. printf("%lld\n", ans[S - 1]); 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 |
[入力例] 7 [出力例] 3 ※AtCoderテストケースより [入力例] 2 [出力例] 0 ※AtCoderテストケースより [入力例] 1729 [出力例] 294867501 ※AtCoderテストケースより [入力例] 12 [出力例] 19 [入力例] 39 [出力例] 578949 [入力例] 2000 [出力例] 883312678 |
■C++版プログラム(問題E/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 |
// 以下の(過去問)解説を参照. // https://img.atcoder.jp/arc065/editorial.pdf // 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--) int x[202020], y[202020]; int main() { // 1. 入力情報取得. int N; scanf("%d", &N); rep(i, N){ int tx, ty; scanf("%d %d", &tx, &ty); // 変換(tx, ty) -> (tx + ty, tx - ty). x[i] = tx + ty; y[i] = tx - ty; } // 2. sort. sort(x, x + N); sort(y, y + N); // 3. 出力. int ans = max(x[N - 1] - x[0], y[N - 1] - y[0]); printf("%d\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 |
[入力例] 3 1 1 2 4 3 2 [出力例] 4 ※AtCoderテストケースより [入力例] 2 1 1 1 1 [出力例] 0 ※AtCoderテストケースより [入力例] 5 1 8 10 12 3 7 5 15 9 16 [出力例] 16 [入力例] 11 9899 2340 5334 6741 6785 11178 7271 1786 1283 5303 1677 7101 3034 876 12046 7909 4690 4561 6043 9814 4879 8511 [出力例] 16045 |
■参照サイト
AtCoder Beginner Contest 178
AtCoder Regular Contest 065