Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-07SRM482(DIV1)

HanoiGoodAndBad

|  HanoiGoodAndBad - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  HanoiGoodAndBad - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10858

この問題は2つのパートに分かれている。

  • Daveが手数分動かした際の輪っかの状態を作る
  • Earlがその状態に辿りつくまでの手数を求める

Daveが手数分動かした際の状態を作る

問題文中の solve_Dave(N) を実行するのに 2^N - 1 ターンかかることを考えると、

2^(N-1)-1 ターンあれば 上からN-1個の輪っかをsourceからspareに移すことができ、

余ったターンのうち、

  • 1ターンは 上からN個目の輪っかをtargetに移す
  • 2^(N-1)-1ターンは再度solve_Dave

に使える。

このとき、最初に移す輪っかの数の偶奇により、spareとtargetが入れ替わるので注意する。

再帰関数を愚直に実装した。残り手数が0になったところで終了する。

Earlが特定の状態に辿りつくまでの手数を求める

一番下の輪っかから順番に考えていけばOK。求める状態の輪っかの位置が、

  • sourceにあるなら経過ターン数は0
  • spareにあるなら経過ターン数は (3^(N-1) - 1) + 1
    • 上にあるN - 1個の輪っかを target に移すのに 3^(N-1) - 1 ターン
    • 自身を spareに移すのに 1ターン
    • この状態で、上の輪っかについて考える。sourceとtargetが入れ替わるのことに注意する
  • targetにあるなら経過ターン数は (3^(N-1) * 2 - 2) + 2
    • 上にあるN - 1個の輪っかを sourceからtarget、targetからsourceに移すのに 3^(N-1) * 2 - 2 ターン
    • 自身を sourceからspare、spareからtargetに移すのに 2ターン
    • この状態で、上の輪っかについて考える。

public class HanoiGoodAndBad {

	public int[] state;

	public int doEarl(int N, int source, int target, int spare) {
		if (N == 0) {
			return 0;
		}
		if (state[N-1] == spare) {
			return (int)(Math.pow(3, N-1)) + doEarl(N-1, target, source, spare);
		}
		if (state[N-1] == target) {
			return (int)(Math.pow(3, N-1) * 2) + doEarl(N-1, source, target, spare);
		}
		return doEarl(N-1, source, target, spare);
	}

	public void doDave(int N, int t, int source, int target, int spare) {
		int count = 1;
		int canmove = 0;

		for (int i = 1 ; i <= N - 1 ; i++) {
			count = (int)Math.pow(2, i) - 1;
			if (t <= count) {
				break;
			}
			canmove = i;
		}

		for (int i = N - 1 ; i > canmove ; i--) {
			int sp = target;
			target = spare;
			spare = sp;
		}

		t -= ((int)Math.pow(2, canmove) - 1);
		for (int i = 0 ; i < canmove ; i++) {
			state[i] = spare;
		}
		if (t == 0) {
			return;
		}

		t--;
		state[canmove] = target;
		if (t == 0) {
			return;
		}
		doDave(canmove, t, spare, target, source);
	}

	public int moves(int N, int Dave) {
		state = new int[N];
		doDave(N, Dave, 0, 2, 1);
		return doEarl(N, 0, 2, 1);
	}

}