C++の練習を兼ねて, AtCoder Beginner Contest 066 の 問題C（pushpush）を解いてみた.
■感想.
1. 数列の要素を, 問題文の操作で並び順を変えると, 膨大な計算量(O(nの2乗)) が必要となるが, 規則性を見つけると, 計算量が O(n) の 3倍程度 まで, 削減できる点が, 面白いと感じた.
2. 解説を読んだところ, 標準ライブラリ std::deque があるとのことで, 大変参考になったと思う.
3. 標準ライブラリ std::deque を使ってみたところ, 実装が, よりコンパクトにまとまって, びっくりした(汗).
本家のサイトABC066 / ARC077 解説をご覧下さい.
■C++版プログラム.
|
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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) typedef long long LL; int main() { // 1. 入力情報取得. int N; cin >> N; LL A[N] = {}; FOR(i, 0, N) cin >> A[i]; // 2. 問題文の操作した数列を保存. // 例) // 1 -> 1 // 1 2 -> 2 1 // 1 2 3 -> 3 1 2 // 1 2 3 4 -> 4 2 1 3 // 1 2 3 4 5 -> 5 3 1 2 4 // -> 以上のことから, // A の i番目の要素 は, // B の (N / 2) + sign * ((i + 1)/ 2)番目 に, 対応することが分かった. // 但し, 符合 sign の 初期値 は, N の 偶奇 で 分岐. LL B[N] = {}; int sign = ((N % 2 == 0) ? (-1) : 1); FOR(i, 0, N) { sign *= (-1); int index = (N / 2); index += (sign * ((i + 1) / 2)); // cout << index << endl; B[index] = A[i]; } // 3. 出力 ～ 後処理. FOR(i, 0, N) cout << B[i] << " "; return 0; } |
■C++版プログラム(std::dequeを使った場合).
|
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 |
// 解き直し. // std::deque を 使って, 実装した版. // ABC066 / ARC077 解説. // https://atcoder.jp/img/arc077/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) typedef long long LL; int main() { // 1. 入力情報取得. int N; cin >> N; LL A[N] = {}; FOR(i, 0, N) cin >> A[i]; // 2. 問題文の操作した数列を保存. // 例) // 1 -> 1 // 1 2 -> 2 1 // 1 2 3 -> 3 1 2 // 1 2 3 4 -> 4 2 1 3 // 1 2 3 4 5 -> 5 3 1 2 4 // // 解説通り. // i(※0 ～ N - 1) と N の 偶奇 を確認して, // 一致する … 数列A の要素を, deque の 末尾 に追加. // 一致しない … 数列A の要素を, deque の 先頭 に追加. deque<LL> dq; FOR(i, 0, N) { if((N - i) % 2 == 0) dq.push_back(A[i]); else dq.push_front(A[i]); } // 3. 出力 ～ 後処理. for (auto &p : dq) cout << p << " "; return 0; } |
■参照サイト
AtCoder Beginner Contest 066