AOJ 0503 - Cup (Part 1)

AOJ

実質初投稿です。
書くネタはほとんどないのですが、以前書いたコードの解説でもしてみようかと思います。
題材はAOJ 0503です。私のお気に入りの問題の一つです。

問題ではコップが使われていますが、このままだと微妙に図で説明しづらいです。
というわけで、問題設定をちょっと変更します。
まず、各コップには一意な番号k (1≦k≦n)が付けられていますが、これを全てn-kという番号に付け替えます。これで、番号は[0,n)に付け替わります。以後、こちらの番号で説明します。
さらに、それぞれの番号に対し、円盤を対応付けます。このとき、0番の円盤が一番小さく、n-1番の円盤が一番大きくなるようにします。
ちょっと分かりにくいので、図で説明します。問題の入力例2に対応するのが図1です。コップで表したのが上半分で、さらに番号を付け替えて円盤で表したのが下半分です*1。これはどう見てもハノイの塔ですね*2。
これまた説明のために、それぞれの杭に#0～#2の番号を付けておきます。なお、この番号および杭は、以後面倒なので省略します。
f:id:climpet:20130101130131p:plain
ちなみに、n=4の場合の完成形は図2(もしくはこれを左右反転させたもの)です。
f:id:climpet:20130101130136p:plain
では、解法を説明します。この問題はJOIの過去問で、公式で解説も出ていますが、そのやり方とはやや異なるようです。漸化式？なにそれおいしいの？
この問題は、初期状態が与えられていて、最終状態(#0または#2に集める)にするまでのステップ数を答えるものです。これを逆に考えて、最終状態から初期状態にするまでのステップ数でも同じになるはずです。なのでここでは、全円盤が#0に集まった状態から、初期状態にするまでのステップ数を考えることにします。#2については後述します。
さらにこの問題をよく考えると、番号の大きい円盤*3から順に位置を確定させていくような感じにせざるをえません*4。
というわけで、i番の円盤を#0から目的の場所に移動させるためのステップ数、およびそのときの他の円盤への影響を考えてみます。

  • i番の円盤を#0から#0に移動させる場合
    • 何もしないでいいです
  • i番の円盤を#0から#1に移動させる場合
    • まず、0～i-1の円盤が邪魔なので、これらを一旦#2に移動させる必要があります。これには3^i-1ステップかかります*5。さらにその後、i番を#0から#1に移動させるため、全部で3^iステップ要することが分かります。このとき、0～i-1番は全部#2に移動します。この結果を図3に示します。
  • i番の円盤を#0から#2に移動させる場合
    • 「#0から#1」の移動の後、さらに「#1から#2」の移動を行います。後者については、0～i-1番を#2から#0に移し(3^i-1ステップ)、さらにi番を#1から#2に移します。結果として、2\times 3^iステップかかります。またこの後、0～i-1番は#0にあります。この結果を図4に示します。

f:id:climpet:20130101130141p:plain
f:id:climpet:20130101130149p:plain
以上の考察から、次のようにすれば全体のステップ数が求まることが分かります。

  1. 全部の円盤が#0にあると仮定する。なお、この位置をpとおくことにする(すなわちp=0)。
  2. i←n-1 とする。
  3. i≧0 の間、以下を繰り返す。
    1. i番目の円盤を移動させる距離d(同じ杭なら0、隣の杭なら1、それ以外は2)を求める。
    2. d\times 3^iをステップ数に加算
    3. dが1なら、0～i-1番の円盤を反対側に移動させる。すなわち、p←2-pとする。
    4. i←i-1とする。

これにより求まったステップ数をxとおくことにします。

では次に、全円盤が#2にあるとした場合のステップ数yを求めます。これとxのうち、小さいほうが答えとなります。
これは、pの初期値を2に変えれば、同様に求めることができます。しかしここでは、次のようにして求めることにします。
それぞれの円盤は#0,#1,#2の3通りの位置が考えられるため、この問題全体の状態数は3^nステップです。一方、全円盤を#0から#2に移動させるためのステップ数は、実は3^n-1ステップとなります。すなわち、全円盤を#0から#2に移動させる場合、その間に全状態を経由していることが分かります。従って、y=3^n-1-xが成り立ちます(図5参照)。
あとは、min{x,y}とmを比較し、mを超えていなければその値を、超えていれば-1を出力するだけです。
f:id:climpet:20130101125748p:plain
というわけで、やっとソースコードです。

#include <stdio.h>
#include <stdlib.h>

int main(void){
	int pow3[16], c[16];
	int n, m, i, j, k, d, x, y, p;

	pow3[0] = 1;
	for(i = 1; i <= 15; ++i){
		pow3[i] = pow3[i-1] * 3;
	}

	while(scanf("%d%d", &n, &m), n){
		for(i = 0; i < 3; ++i){
			for(scanf("%d", &j); j > 0; --j){
				scanf("%d", &k);
				c[n-k] = i;	/* 番号付け替え */
			}
		}

		p = 0;
		x = 0;
		for(i = n - 1; i >= 0; --i){
			d = abs(p - c[i]);
			x += pow3[i] * d;
			if(d == 1){
				p = 2 - p;	/* 反対側に移動 */
			}
		}

		y = pow3[n] - 1 - x;
		if(x > y){
			x = y;
		}
		printf("%d\n", x > m ? -1 : x);
	}
	return 0;
}

(Part 2に続く予定)

*1:これらの図は、画像作成ソフトExcelを用いて作成されました

*2:ただし、各円盤は隣の杭にしか動かせないという制約付きです

*3:コップの番号で言えば小さいもの

*4:ここらへん日本語として変な気がする

*5:これは漸化式を立てれば証明できますが、割愛します