C++の練習を兼ねて, AtCoder Regular Contest 152 の 問題C (Pivot) を解いてみた.
■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 152 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc152/editorial/5118 // 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--) LL a[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. 解説通り. LL d = a[N - 1] - a[0], g = d, m = a[0]; rep(i, N) g = __gcd(g, 2 * (a[i] - m)); // 3. 出力. printf("%lld\n", m % g + d); 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 |
[入力例] 3 1 3 6 [出力例] 5 ※AtCoderのテストケースより [入力例] 5 400 500 600 700 800 [出力例] 400 ※AtCoderのテストケースより [入力例] 10 28 35 48 60 64 71 98 99 101 105 [出力例] 77 [入力例] 30 101 120 222 333 429 433 444 465 500 510 528 555 600 666 701 777 811 826 828 888 900 924 987 999 1010 1111 1155 1199 1200 1212 [出力例] 1111 [入力例] 50 2244 2823 2952 4405 4758 5000 11111 13509 14422 14746 20081 22222 30000 31135 31160 31171 31423 33333 41000 43000 44444 44633 55555 58825 60236 62022 65280 66392 66666 68304 69169 70842 72100 73600 77777 79455 81845 83000 84427 96524 97000 97967 98639 99227 99999 100000 105000 111111 115000 123456 [出力例] 121212 |
■参照サイト
AtCoder Regular Contest 152