C++の練習を兼ねて, AtCoder Grand Contest 058 の 問題A (Make it Zigzag) を解いてみた.
■感想.
1. 問題Aは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Grand Contest 058 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A／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 |
// 解き直し. // https://atcoder.jp/contests/agc058/editorial/4574 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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 p[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, 2 * N) scanf("%d", &p[i]); // 2. 操作列. vi ans; rep(i, 2 * N - 1){ // 奇数. if(i & 1){ if(p[i] < p[i + 1]){ if(i == 2 * N - 2 || p[i] < p[i + 2]){ ans.pb(i + 1); swap(p[i], p[i + 1]); }else{ ans.pb(i + 2); swap(p[i + 1], p[i + 2]); } } } // 偶数. if(!(i & 1)){ if(p[i] > p[i + 1]){ if(i == 2 * N - 2 || p[i] > p[i + 2]){ ans.pb(i + 1); swap(p[i], p[i + 1]); }else{ ans.pb(i + 2); swap(p[i + 1], p[i + 2]); } } } } // 3. 出力. int n = ans.size(); printf("%d\n", n); rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n"); 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 |
[入力例] 2 4 3 2 1 [出力例] 2 1 3 ※AtCoderテストケースより [入力例] 1 1 2 [出力例] 0 ※AtCoderテストケースより [入力例] 3 5 1 2 3 6 4 [出力例] 2 1 4 [入力例] 4 5 4 2 1 3 8 6 7 [出力例] 2 1 4 [入力例] 15 3 2 9 30 12 29 14 4 21 19 18 13 25 10 5 8 6 11 24 16 15 26 17 1 20 22 27 23 28 7 [出力例] 8 2 8 12 13 18 24 26 29 [入力例] 25 22 38 35 49 29 48 17 27 4 19 14 42 2 20 15 10 1 23 44 43 8 26 39 37 34 3 40 46 45 6 16 50 7 33 25 21 41 47 31 24 11 5 13 9 18 30 12 28 32 36 [出力例] 10 15 18 22 26 29 36 39 42 44 48 [入力例] 25 50 8 29 35 19 46 28 25 22 2 7 42 36 30 47 23 18 13 44 38 4 1 21 34 5 27 20 15 26 9 12 14 49 31 45 37 40 48 43 33 39 17 6 41 3 16 32 10 24 11 [出力例] 16 1 7 9 14 15 18 22 28 29 32 34 36 39 41 47 49 |
■参照サイト
AtCoder Grand Contest 058