CSAcademy Round #26 : D. Build the Towers

1ミスしたけど割とよい順位でした。
https://csacademy.com/contest/round-26/#task/build-the-towers

問題

0だけで埋められたN要素の数列がある。
数列中0の要素を1つ任意に選択する、という処理を任意回数行える。
要素を選択すると、0は以下の通りに変化する。

• 隣接要素に1がなければ1になる。
• 隣接要素に1があるが2がなければ2になる。その際隣接する1は0になる。
• 隣接要素に1と2あれば3になる。その際隣接要素は0になる。

N要素の数列が与えられるので、上記処理を繰り返し入力の数列を生成するための手順を答えよ。

解法

処理の内容から、1,2,3のそれぞれを構築するのに必要な条件を考える。
大きな数字を作る方が難しいので、先に大きな数字を作り、あとで小さな数字を作るとする。
まず以下は容易にわかる。

• 0以外の要素で同じ要素が連続するものを作ることはできない。
• それ以外の場合、1は任意に作成できる(両隣が0,2,3のいずれかの状態でその要素を選択すればよい)
• 2は両隣のいずれかが1以下の要素を生成すればよいなら生成可能。

まず3を作ることを考える。
3を作るには両隣に1,2を作る必要がある。
1は容易に作成できるが、2を作るには3の隣に2要素の空きが必要である。

よって、まず目的の数列を探索し、2要素以上連続で3以外の数値がある箇所があるか判定する。
それがないなら2を生成できないので条件を満たせない。
条件を満たす場合、*3**という状態を作るためには、0000→1000→1001→1020→0300とすれば他の要素を0としたまま3を生成できる。
あとは遠い順に3を生成しよう。

次に2を生成する。その際、両隣のいずれかに1以下でよい要素があれば、そこに一旦1を作って、本来の目的の2を作ることができる。
最後に1を生成して終了。

int N;
int A[101010];
vector<int> res;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	FOR(i,N-1) if(A[i]==A[i+1] && A[i]!=0) return _P("-1\n");
	if(A[0]==3 || A[N-1]==3) return _P("-1\n");
	
	if(*max_element(A,A+N)==3) {
		FOR(i,N-1) if(A[i]!=3 && A[i+1]!=3) {
			FOR(j,i) if(A[j]==3) {
				res.push_back(j-1);
				res.push_back(j+2);
				res.push_back(j+1);
				res.push_back(j);
			}
			for(j=N-1;j>i;j--) if(A[j]==3) {
				res.push_back(j+1);
				res.push_back(j-2);
				res.push_back(j-1);
				res.push_back(j);
			}
			break;
		}
		if(i==N-1) return _P("-1\n");
	}
	FOR(i,N) if(A[i]==2) {
		if(i&&A[i-1]<=1) {
			res.push_back(i-1);
			res.push_back(i);
		}
		else if(i<N-1&& A[i+1]<=1){
			res.push_back(i+1);
			res.push_back(i);
		}
		else return _P("-1\n");
	}
	FOR(i,N) if(A[i]==1) res.push_back(i);
	
	_P("%d\n",res.size());
	FOR(i,res.size()) _P("%d%c",res[i]+1,(i==res.size()-1)?'\n':' ');
}

まとめ

なんか変わった問題。