Code Formula 2014 本選 : G - ノイハの塔

方針は割とすぐ立った。
http://code-formula-2014-final.contest.atcoder.jp/tasks/code_formula_2014_final_g

問題

ハノイの塔と類似したルールのゲームだが、小さな円盤の上に大きな円盤を乗せてもよい、というルールを追加したゲームを考える。
初期状態では、N個の大きさの異なる円盤が１つ目の杭に刺さっており、その順番が与えられる。

これらを円盤を１個ずつ動かし、最終的に１つの杭にすべての円盤が下から大きい順に積み重なるようにしたい。
動かし方の手順を答えよ。

解法

二分探索の要領で半分ずつ処理していく。

• 対象の円盤群が、すでに下から大きい順に並んでいる。
  • すでに１番の杭に刺さっているなら終了
  • ２番または３番の杭にささっているなら、一度逆の３番または２番に全部動かし、再度１番に動かす。
• 対象の円盤群が、下から小さい順に並んでいる。
  • ２番または３番の杭にささっているなら、それらを１番の杭に動かす。
  • １番の杭に刺さっているなら、全部を１番→２番→３番→１番と動かすと上下逆転できる。
• そのどちらでもない、すなわち昇順にも降順にも綺麗にならんでいない。
  • この場合半分ずつ処理する。
    • 今の杭が１番なら、大きい半分を２番に、小さい半分を３番に振り分ける。
    • 今の杭が２番なら、大きい半分を１番に、小さい半分を３番に振り分ける。
    • 今の杭が３番なら、大きい半分を１番に、小さい半分を２番に振り分ける。
  • その後、大きい半分を再帰的に処理し、小さい半分を再帰的に処理する。

上記手順では、基本的に小さな円盤は２番・３番に集まるので、大きな円盤を大きい順に１番に積むようにすると小さな円盤が邪魔にならない。
最終的にすべての円盤は１番に集まる。

以下のコードではdequeueを使って杭の情報を管理する。
基本的にはstackのようにpop/pushするだけだが、dequeは添え字を使ったアクセスができて便利。

int N;
deque<int> D[3];
vector<pair<int,int> > R;

void dodo(int l,int r,int p) {
	bool same,rev;
	int i,n,S,sp;
	
	if(l>=r) return;
	S=D[p].size();
	sp=r-l;
	same=(D[p][S-sp]==l);
	rev=(D[p][S-sp]==r-1);
	FOR(i,r-l-1) {
		if(D[p][S-sp+i]+1!=D[p][S-sp+i+1]) same=false;
		if(D[p][S-sp+i]-1!=D[p][S-sp+i+1]) rev=false;
	}
	
	if(same) {
		FOR(i,r-l) D[p].pop_back();
		if(p!=0) {
			n=3-p;
			FOR(i,r-l) R.push_back(make_pair(p,n));
			FOR(i,r-l) R.push_back(make_pair(n,0));
		}
		return;
	}
	if(rev) {
		FOR(i,r-l) D[p].pop_back();
		if(p!=0) {
			FOR(i,r-l) R.push_back(make_pair(p,0));
		}
		else {
			FOR(i,r-l) R.push_back(make_pair(0,1));
			FOR(i,r-l) R.push_back(make_pair(1,2));
			FOR(i,r-l) R.push_back(make_pair(2,0));
		}
		return;
	}
	
	int sm,la;
	if(p==0) sm=1,la=2;
	if(p==1) sm=0,la=2;
	if(p==2) sm=0,la=1;
	FOR(i,r-l) {
		int v=D[p].back();
		D[p].pop_back();
		if(v<(r+l)/2) D[sm].push_back(v), R.push_back(make_pair(p,sm));
		else D[la].push_back(v), R.push_back(make_pair(p,la));
	}
	dodo(l,(r+l)/2,sm);
	dodo((r+l)/2,r,la);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, D[0].push_back(N-x);
	dodo(0,N,0);
	
	_P("%d\n",R.size());
	FOR(i,R.size()) _P("%d %d\n",R[i].first+1,R[i].second+1);
}

まとめ

解法があっさり思いついたこともあって楽しめた。