【競プロ】1日1AC : ABC66 C問題

暇を持て余しているので、深夜に2記事更新です。今日の問題はこちら。

Diffは524（茶）です。
問題の意味は分かりやすいですが、そのままシミュレーションすると間に合わないタイプの問題ですね。

提出コードと考え方

先ほども書きましたが、問題文通りにシミュレーションすると間に合いません。配列の要素を逆順に並べ替える時、要素数に比例した時間がかかるので、この問題の場合は計算量が \(\mathcal{O}(n^2)\) になるからですね。

ではどうするかというと、数列自体はいじらずに、方向（どちらを先頭とするか）だけbool型の変数で管理します。
例えば、1回目の操作の2番目では数列を反転しますが、これを「数列を逆方向に読むフラグを立てる」ことで処理します。次の操作では、直前に反転した数列の末尾に要素を追加するのですが、これを「逆方向に読むフラグが立っているなら要素を先頭に追加、そうでないなら末尾に追加」と処理できます。
（手を動かして試してみるとやっていることが分かりやすいと思います。）
要素を先頭や末尾に追加したい時はdequeを使うのが便利です。

以下が提出コードです。答えを出力するときに、数列をどっちに読むかの処理を忘れないようにしましょう。（\(n\) の偶奇でわかりますが。）

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
	int n;
	cin >> n;
	vector a(n);
	rep(i,n) cin >> a[i];
	
	deque b;
	bool isFor = true;
	rep(i,n){
		if(isFor) b.push_back(a[i]);
		else b.push_front(a[i]);
		isFor = !isFor;
	}

	if(isFor){
		rep(i,b.size()) cout << b[i] << " ";
		cout << endl;
	}else{
		rep(i,b.size()) cout << b[b.size()-1-i] << " ";
		cout << endl;
	}
	return 0;
}