Dice I, II, III, IV [ AIZU ONLINE JUDGE ITP1_11 ] - 文系プログラマーのプログラミング備忘録

AIZU ONLINE JUDGE の Introduction to Programming I の最後に構えている問題、Dice I, II, III, IV を全部まとめて解いてしまいたいと思います。一見すると何やらややこしそうですが、実際にはオブジェクト指向・全探索と、プログラミングの基本が詰まっている良問だと思います。

Dice I

judge.u-aizu.ac.jp

問題文に書かれているように、サイコロ（とサイコロをそれぞれの方向に転がすメソッド）を実装して解答します。
以降の3問では、スペース節約のためにコードから Dice クラスを省略しています。

void solve (FastScanner in, PrintWriter out, Methods ms) {
	
	Dice d = new Dice(in.nextInt(), in.nextInt(), in.nextInt(),
						in.nextInt(), in.nextInt(), in.nextInt());
	
	char[] a = in.next().toCharArray();
	
	for (int i=0; i<a.length; i++) {
		if (a[i] == 'N') d.turnN();
		else if (a[i] == 'E') d.turnE();
		else if (a[i] == 'S') d.turnS();
		else if (a[i] == 'W') d.turnW();
	}
	
	out.println(d.U);

}

static class Dice {

	int U, D, N, E, S, W, temp;

	Dice (int u, int s, int e, int w, int n, int d) {
		U = u; S = s; E = e; W = w; N = n; D = d;
	}

	void turnN () {
		temp = D;
		D = N; N = U; U = S; S = temp;
	}
	void turnE () {
		temp = W;
		W = D; D = E; E = U; U = temp;
	}
	void turnS () {
		temp = D;
		D = S; S = U; U = N; N = temp;
	}
	void turnW () {
		temp = W;
		W = U; U = E; E = D; D = temp;
	}
	void turnRight () {
		temp = W;
		W = S; S = E; E = N; N = temp;
	}
	void turnLeft () {
		temp = W;
		W = N; N = E; E = S; S = temp;
	}
}

Dice II

judge.u-aizu.ac.jp

求めたいのは「上面が u 、前面が s のときの右面の数字」です。
よって、サイコロの向きのパターンを全て列挙することを考えます。

さまざまなやり方があるかと思いますが、以下のコードでおこなっているのは、上面を固定し、サイコロを右に回すことを繰り返す方法です。

上面のパターンはいうまでもなく 6通りです。ある上面について、側面のパターンは 4通り、下面のパターンは 1通りです。すなわち、サイコロの向きのパターンは高々 24通りであることが分かります。Q は 1<=Q<=24 なので、十分間に合います。

この方法でサイコロの向きのパターンを順に列挙していき、もし上面が u 、下面が s になるようなパターンがあれば、そのときの右面を出力することでこの問題を解くことができます。

void solve (FastScanner in, PrintWriter out, Methods ms) {
	
	Dice d = new Dice(in.nextInt(), in.nextInt(), in.nextInt(),
						in.nextInt(), in.nextInt(), in.nextInt());
	
	int n = in.nextInt();
	
	for (int i=0; i<n; i++) {
		
		int u = in.nextInt(), s = in.nextInt();
		Dice temp = new Dice(d.U, d.S, d.E, d.W, d.N, d.D);
		
		loop : for (int j=0; j<6; j++) {
			
			//各面を上面に固定してから
			for (int k=0; k<pattern[j].length(); k++) {
				if (pattern[j].charAt(k) == 'N') temp.turnN();
				else if (pattern[j].charAt(k) == 'E') temp.turnE();
			}
			
			//右に回転させる
			for (int k=0; k<4; k++) {
				temp.turnRight();
				if (temp.U == u && temp.S == s) {
					out.println(temp.E);
					break loop;
				}
			}
			
		}
	}
	
}

//U, S, D, N, W, E をこの順番で上面にするための回転パターン
static String[] pattern = {"", "N", "N", "N", "E", "EE"};

Dice III

judge.u-aizu.ac.jp

2つのサイコロが同一のものであるかを判定する問題です。

1つ目のサイコロを d1 、2つ目のサイコロを d2 とします。

Dice II と同じ方法で d2 の向きのパターンを全て列挙しつつ、いずれかのパターンが d1 と一致すれば Yes 、どのパターンも一致しなければ No を出力することでこの問題を解くことができます。

なお、Dice IV では複数のサイコロの一致を判定する必要があるため、上記の処理はこの問題の時点でメソッド化しています。

void solve (FastScanner in, PrintWriter out, Methods ms) {
	
	Dice d1 = new Dice(in.nextInt(), in.nextInt(), in.nextInt(),
						in.nextInt(), in.nextInt(), in.nextInt());
	
	Dice d2 = new Dice(in.nextInt(), in.nextInt(), in.nextInt(),
						in.nextInt(), in.nextInt(), in.nextInt());
	
	out.println(isSameDice(d1, d2)==true? "Yes" : "No");
	
}

static boolean isSameDice (Dice d1, Dice d2) {

	for (int i=0; i<6; i++) {

		for (int k=0; k<pattern[i].length(); k++) {
			if (pattern[i].charAt(k) == 'N') d2.turnN();
			else if (pattern[i].charAt(k) == 'E') d2.turnE();
		}

		for (int j=0; j<4; j++) {
			d2.turnRight();
			if (d1.U==d2.U && d1.S==d2.S && d1.E==d2.E &&
				d1.W==d2.W && d1.N==d2.N && d1.D==d2.D)
			{
				return true;
			}
		}

	}

	return false;
	
}

static String[] pattern = {"", "N", "N", "N", "E", "EE"};

Dice IV

judge.u-aizu.ac.jp

与えられた n 個のサイコロが全て異なるかどうかを判定する問題です。

上記の関数を使って、nC2 個の全てのサイコロの組み合わせについて異なるかどうかを調べればよいです。
計算量は n が最大（n = 100）のとき 100C2 * 24 = 約120,000 となり、十分間に合います。

void solve (FastScanner in, PrintWriter out, Methods ms) {
	
	int n = in.nextInt();
	Dice[] d = new Dice[n];
	for (int i=0; i<n; i++) {
		d[i] = new Dice(in.nextInt(), in.nextInt(), in.nextInt(),
						in.nextInt(), in.nextInt(), in.nextInt());
	}

	for (int i=0; i<n-1; i++) {
		for (int j=i+1; j<n; j++) {
			if (isSameDice(d[i], d[j]) == true) {
				out.println("No");
				return;
			}
		}
	}

	out.println("Yes");

}

static boolean isSameDice (Dice d1, Dice d2) {

	for (int i=0; i<6; i++) {

		for (int k=0; k<pattern[i].length(); k++) {
			if (pattern[i].charAt(k) == 'N') d2.turnN();
			else if (pattern[i].charAt(k) == 'E') d2.turnE();
		}

		for (int j=0; j<4; j++) {
			d2.turnRight();
			if (d1.U==d2.U && d1.S==d2.S && d1.E==d2.E &&
				d1.W==d2.W && d1.N==d2.N && d1.D==d2.D)
			{
				return true;
			}
		}

	}

	return false;
	
}

static String[] pattern = {"", "N", "N", "N", "E", "EE"};