Dice Puzzle(AOJ No.0171), Doctor's Research Rooms(AOJ No.0172), Haunted House(AOJ No.0173), Badminton(AOJ No.0174), A King in Hawaii(AOJ No.0175), What Color?(AOJ No.0176), Distance Between Two Cities(AOJ No.0177), TETORIS(AOJ No.0178), Mysterious Worm(AO

Dice Puzzle(AOJ No.0171)

アルファベットが書かれたサイコロが８つ与えられ、それらを全て使って立方体を作ることを考える。
立方体を作る際、サイコロが接している面は同じアルファベットの大文字と小文字でなければならない。
与えられた８つのサイコロで立方体を作ることができるかを答える。
制約
１つのサイコロの面は全て異なる文字(同じアルファベットの大文字と小文字は その限りではない）

アルゴリズム

DFS。サイコロ１つの状態数は24パターンなので、全状態数はあるが、サイコロの配置条件が厳しいので、置けなくなった時点で枝刈りすれば、だいぶ速く終わりそう。
こういう場合の計算量の見積もりができない...orz
やるだけだが非常にめんどい

コード

enum便利

import java.util.*;
public class aoj0171 {
	static final int N = 4, M = 8;
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		String s;
		while(!(s = stdin.nextLine()).equals("0")){
			dice[0] = generateAllPatern(s);
			P = dice[0].length; //P=24
			for(int i = 1; i < M; i++) dice[i] = generateAllPatern(stdin.nextLine());
			Arrays.fill(used, false);
			System.out.println(DFS(0) ? "YES" : "NO");
		}
	}
	static Character[] stringToCharacterArray(String s){
		Character[] ret = new Character[s.length()];
		for(int i = 0; i < s.length(); ++i) ret[i] = s.charAt(i);
		return ret;
	}
	@SuppressWarnings("unchecked") static Cube<Character>[] generateAllPatern(String s){
		Set<Cube<Character>> all = new Cube<Character>(stringToCharacterArray(s)).generateAllPattern();
		return (Cube<Character>[]) all.toArray(new Cube[all.size()]);
	}
	@SuppressWarnings("unchecked") static Cube<Character> dice[][] = new Cube[M][];
	static boolean[] used = new boolean[M];
	static int P;
	static int[] order = new int[M], porder = new int[M];
	static boolean DFS(int c){
		if(c == M) return true;
		for(int i = 0; i < M; ++i){
			if(used[i]) continue;
			order[c] = i; used[i] = true;
			for(int j = 0; j < P; ++j){
				porder[c] = j;
				if(!check(c)) continue;
				if(DFS(c+1)) return true;
			}
			used[i] = false;
		}
		return false;
	}
	static final boolean check(int c){
		switch(c){
		case 0: return	true;
		case 1: return	match(target(1).get(Surface.LEFT), target(0).get(Surface.RIGHT));
		case 2: return	match(target(2).get(Surface.FRONT), target(0).get(Surface.BACK));
		case 3: return	match(target(3).get(Surface.LEFT), target(2).get(Surface.RIGHT)) &&
						match(target(3).get(Surface.FRONT), target(1).get(Surface.BACK));
		case 4: return	match(target(4).get(Surface.TOP), target(0).get(Surface.BOTTOM));
		case 5: return 	match(target(5).get(Surface.LEFT), target(4).get(Surface.RIGHT)) &&
						match(target(5).get(Surface.TOP), target(1).get(Surface.BOTTOM));
		case 6: return	match(target(6).get(Surface.FRONT), target(4).get(Surface.BACK)) &&
						match(target(6).get(Surface.TOP), target(2).get(Surface.BOTTOM));
		case 7:	return 	match(target(7).get(Surface.LEFT), target(6).get(Surface.RIGHT)) &&
						match(target(7).get(Surface.FRONT), target(5).get(Surface.BACK)) &&
						match(target(7).get(Surface.TOP), target(3).get(Surface.BOTTOM));
		}
		assert false; //ここには来ないはず
		return false;
	}
	static final boolean match(char a, char b){ return Character.toUpperCase(a)==Character.toUpperCase(b) && a!=b; }
	static final Cube<Character> target(int c){ return dice[order[c]][porder[c]]; }
	static enum Surface{TOP, FRONT, RIGHT, LEFT, BACK, BOTTOM};
	@SuppressWarnings("unchecked") public static class Cube <T>{
		static final int N = 6, M = 4;
		private T[] id;
		public final T get(Surface s){ return id[s.ordinal()]; }
		public Cube(T[] c){ id = (T[]) new Object[N]; System.arraycopy(c, 0, id, 0, N); }
		public Cube(Cube<T> c){ id = (T[]) new Object[N]; System.arraycopy(c.id, 0, id, 0, N); }
		public final void rotateXZ() { rotate(Surface.TOP, Surface.FRONT, Surface.BOTTOM, Surface.BACK); }
		public final void rotateYZ() { rotate(Surface.TOP, Surface.RIGHT, Surface.BOTTOM, Surface.LEFT); }
		public final void rotateXY() { rotate(Surface.FRONT, Surface.LEFT, Surface.BACK, Surface.RIGHT); }
		private final void rotate(Surface a, Surface b, Surface c, Surface d) { //abcd->bcda
			T tmp = id[a.ordinal()];
			id[a.ordinal()] = id[b.ordinal()];
			id[b.ordinal()] = id[c.ordinal()];
			id[c.ordinal()] = id[d.ordinal()];
			id[d.ordinal()] = tmp;
		}
		public Set<Cube<T>> generateAllPattern(){
			Set<Cube<T>> ret = new HashSet<Cube<T>>(N*M);
			for (int k = 0; k < N; ++k){
				for (int i = 0; i < M; rotateXY(), ++i) ret.add(new Cube<T>(this));
				if((k&1)==0) rotateXZ(); else rotateYZ();
			}
			return ret;
		}
		@Override public String toString() {
			StringBuilder sb = new StringBuilder();
			for(Surface s : Surface.values()) sb.append(id[s.ordinal()]);
			return sb.toString();
		}
		@Override public boolean equals(Object o) {
			if(!(o instanceof Cube<?>))return false;
			Cube<T> d = (Cube<T>)o;
			for(Surface f : Surface.values()) if(!id[f.ordinal()].equals(d.id[f.ordinal()])) return false;
			return true;
		}
		@Override public int hashCode() {
			int hash = 17;
			for(Surface f : Surface.values()) hash += 31*hash+id[f.ordinal()].hashCode();
			return hash;
		}
	}
}

Doctor's Research Rooms(AOJ No.0172)

１からnの番号が振られた部屋の電気の点灯状態と、各部屋から消灯・点灯できるスイッチの情報および部屋の隣接情報が与えられる。
電気の付いていない部屋には立ち入れない（自分がいる部屋の電気を消すこともできない）。
１からnの部屋にたどり着けるかどうかを答える。１からnの部屋にたどり着ける場合、1からn-1の部屋の電気を消灯することができるなら、そのステップ数と、行動(移動、スイッチオン、オフ)を答える。複数のスイッチを押す場合は、部屋番号の小さい順で出力する。
制約

アルゴリズム

明らかなBFS. 現在位置と点灯状態をあわせると状態数はなので余裕。
ゴールした時点で直ちに探索終了してしまうと、1からn-1の部屋の電気を消灯できるかどうか分からないので終了条件は「現在位置がn」かつ「1からn-1の部屋が消灯している」。各部屋のスイッチ情報はあらかじめソートしておくと、小さい順で出力されるようになっているはず。

コード

import java.util.*;
public class aoj0172 {
	static final Scanner stdin = new Scanner(System.in);
	enum Data{ POS, STATE, COMMAND } enum Command{ MOVE, ON, OFF } enum Result{ PERFECT, NOT_PERFECT, HELP }
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt(), m = stdin.nextInt();
			if((n|m) == 0) break;
			@SuppressWarnings("unchecked") 
			ArrayList<Integer>[] adjList = new ArrayList[n], light = new ArrayList[n];
			for(int i = 0; i < n; ++i){
				adjList[i] = new ArrayList<Integer>();
				light[i] = new ArrayList<Integer>();
			}
			for(int i = 0; i < m; ++i){
				int s = stdin.nextInt()-1, t = stdin.nextInt()-1;
				adjList[s].add(t); adjList[t].add(s);
			}
			int S = 0;
			for(int i = 0; i < n; ++i) if(stdin.nextInt() == 1) S |= (1<<i);
			for(int i = 0; i < n; ++i){
				int k = stdin.nextInt();
				while(k-- > 0) light[i].add(stdin.nextInt()-1);
				Collections.sort(light[i]);
			}
			switch(BFS(adjList, light, S)){
				case PERFECT:
					System.out.println(String.format("You can go home in %d steps.", 
							(command.length-Data.COMMAND.ordinal())/2));
					for(int i = Data.COMMAND.ordinal(); i < command.length; i+=2)
						System.out.println((String.format("%s room %d.",
							(command[i] == Command.MOVE.ordinal()) ? "Move to" : 
							(command[i] == Command.ON.ordinal()) ? "Switch on" : "Switch off", 
							command[i+1]+1)));
					break;
				case NOT_PERFECT:
					System.out.println("You can not switch off all lights."); break;
				case HELP:
					System.out.println("Help me!");
			}
		}
	}
	static int[] command;
	static boolean[][] visited;
	static Result BFS(ArrayList<Integer>[] adjList, ArrayList<Integer>[] light, int S){
		Result ret = Result.HELP;
		int n = adjList.length;
		visited = new boolean[n][1<<n];
		for(int i = 0; i < n; ++i) Arrays.fill(visited[i], false);
		visited[0][S] = true;
		Queue<int[]> q = new LinkedList<int[]>(); q.add(new int[]{0, S});
		while(!q.isEmpty()){
			int[] e = q.poll(); int pos = e[Data.POS.ordinal()], state = e[Data.STATE.ordinal()];
			if((state & (1<<pos)) == 0) continue; //今いる部屋の明かりが消えている
			if(pos == n-1 && check(n, state)){ command = e; return Result.PERFECT; }
			if(pos == n-1) ret = Result.NOT_PERFECT;
			for(Integer i: adjList[pos]){
				int nextData[] = new int[e.length+2]; System.arraycopy(e, 0, nextData, 0, e.length);
				nextData[e.length] = Command.MOVE.ordinal();
				nextData[e.length+1] = i;
				nextData[Data.POS.ordinal()] = i;
				if(visited[i][state]) continue;
				visited[i][state] = true;
				q.add(nextData);
			}
			for(Integer i: light[pos]){
				int nextData[] = new int[e.length+2]; System.arraycopy(e, 0, nextData, 0, e.length);
				int bit = (1<<i);
				nextData[e.length] = (state & bit) != 0 ? Command.OFF.ordinal() : Command.ON.ordinal();
				nextData[e.length+1] = i;
				nextData[Data.STATE.ordinal()] = (state & bit) != 0 ? (state & (~bit)) : (state | bit);
				if(visited[pos][nextData[Data.STATE.ordinal()]]) continue;
				visited[pos][nextData[Data.STATE.ordinal()]] = true;
				q.add(nextData);
			}
		}
		return ret;
	}
	static final boolean check(int n, int state){
		for(int i = 0; i < n-1; ++i) if(((state>>i)&1) == 1) return false;
		return true;
	}
}

Haunted House(AOJ No.0173)

(s,a,b)が与えられ(s,a+b,200a+300b)と答える

コード

import java.util.*;
public class aoj0173 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int i = 9;
		while(i-- > 0){
			String s = stdin.next(); int a = stdin.nextInt(), b = stdin.nextInt();
			System.out.println(s + " " + (a+b) + " " + (200*a+300*b));
		}
	}
}

Badminton(AOJ No.0174)

• 3ゲームを行います。
• 11点を先取した人が、そのゲームの勝者となります。
• 第1ゲームの最初のサーブはA君から始まりますが、次のサーブは直前のポイントを取った人が行います。
• 第2ゲーム、第3ゲームは前のゲームを取った人が最初のサーブを行います。
• 10-10 になって以降は 2 点差をつけた人が勝者となります。

サーブを打った人の情報が与えられたとき、各ゲーム毎の点数を答える。

コード

３ゲームという記述を読みと落としてた...

import java.util.*;
public class aoj0174 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int s = 0, game = 2;
		int[] d = new int[2];
		String str;
		while(!(str=stdin.nextLine()).equals("0")){
			if((game = (game + 1)%3) == 0) s = 0;
			Arrays.fill(d, 0);
			for(char c : str.toCharArray()) if(c == 'A') d[0]++; else d[1]++;
			d[s]--;
			if(d[0] > d[1]){ d[0]++; s = 0; }
			else{ d[1]++; s = 1; }
			System.out.println(d[0] + " " + d[1]);
		}
	}
}

A King in Hawaii(AOJ No.0175)

10進数を４進数にしる

コード

import java.util.*;
public class aoj0175 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int a;
		while((a = stdin.nextInt()) != -1) System.out.println(Integer.toString(a, 4));
	}
}

What Color?(AOJ No.0176)

16進数でRGBが与えられるので、下の表から一番近い色を答える。

color	R	G	B
black	00	00	00
blue	00	00	ff
lime	00	ff	00
aqua	00	ff	ff
red	ff	00	00
fuchsia	ff	00	ff
yellow	ff	ff	00
white	ff	ff	ff

コード

import java.util.*;
public class aoj0176 {
	static final Scanner stdin = new Scanner(System.in);
	static final int color[][] = { {0, 0, 0}, {0, 0, 255}, {0, 255,0}, {0, 255,255}, {255, 0, 0}, {255, 0,255}, {255,255,0}, {255,255,255} };
	static final String name[] = {"black", "blue", "lime", "aqua", "red", "fuchsia", "yellow", "white"};
	static final int dist(int[] a, int[] b){
		int ret = 0;
		for(int i = 0; i < 3; ++i) ret += (a[i]-b[i])*(a[i]-b[i]);
		return ret;
	}
	public static void main(String[] args) {
		String s;
		while(!(s = stdin.nextLine()).equals("0")){
			int c = -1, m = Integer.MAX_VALUE;
			for(int i = 0; i < color.length; ++i){
				int d = dist(color[i], new int[]{ Integer.parseInt(s.substring(1, 3), 16), Integer.parseInt(s.substring(3, 5), 16), Integer.parseInt(s.substring(5, 7), 16) });
				if(d < m){ c = i; m = d; }
			}
			System.out.println(name[c]);
		}
	}
}

Distance Between Two Cities(AOJ No.0177)

(緯度, 経度)の形式で地球上の２点がが与えられる。
地球の半径を[km]としたとき、２点間の(球面)距離を求める。
ただし、緯度は, 緯度はで与えられる。

アルゴリズム

計算するだけだが、数学とかでよく使う３次元の極座標系 - Wikipediaはがz軸からの角度なので注意する。

を使って、を求める。
これらの位置ベクトルのなす角をとすると内積を使って、で求まる。
弧度法[rad]の定義から球面距離は、
整理すると、

コード

import java.util.*;
public class aoj0177 {
	static final Scanner stdin = new Scanner(System.in);
	static final double rad(double d){ return d*Math.PI/180; }
	static final double r = 6378.1;
	public static void main(String[] args) {
		double[] theta = new double[2], phi = new double[2];
		while(true){
			theta[0] = stdin.nextDouble(); phi[0] = stdin.nextDouble();
			theta[1] = stdin.nextDouble(); phi[1] = stdin.nextDouble();
			if(theta[0] == -1 && phi[0] == -1 && theta[1] == -1 && phi[1] == -1) break;
			System.out.println( (int)(r*Math.acos(
					Math.cos(rad(theta[0]))*Math.cos(rad(phi[0]))*Math.cos(rad(theta[1]))*Math.cos(rad(phi[1])) + 
					Math.cos(rad(theta[0]))*Math.sin(rad(phi[0]))*Math.cos(rad(theta[1]))*Math.sin(rad(phi[1])) +
					Math.sin(rad(theta[0]))*Math.sin(rad(theta[1]))
					)+0.5)
			);
		}
	}
}

TETORIS(AOJ No.0178)

しょぼいテトリス。n個ブロックが落ちてきて、最後に残っているブロックの数を答える。
枠のサイズは縦∞、横5.
落ちてくるブロックは一直線の物しか無く(d,p,q)で表される。
d=1 なら横、d=2なら縦。pはブロックの長さ。qは左端のブロックの位置。
制約

コード

なんか無駄が多い。
q=2, p=5 のブロックが同じ位置に5000個落ちてきたときを考慮して、枠ノサイズは縦5001, 横5のサイズはにした。

import java.util.*;
public class aoj0178 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 5, H = 5001;
	static final BitSet[] map = new BitSet[H];
	public static void main(String[] args) {
		for(int i = 0; i < H; ++i) map[i] = new BitSet(N);
		int n;
		while((n = stdin.nextInt()) != 0){
			for(int i = 0; i < H; ++i) map[i].clear();
			for(int i = 0; i < n; ++i){
				int d = stdin.nextInt(), p = stdin.nextInt(), q = stdin.nextInt()-1;
				drop(d, p, q);	
			}
			int ans = 0;
			for(int i = 0; i < H; ++i) ans += map[i].cardinality();
			System.out.println(ans);
		}
	}
	static void drop(int d, int p, int q){
		int h = 1, y = H - 1, w = p; //横
		if(d == 2){ h = p; y = H - p; w = 1; } //縦
		y--; //一番上は空白
		while(y != 0 && downCheck(y,w,q)) y--; //落とせるところまで落とす
		for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) map[y+i].set(q+j); //セット
		for(int i = 0; i < h; ++i){
			if(map[y].cardinality() == N)
				for(int j = y+1; j < H; ++j){ map[j-1].clear(); map[j-1].or(map[j]); } //消してずらす
			else
				++y;
		}
	}
	static boolean downCheck(int y, int w, int q){
		for(int i = 0; i < w; ++i) if(map[y-1].get(q+i)) return false;
		return true;
	}
}

Mysterious Worm(AOJ No.0179)

虫の体節の色の並びが 2以上 10以下のr(赤)、g(緑)、b(青)で与えられる。
1秒毎に、虫の体節の色が変化する。
変化する条件は、隣接する体節が異なる色なら、その部分だけが残りの別の色に変化する。
ただし、変化する場合、変化する体節は常に２個。
与えられた、虫の全体節が同じ色になるのに必要な最低秒数を答える。

コード

明らかにBFS. 無駄にset使い過ぎ。

import java.util.*;
public class aoj0179 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		String s; char temp;
		while(!(s = stdin.nextLine()).equals("0")){
			int n = s.length();
			String ans = "NA";
			Set<String> found = new HashSet<String>(n*n);
			Queue<T> q = new LinkedList<T>();
			q.add(new T(0, s));
			while(!q.isEmpty()){
				T e = q.poll();
				if(e.check()){ ans = e.sec.toString(); break; }
				if(found.contains(e.toString())) continue;
				found.add(e.toString());
				for(int i = 1; i < n; ++i){
					if((temp = check(e.body[i-1], e.body[i])) != ' '){
						T nextT = new T(e);
						nextT.body[i-1] = nextT.body[i] = temp;
						nextT.sec++;
						if(found.contains(nextT.toString())) continue;
						q.add(nextT);
					}
				}
			}
			System.out.println(ans);
		}
	}
	static class T{
		Integer sec;
		char[] body;
		T(Integer sec, String body){ this.sec = sec; this.body = body.toCharArray(); }
		T(T o){ sec = o.sec; body = o.body.clone(); }
		boolean check(){
			char c = body[0];
			for(int i = 1; i < body.length; ++i) if(body[i] != c) return false;
			return true;
		}
		@Override public String toString(){ return new String(body); }
	}
	@SuppressWarnings("serial") static char check(char a, char b){
		if(a == b) return ' ';
		Set<Character> s = new HashSet<Character>(){ {add('r'); add('g'); add('b'); } };
		s.remove(a); s.remove(b);
		return s.iterator().next();
	}
}