UFO Shooting Down Operation(AOJ No.0204), Rock, Paper, Scissors(AOJ No.0205), Next Trip(AOJ No.0206), Block(AOJ No.0207), Room Numbers of a Hospital(AOJ No.208), Scene in a Picture(AOJ No.0209), The Squares(AOJ No.0210)

UFO Shooting Down Operation(AOJ No.0204)

円形のUFO $(x_i, y_i, r_i)$ がN個あり、分速 $v_i$ で原点に向かってくる。
原点からレーザーを発射して、UFOを破壊する。レーザーは無限にのびるが、発射位置(原点)から距離R以内の範囲では、威力が出ずUFOを破壊できない。
初期状態から１分後、原点からR以内に侵入したUFOは見逃し、レーザー以外の手段で破壊するとして、
原点からの距離がRより大きく、最も近いUFOに向かってレーザーを放つ。
これを繰り返して、全てのUFOを処理したとき、レーザー以外の手段で破壊するUFOの数を答える。
制約
$-1000 \leq x_i,y_i \leq 1000$
$0 < R, r_i, v_i \leq 500$
$0 < N \leq 100$

アルゴリズム

レーザー(原点からロックオンしたUFOへ)の正規化方向ベクトルを $\vec{p}$ とし、
巻き添えを食らうかどうかを判定するUFOの位置を $\vec{c}$ , 半径を $r$ とする。
円の方程式でUFOを表現すると、 $|\vec{x}-\vec{c}|=r\rightarrow (\vec{x}-\vec{c})\bullet (\vec{x}-\vec{c})=r^2$
この円と $\vec{p}$ の延長線 $t\vec{p}$ $(t > 0)$ との交点を求める。
$\vec{x}$ に $t\vec{p}$ を代入すると、
$(t\vec{p}-\vec{c})\bullet (t\vec{p}-\vec{c})=r^2$
$\vec{p}\bullet \vec{p}t^2 - 2\vec{p}\bullet \vec{c}t + \vec{c}\bullet \vec{c} - r^2 = 0$
$t$ を解の公式で解くと交点 $t\vec{p}$ が求まる。
実数解なら交点が存在するが、原点からの距離がR以下のところであたっても意味が無いので、
判別式 $\geq 0$ かつ $t > R$ のUFOを破壊してシミュレートすればいい。

コード

初期状態から１分後にレーザーを打ち始めるということに気付かずWAをだしまくった。

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0204 {
	static final Scanner stdin = new Scanner(System.in);
	static final double INF = 1e10;
	public static void main(String[] args) {
		while(true){
			int R = stdin.nextInt(), N = stdin.nextInt();
			if((R|N) == 0) break;
			T[] data = new T[N];
			boolean[] ignore = new boolean[N]; Arrays.fill(ignore, false);
			for(int i = 0; i < N; ++i) {
				data[i] = new T(stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), stdin.nextInt());
				data[i].move();
			}
			int ans = 0;
			while(true){
				double m = INF;
				int mi = -1;
				for(int i = 0; i < N; ++i){
					if(ignore[i]) continue;
					double d = data[i].dist;
					if(d <= R){
						ignore[i] = true;
						ans++;
					} else if(d < m){
						m = d;
						mi = i;
					}
				}
				if(mi == -1) break;

				Point laser = data[mi].c.o.unit();
				for(int i = 0; i < N; ++i){
					if(ignore[i]) continue;
					double a = laser.normsq();
					double b = -2*laser.dot(data[i].c.o);
					double c = data[i].c.o.normsq() - data[i].c.r * data[i].c.r;
					double D = b*b - 4*a*c;
					if(D >= 0){
						double d = Math.sqrt(D);
						double t1 = (-b + d)/(2*a), t2 = (-b - d)/(2*a);
						if(t1 > R || t2 > R) ignore[i] = true;
					}
					data[i].move();
				}
			}
			System.out.println(ans);
		}
	}
	static class T {
		Circle c;
		final Point dv;
		final double v;
		double dist;
		T(int x, int y, int r, int v){
			c = new Circle(x,y,r);
			this.v = v;
			double norm = c.o.norm();
			dv = c.o.mul(-v/norm);
			dist = norm;
		}
		void move(){
			c.o.set(c.o.add(dv));
			dist -= v;
		}
	}
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,y); }
		public final void set(Point p){ this.x = p.x; this.y = p.y; }
		public final double norm(){ return Math.sqrt( normsq() ); }
		public final double normsq(){ return x*x + y*y; }
		public final Point add(Point p){ return new Point( x + p.x, y + p.y ); }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		public final Point mul(double k){ return new Point( k*x, k*y ); }
		public final Point div(double k){ return new Point( x/k, y/k ); }
		public final Point unit(){ return this.div(this.norm()); }
		public final double cross(Point p){ return x * p.y - y * p.x; }
		public final double dot(Point p){ return x * p.x + y * p.y; }
	}
	public static class Circle{
		public final Point o;
		public double r;
		public Circle(double x, double y, double r){ this.o = new Point(x,y); this.r = r; }
	}
}

Rock, Paper, Scissors(AOJ No.0205)

５人でジャンケンしたときの勝敗判定をする

コード

やるだけ、手の種類が1 or 3ならあいこ。

import java.util.*;
public class aoj0205 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 3, M = 5, WIN = 1, LOSE = 2, DRAW = 3;
	public static void main(String[] args) {
		int[] freq = new int[N], data = new int[M];
		while((data[0] = stdin.nextInt()-1) != -1){
			Arrays.fill(freq, 0);
			freq[data[0]]++;
			for(int i = 1; i < M; ++i){
				data[i] = stdin.nextInt()-1;
				freq[data[i]]++;
			}
			int temp = 0, a = -1, b = -1;
			for(int i = 0; i < N; ++i){
				if(freq[i] > 0){
					temp++;
					if(a == -1) a = i;
					else b = i;
				}
			}
			if(temp == 2) if((a+1) != b){ temp = a; a = b; temp = b; }
			for(int d: data)
				System.out.println(temp == 2 ? (d == a ? WIN : LOSE) : DRAW);
		}
	}
}

Next Trip(AOJ No.0206)

要するに数列 $a_i$ $(1\leq i \leq 12)$ 、 $L$ が与えられて、
$\sum_{i=1}^x a_i \geq L$ となる最小の $x$ を求める。

コード

import java.util.*;
public class aoj0206 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int L, sum, N = 12, i, ans;
		while((L = stdin.nextInt()) != 0){
			for(i = sum = ans = 0; i < N; ++i){
				sum += stdin.nextInt() - stdin.nextInt();
				if(ans == 0 && sum >= L) ans = i+1;
			}
			System.out.println(ans > 0 ? ans : "NA");
		}
	}
}

Block(AOJ No.0207)

mapが与えられて、スタートからゴールまでいけるか判定する

コード

スタート地点が移動不能地形の場合があるので注意する。Manhattan Distance 優先探索

import java.util.*;
public class aoj0207 {
	static final Scanner stdin = new Scanner(System.in);
	static final int X = 0, Y = 1, F = 2;
	static final int delta[][] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
	static final int ManhattanDistance(int[] s, int[] g){ return Math.abs(s[X] - g[X]) + Math.abs(s[Y] - g[Y]); }
	public static void main(String[] args) {
		while(true){
			int w = stdin.nextInt(), h = stdin.nextInt();
			if((w|h) == 0) break;
			int s[] = {stdin.nextInt(), stdin.nextInt()}, g[] = {stdin.nextInt(), stdin.nextInt()};
			int n = stdin.nextInt();
			int[][] map = new int[h+2][w+2]; for(int i = 0; i < h+2; ++i) Arrays.fill(map[i], 0);
			for(int i = 0; i < n; ++i){
				int c = stdin.nextInt(), d = stdin.nextInt(), x = stdin.nextInt(), y = stdin.nextInt();
				for(int j = 0; j < 2; ++j)
					for(int k = 0; k < 4; ++k)
						if(d == 0) map[y+j][x+k] = c;
						else map[y+k][x+j] = c;
				
			}
			System.out.println(BFS(map, s, g) ? "OK" : "NG");
		}
	}
	static boolean BFS(int[][] map, int[] s, int[] g){
		int color;
		if((color = map[s[Y]][s[X]]) == 0) return false;
		PriorityQueue<int[]> q = new PriorityQueue<int[]>(map.length*map[0].length, new Comparator<int[]>(){
			@Override public int compare(int[] o1, int[] o2) { return o1[F] - o2[F]; }
		});
		q.add(new int[]{s[X], s[Y], ManhattanDistance(s,g)});
		while(!q.isEmpty()){
			int[] e = q.poll();
			int x = e[X], y = e[Y];
			if(map[y][x] != color) continue;
			if(y == g[Y] && x == g[X]) return true;
			map[y][x] = 0;
			for(int[] d: delta){
				int n[] = {x + d[X], y + d[Y], 0};
				if(map[n[Y]][n[X]] != color) continue;
				n[F] = ManhattanDistance(e, n);
				q.add(n);
			}
		}
		return false;
	}
}

Room Numbers of a Hospital(AOJ No.208)

１０進数xが与えられる。'4','6'を忌み数なので使わないようにxを変換する。変換後の数字を答える。

アルゴリズム

xを８進数に変換して下のように変換する。

8進数	0	1	2	3	4	5	6	7
変換	0	1	2	3	5	7	8	9

コード

import java.util.*;
public class aoj0208 {
	static final Scanner stdin = new Scanner(System.in);
	static final int[] LUT = {0,1,2,3,5,7,8,9};
	public static void main(String[] args) {
		int o;
		while((o = stdin.nextInt()) != 0){
			for(char c: Integer.toOctalString(o).toCharArray())
				System.out.print(LUT[c-'0']);
			System.out.println();
		}
	}
}

Scene in a Picture(AOJ No.0209)

$n\times n$ の写真と $m\times m$ のピースが整数行列として与えられる。
ただし、ピースのある要素が-1のときは、その位置は欠落しているものと見なす。
ピースを0, 90, 180, 270度回転した物と写真を照らし合わせて一致する場所を探す。
ただし、候補が複数ある場合は、ピースの位置で優先度が決まり一つ選ぶ。
優先度は、1. y座標が小さい　2. x座標が小さい　という基準。
制約
$0 < n \leq 100$
$0 < m \leq 50$
0 < 画素値 $\leq 15$
$m < n$

コード

計算量 $4n^2m^2 = 4\times 100^2 \times 50^2 = 100,000,000$
右上から見ていって一致するところが見つかっても、もうちょい先で他の回転パターンが一致して、優先度の高い物が存在する可能性があるので、直ちに計算打ち切りするとWA.
5重ループ　コード汚い

import java.util.*;
public class aoj0209 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 4, INF = Integer.MAX_VALUE/2;
	static class T {
		int[][] p;
		int ax, ay;
		T(int[][] x){
			p = x;
			int n = x.length;
			for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) if(x[i][j] != -1){ ay = i; ax = j; return; }
		}
	}
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt(), m = stdin.nextInt();
			if((n|m) == 0) break;
			int[][] map = new int[n][n], piece = new int[m][m];
			T[] p = new T[N];
			for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) map[i][j] = stdin.nextInt();
			for(int i = 0; i < m; ++i) for(int j = 0; j < m; ++j) piece[i][j] = stdin.nextInt();
			p[0] = new T(piece);
			for(int i = 1; i < N; ++i) p[i] = new T(rotate(p[i-1].p));
			int ans[] = {INF,INF};
			for(int i = -m+1; i < n; ++i)
				for(int j = -m+1; j < n; ++j)
					SKIP: for(int k = 0; k < N; ++k){
						for(int I = 0; I < m; ++I)
							for(int J = 0; J < m; ++J){
								int P = p[k].p[I][J];
								if(P == -1) continue;
								if(!(i+I >= 0 && i+I < n && j+J >= 0 && j+J < n)) continue SKIP;
								int M = map[i+I][j+J];
								if(P != M) continue SKIP;
							}
						int ay = i + p[k].ay + 1, ax = j + p[k].ax + 1;
						if(ans[0] > ay || ans[0] == ay && ans[1] > ax){ ans[0] = ay; ans[1] = ax; }
					}
			System.out.println(ans[0] == INF ? "NA" : ans[1] + " " + ans[0]);	
		}
	}
	static final int[][] rotate(int[][] p){
		int n = p.length;
		int[][] ret = new int[n][n];
		for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) ret[i][j] = p[n-j-1][i];
		return ret;
	}
}

The Squares(AOJ No.0210)

$H\times W$ のマップが与えられる。地形は

#	壁
.	床
X	非常口
E	東を向いている人
N	北を向いている人
W	西を向いている人
S	南を向いている人

現在向いている方向の、右、前、左、後のマス目を順番に調べ、最初に見つけた、空いている通路または非常口の方向に向きを変える。そのようなマス目が無い場合は向きを変えない。
目の前のマス目が空いていて、他の人の目の前のマス目になっていない場合は移動する。同じマス目を目の前のマスとする人が複数いる場合は、そのマス目の、東、北、西、南のマス目にいる人の順で選択された 1 人が移動する。

非常口に入ると、その人はマップからいなくなる。
シミュレートして、全員が脱出する時間を答える。ただし、１８０ターンで脱出できなければシミュレーションを打ち切る。
制約
$0 < W,H \leq 30$

コード

やるだけだが...コードがあまりすっきりしてない。
同じマス目を目の前のマスとする人が複数いる場合、そのマス目の、東、北、西、南にいる人の順で優先するということは、西、南、東、北に向いている人の順で動かせばいいということ。
あるターンで非常口に一人(最も優先度が高い人)が入ったら、他の人が入らないように非常口を書き換えて、ターンの最後に戻してる。

import java.util.*;
public class aoj0210 {
	static final Scanner stdin = new Scanner(System.in);
	static final int Delta = 3, d[][] = {{-1, 0}, {0,-1}, {1,0}, {0,1}}, D = 4, Y = 0, X = 1, L = 180;
	@SuppressWarnings("serial") static final Map<Character, Integer> dir2id = new HashMap<Character, Integer>(){
		{put('N', 0); put('W', 1); put('S', 2); put('E',3); }
	};
	static final char WALL = '#', SPACE = '.', EXIT = 'X', MAN = 'M', TEMP = 'm';
	static class T{
		int y, x, d;
		T(int y, int x, int d){ this.y = y; this.x = x; this.d = d; }
	}
	public static void main(String[] args) {
		while(true){
			int W = stdin.nextInt(), H = stdin.nextInt();
			if((W|H) == 0) break;
			char[][] map = new char[H][];
			List<T> p = new ArrayList<T>();
			for(int i = 0; i < H; ++i){
				map[i] = stdin.next().toCharArray();
				for(int j = 0; j < W; ++j)
					switch(map[i][j]){
						case WALL: break;
						case SPACE: break;
						case EXIT: break; 
						default: p.add(new T(i,j,dir2id.get(map[i][j]))); map[i][j] = MAN;
					}
			}
			int ans = 1;
			while(!p.isEmpty() && ans++ <= L){
				List<T> next = new ArrayList<T>();
				int n = p.size();
				int[] nextD = new int[n];
				for(int i = 0; i < n; ++i){
					T e = p.get(i);
					nextD[i] = -1;
					for(int j = 0; j < D; ++j){
						int nd = (e.d+Delta+j)%D;
						int ny = e.y + d[nd][Y], nx = e.x + d[nd][X];
						if(map[ny][nx] == SPACE || map[ny][nx] == EXIT){ nextD[i] = nd; break; }
					}
					if(nextD[i] == -1) next.add(e);
				}
				for(int k = 0; k < D; ++k){
					for(int i = 0; i < n; ++i){
						if(nextD[i] != (k+1)%D) continue;
						T e = p.get(i);
						int ny = e.y + d[nextD[i]][Y], nx = e.x + d[nextD[i]][X];
						if(map[ny][nx] == EXIT){
							map[e.y][e.x] = SPACE;
							map[ny][nx] = TEMP;
						}else if(map[ny][nx] == SPACE){
							map[ny][nx] = MAN;
							map[e.y][e.x] = SPACE;
							next.add(new T(ny,nx,nextD[i]));
						}else{
							next.add(new T(e.y, e.x, nextD[i]));
						}
					}
				}
				p = next;
				for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j) if(map[i][j] == TEMP) map[i][j] = EXIT;
			}
			System.out.println(--ans > L ? "NA" : ans);
		}
	}
}

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

UFO Shooting Down Operation(AOJ No.0204), Rock, Paper, Scissors(AOJ No.0205), Next Trip(AOJ No.0206), Block(AOJ No.0207), Room Numbers of a Hospital(AOJ No.208), Scene in a Picture(AOJ No.0209), The Squares(AOJ No.0210)

UFO Shooting Down Operation(AOJ No.0204)

アルゴリズム

コード

Rock, Paper, Scissors(AOJ No.0205)

コード

Next Trip(AOJ No.0206)

コード

Block(AOJ No.0207)

コード

Room Numbers of a Hospital(AOJ No.208)

アルゴリズム

コード

Scene in a Picture(AOJ No.0209)

コード

The Squares(AOJ No.0210)

コード