C++の練習を兼ねて, AtCoder Beginner Contest 125 の 問題C (C – GCD on Blackboard) ～ 問題D (D – Flipping Signs) を解いてみた.
■感想.
1. 問題C, D ともに, 解答方針が全く見えなかったので, 解説を丸写しする感覚で解き直しした.
本家のサイトABC125解説をご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc125/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. int N; cin >> N; LL A[N + 1]; A[0] = 0; for(int i = 1; i < N + 1; i++) cin >> A[i]; // 2. 解説通り. // L[0], L[1], L[2], ... , L[N + 1] // R[0], R[1], R[2], ... , R[N + 1] // を用意する. LL L[N + 2], R[N + 2]; L[0] = 0, R[N + 1] = 0; for(int i = 0; i <= N; i++) L[i + 1] = __gcd(L[i], A[i]); for(int i = N; i >= 0; i--) R[i] = __gcd(R[i + 1], A[i]); // 3. 解説通り. LL ans = 0; for(int i = 0; i <= N; i++) ans = max(ans, __gcd(L[i], R[i + 1])); // 4. 後処理. 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 |
// 解き直し. // https://img.atcoder.jp/abc125/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. int N; cin >> N; LL A[N]; LL total = 0; int zero = 0, minus = 0; for(int i = 0; i < N; i++){ LL a; cin >> a; A[i] = a; total += abs(a); if(a == 0) zero++; if(a < 0) minus++; } // 2. 解説通り. LL ans = 0; for(int i = 0; i < N; i++) ans = max(ans, total - 2 * abs(A[i])); if(zero > 0 || minus % 2 == 0) ans = total; // 3. 後処理. cout << ans << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 125