kanetaiの二次記憶装置

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

Seven Puzzle(AOJ No.0121), Summer of Phyonkichi(AOJ No.0122), Speed Skating Badge Test(AOJ No.0123), League Match Score Sheet(AOJ No.0124), Day Count(AOJ No.0125), Puzzle(AOJ No.0126), Pocket Pager Input(AOJ No.0127), Abacus(AOJ No.0128), Hide-and-Seek Su

Online Judge

リポジトリ

Seven Puzzle(AOJ No.0121)

2\times 4のパズル、0〜7のパネルが与えられて、
0のパネルを上下左右のどれかのパネルと交換して、

0 1 2 3
4 5 6 7

の状態にするゲーム。
与えられた状態から、上の最終状態にするまでの最小の交換回数を求める。
ただし、ゲームクリア可能な初期状態しか与えられないものとする。

アルゴリズム

最終状態が決まっているので、初期状態から幅優先探索せず、
最終状態から、幅優先で繊維可能な全状態と交換回数を列挙しておけば良い。

コード

ルールを勘違いしてて、無駄に時間がかかった。状態は文字列で持ってる。
久しぶりのコンパイルエラー。提出するとき、クラス名とコンストラクタの名前かえるの忘れてた。

import java.util.*;
public class aoj0121 {
	static final Scanner stdin = new Scanner(System.in);
	static final String INISTR = "01234567";
	static final int N = INISTR.length();
	static final HashMap<String, Integer> map = new HashMap<String, Integer>();
	static final int[] offset = {-1, 1, +4, -4};
	public static void main(String[] args) { 
		BFS();
		while(stdin.hasNext()){
			StringBuilder line = new StringBuilder(N);
			for(int i = 0; i < N; ++i) line.append(stdin.nextInt());
			System.out.println(map.get(line.toString()));
		}
	}
	static String swap(String str, int i, int j){
		StringBuilder chars = new StringBuilder(str);
		char c = chars.charAt(i);
		chars.setCharAt(i, chars.charAt(j));
		chars.setCharAt(j, c);
		return chars.toString();
	}
	static class Node{
		String state;
		int count;
		int pos0;
		Node(String state, int count, int pos0){this.state = state; this.count = count; this.pos0 = pos0;}
	}
	static void BFS(){
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(INISTR, 0, 0));
		map.put(INISTR, 0);
		while(!q.isEmpty()){
			Node n = q.poll();
			for(int d: offset){
				int j = n.pos0 + d;
				if(j >=0 && j < N && !(n.pos0 == 3 && d == 1 || n.pos0 == 4 && d == -1) ){	
					String next = swap(n.state, n.pos0, j);
					if(!map.containsKey(next)){
						map.put(next, n.count + 1);
						q.add(new Node(next, n.count + 1, j));
					}
				}
			}
		}
	}
}

Summer of Phyonkichi(AOJ No.0122)

10\times 10のマスにn個のスプリンクラー s_iがある。
カエルの位置を○とすると、このカエルは、次に■の位置のどれかにジャンプする。
□■■■□
■□□□■
■□○□■
■□□□■
□■■■□
また、スプリンクラー s_iはカエルがi回ジャンプしたとき周囲８近傍に散水し( (sx_i, sy_i)も含む)、次にカエルがジャンプするタイミングで散水をやめる。
カエルの初期位置(x,y)とスプリンクラーの位置 (sx_i, sy_i)が与えられたとき、
カエルがすべてのスプリンクラーの水を浴びられるかを答える。

コード

import java.util.*;
public class aoj0122 {
	static final Scanner stdin = new Scanner(System.in);
	static final int[] offx = {0,  1,  2,  2,  2,  1,  0,  -1, -2, -2, -2, -1};
	static final int[] offy = {-2, -2, -1, 0,  1,  2,  2,  2,  1,  0,  -1, -2};
	static class State implements Comparable<State>{
		int x, y, time;
		State(int x, int y, int time){this.x = x; this.y = y; this.time = time; }
		public int compareTo(State o) {
			return this.x < o.x ? -1 : this.x > o.x ? 1 :
				this.y < o.y ? -1 : this.y > o.y ? 1 :
					this.time < o.time ? -1 : this.time > o.time ? 1 : 0;
		}
	}
	static final int N = offx.length;
	public static void main(String[] args) { 
		while(true){
			int x = stdin.nextInt(), y = stdin.nextInt();
			if(x == 0 && y == 0) break;
			int n = stdin.nextInt();
			int[] sx = new int[n], sy = new int[n];
			for(int i = 0; i < n; ++i){
				sx[i] = stdin.nextInt(); sy[i] = stdin.nextInt();
			}
			System.out.println(BFS(x, y, n, sx, sy) ? "OK" : "NA");
		}
	}
	static boolean BFS(int x, int y, int n, int[] sx, int[]sy){
		Queue<State> q = new LinkedList<State>();
		State s = new State(x, y, -1);
		q.add(s);
		TreeSet<State> map = new TreeSet<State>();
		map.add(s);
		while(!q.isEmpty()){
			s = q.poll();
			if(s.time == n-1) return true;
			for(int i = 0; i < N; ++i){
				int nx = s.x + offx[i], ny = s.y + offy[i];
				if(check(nx, ny, sx[s.time+1], sy[s.time+1])){
					State ns = new State(nx, ny, s.time + 1);
					if(!map.contains(ns)){
						q.add(new State(nx, ny, ns.time));
						map.add(ns);
					}
				}
			}
		}
		return false;
	}
	static boolean check(int x, int y, int sx, int sy){
		return 0 <= x && 0 <= y && x < 10 && y < 10 && 
				sx-1 <= x && x <= sx+1 && sy-1 <= y && y <= sy+1;
	}
}

Speed Skating Badge Test(AOJ No.0123)

500M, 1000Mのタイムが与えられて、以下の表でランク付けする。
500M, 1000Mどちらのタイムも下の表のある級のタイム未満だったら、その級が認められる。
E級以下ならNAと答える。

男子 500M 1000M
AAA級 35秒50 1分11秒00
AA級 37秒50 1分17秒00
A級 40秒00 1分23秒00
B級 43秒00 1分29秒00
C級 50秒00 1分45秒00
D級 55秒00 1分56秒00
E級 1分10秒00 2分28秒00

コード

思ったより短く書けた

import java.util.*;
public class aoj0123 {
	static final Scanner stdin = new Scanner(System.in);
	static String[] rank = {"AAA", "AA", "A", "B", "C", "D", "E", "NA"};
	static double[][] time = {{35.5, 71.0}, {37.5, 77.0}, {40.0, 83.0}, {43.0, 89.0}, {50.0, 105.0}, {55.0, 116.0}, {70.0, 148.0}};
	public static void main(String[] args) {
		while(stdin.hasNext()){
			double a = stdin.nextDouble(), b = stdin.nextDouble();
			int i;
			for(i = 0; i < time.length; ++i)
				if(a < time[i][0] && b < time[i][1]) break;
			System.out.println(rank[i]);
		}
	}
}

League Match Score Sheet(AOJ No.0124)

勝ち３点、負け０点、引き分け１点で得点計算する。
チーム名と、価値、負け、引き分けの数が与えられて、それを集計し、得点順にソートして、
チーム名と得点を出力する。
同じ得点のチームが存在する場合は、入力順にする。

コード

Arrays.sortが安定ソートだと初めて知った。
チーム数をstdin.nextInt()で読み込んで、stdin.nextLine()で改行を空読みして、レコードをstdin.nextLine().split("")で読み込んだら、
これが原因か知らんが、なんかruntime errorになった。
いつもはこれでAcceptしてたんだけど、最後の改行の空読みがだめだったのかな(最後の0の後に改行がなくEOFがあった？？？)？

import java.util.*;
public class aoj0124 {
	static final Scanner stdin = new Scanner(System.in);
	static class Record{
		String name;
		int point;
		Record(String name, int point){ this.name = name; this.point = point; }
	}
	public static void main(String[] args) {
		boolean flag = false;
		while(true){
			int n = stdin.nextInt(); 
			if(n == 0) break;
			if(flag) System.out.println("");
			flag = true;
			Record[] a = new Record[n];
			for(int i = 0; i < n; ++i)
				a[i] = new Record(stdin.next(), 3*stdin.nextInt() + 0*stdin.nextInt() + stdin.nextInt());
			Arrays.sort(a, new Comparator<Record>(){
				public int compare(Record o1, Record o2){
					return o1.point > o2.point ? -1 : o1.point == o2.point ? 0 : 1;
				}
			});
			for(Record r: a) System.out.println(r.name + "," + r.point);
		}
	}
}

Day Count(AOJ No.0125)

ymd形式で二つの日付 ymd_1 \leq ymd_2が与えられ、その日数差を答える。

コード

Julian day求めて引き算するだけです。

import java.util.*;
public class aoj0125 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int y1 = stdin.nextInt(), m1 = stdin.nextInt(), d1 = stdin.nextInt();
			int y2 = stdin.nextInt(), m2 = stdin.nextInt(), d2 = stdin.nextInt();
			if(y1 == -1) break;
			System.out.println(GregToJD(y2, m2, d2, true) - GregToJD(y1, m1, d1, true));
		}
	}
	public static final int GregToJD(int y, int m, int d, boolean modflag){ // Ver. 2
		int a  = (14-m)/12;
		y = y + 4800 - a;
		m = m + 12*a -3;
		return d + (153*m+2)/5 + 365 * y + y/4 - y/100 + y/400 - 32045 - (modflag ?  2400001 : 0);
	}
}

Puzzle(AOJ No.0126)

ナンプレのテーブルが与えられて、ルール違反している部分に印を付ける。

コード

投げやりすぎる

import java.util.*;
public class aoj0126 {
	static final Scanner stdin = new Scanner(System.in);
	static final boolean[][] flag = new boolean[9][9];
	static final int[][] p = new int[9][9];
	static final int[] freq = new int[10];
	static void checkRow(int i){
		Arrays.fill(freq, 0);
		for(int x: p[i]) freq[x]++;
		for(int j = 0; j < 9; ++j) if(freq[p[i][j]] > 1) flag[i][j] = false;
	}
	static void checkCol(int j){
		Arrays.fill(freq, 0);
		for(int i = 0; i < 9; ++i) freq[p[i][j]]++;
		for(int i = 0; i < 9; ++i) if(freq[p[i][j]] > 1) flag[i][j] = false;
	}
	static void checkSq(int i, int j){
		Arrays.fill(freq, 0);
		for(int I = i; I < i + 3; ++I)
			for(int J = j; J < j + 3; ++J)
				freq[p[I][J]]++;
		for(int I = i; I < i + 3; ++I)
			for(int J = j; J < j + 3; ++J)
				if(freq[p[I][J]] > 1) flag[I][J] = false;
	}
	public static void main(String[] args) {
		int n = stdin.nextInt();
		while(true){
			for(int i = 0; i < 9; ++i){
				for(int j = 0; j < 9; ++j)
					p[i][j] = stdin.nextInt();
				Arrays.fill(flag[i], true);
			}
			for(int i = 0; i < 9; ++i){
				checkCol(i);
				checkRow(i);
			}
			for(int i = 0; i < 9; i+=3)
				for(int j = 0; j < 9; j+=3)
					checkSq(i,j);
			for(int i = 0; i < 9; i++){
				for(int j = 0; j < 9; j++)
					System.out.print((flag[i][j] ? " " : "*") + p[i][j]);
				System.out.println();
			}
			if(--n != 0) System.out.println();
			else break;
		}
	}
}

Pocket Pager Input(AOJ No.0127)

ポケベルうちによる入力系列が与えられて、下の表に従って、デコードする。
デコードが失敗するときは、NAと答える。

1 2 3 4 5 6
1 a f k p u z
2 b g l p v .
3 c h m r w ?
4 d i n s x !
5 e j o t y

コード

めんどいんでtry catchでいいや

import java.util.*;
public class aoj0127 {
	static final Scanner stdin = new Scanner(System.in);
	static char[][] map = { {'a', 'b', 'c', 'd', 'e'}, {'f', 'g', 'h', 'i', 'j'}, {'k', 'l', 'm', 'n', 'o'}, {'p', 'q', 'r', 's', 't'}, {'u', 'v', 'w', 'x', 'y'}, {'z', '.', '?', '!', ' '}};
	public static void main(String[] args) {
		while(stdin.hasNext()){
			char[] line = stdin.nextLine().toCharArray();
			StringBuilder ans = new StringBuilder();
			try{
				for(int i = 0; i < line.length; i+=2) ans.append(map[line[i]-'1'][line[i+1]-'1']);
			}catch(Exception e){
				ans = new StringBuilder("NA");
			}finally{
				System.out.println(ans.toString());
			}
		}
	}
}

Abacus(AOJ No.0128)

5桁以下の整数 \geq 0が与えられて、それを表すそろばんの配置を出力する。

コード

import java.util.*;
public class aoj0128 {
	static final Scanner stdin = new Scanner(System.in);
	static final String[] abacus = {"* = ****", "* =* ***", "* =** **", "* =*** *", "* =**** ", " *= ****", " *=* ***", " *=** **", " *=*** *", " *=**** " };
	public static void main(String[] args) {
		boolean flag = false;
		while(stdin.hasNext()){
			if(flag) System.out.println();
			flag = true;
			String line = String.format("%05d", stdin.nextInt());
			for(int i = 0; i < 8; ++i){
				for(int j = 0; j < 5; ++j)
					System.out.print(abacus[line.charAt(j)-'0'].charAt(i));
				System.out.println();
			}
		}
	}
}

Hide-and-Seek Supporting System(AOJ No.0129)

AとBがかくれんぼをしている。 n個の円形の障害物の中心座標と半径と、A,Bの座標が与えられる。
BがAを視認できるかを答える。
障害物の後ろにいる場合は、視認できない(境界にいる場合も含む)。
また、どちらも同じ障害物の中にいる場合、ほかの障害物に遮られていなければ、視認できる。

アルゴリズム

まず、同じ円内にA, Bがいるかを求める。いなければ視認不可。
一つ以上、同じ円内にA, Bがいれば、
それらの円を除く他の円と線分ABの交差判定をする。
一つでも交差していれば、視認不可、
交差していなければ、視認可

コード

ライブラリをコピペしているから無駄に長い。
やりかたももっといいのがあると思うが、こういう問題を正解できるとうれしいですね。

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0129 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) { 
		while(true){
			int n = stdin.nextInt();
			if(n == 0) break;
			boolean[] A = new boolean[n], B = new boolean[n];
			Circle[] c = new Circle[n];
			for(int i = 0; i < n; ++i) c[i] = new Circle(stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble());
			int m = stdin.nextInt();
			for(int i = 0; i < m; ++i){
				boolean flag = true;
				Arrays.fill(A, false); Arrays.fill(B, false);
				Line s = new Line(stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble());
				for(int j = 0; j < n; ++j){
					if(s.start.intersectsPC(c[j])) A[j] = true;
					if(s.end.intersectsPC(c[j])) B[j] = true;
					if(A[j] == B[j]) flag = false;
				}
				if(flag){ System.out.println("Safe"); continue; }
				flag = false;
				for(int j = 0; j < n; ++j){
					if(A[j] && B[j]) continue;
					if(s.intersectsSC(c[j])){ flag = true; break; }
				}
				System.out.println(flag ? "Safe" : "Danger");
			}
		}
	}
	public static final double EPS = 1e-10;
	public static boolean equal(double a, double b){ return Math.abs(a-b) < EPS; }	// a == b
	public static boolean less(double a, double b){ return a - b < -EPS; }			// a < b
	public static boolean leq(double a, double b){ return a - b < EPS; }			// a <= b
	public static boolean greater(double a, double b){ return less(b,a); }			// a > b
	public static boolean geq(double a, double b){ return leq(b,a); }				// a >= b
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,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 double dot(Point p){ return x * p.x + y * p.y; }
		public final Point projection(Line l){
			Point a = l.dirV();
			Point b = this.sub(l.start);
			return l.start.add(a.mul(a.dot(b)/a.normsq()));
		}
		public final boolean intersectsPC(Circle c){ return leq(distanceSq(c.o), c.r*c.r); }
		public final double distancePS(Line s){
			Point proj = projection(s);
			return proj.intersectsPS(s) ? distance(proj) : Math.min(distance(s.start), distance(s.end));
		}
		public final boolean intersectsPS(Line s) {
			return equal(s.start.distance(this) + this.distance(s.end), s.end.distance(s.start)); //三角不等式で等号が成り立つとき
		}
	} //class Point
	public static class Line{
		private final Point start, end;
		public Line(double sx, double sy, double ex, double ey){ start = new Point(sx,sy); end = new Point(ex,ey); }
		public Point dirV() { return end.sub(start); } //directional vector
		public final double distanceSP(Point p){ return p.distancePS(this); }
		public final boolean intersectsSC(Circle c) { return geq(c.r, distanceSP(c.o)); }
	} //class Line
	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; }
	}
}

Train(AOJ No.0130)

列車に小文字アルファベットの名前がついていて、２６両以下の編成になっている。
その中で、巡回していて、どの方向に巡回しているかと、車両名を表す系列が与えられる。
これを解読して、車両の並びを答える。
車両名はだぶっていない。

コード

泥臭い実装

import java.util.*;
public class aoj0130 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n = stdin.nextInt();
		while(n-->0){
			char[] line = stdin.next().toCharArray();
			StringBuilder ans = new StringBuilder();
			boolean flag = true;
			int p = -1;
			for(int i = 0; i < line.length; ++i){
				switch(line[i]){
				case '-': break;
				case '<': flag = true; p--; break;
				case '>': flag = false; p++; break;
				default:
					if(p < 0 || ans.length() <= p){
						if(flag){ ans.insert(0,line[i]); p++; }
						else{ ans.append(line[i]); }
					}
				}
			}
			System.out.println(ans.toString());
		}
	}
}