kanetaiの二次記憶装置

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

A Symmetric Point(AOJ No.0081), Flying Jenny(AOJ No.0082), Era Name Transformation(AOJ No.0083), Search Engine(AOJ No.0084), Joseph's Potato(AOJ No.0085), Patrol(AOJ No.0086), Strange Mathematical Expression(AOJ No.0087), The Code A Doctor Loved(AOJ No.00

Online Judge

リポジトリ

A Symmetric Point(AOJ No.0081)

２点 P_1(x_1,y_1), P_2(x_2, y_2)を通る直線について線対称な点 Q(x_Q, y_Q)の像を求める。
制約
P_1, P_2, Qは互いに異なる
Qは対称軸上にはない

アルゴリズム

対称軸//y軸, すなわち、 x_1 = x_2の場合、求める像は (x_Q + 2(x_1-x_Q), y_Q)
同様に、 y_1 = y_2の場合、求める像は (x_Q, y_Q+2(y_1-y_Q))
それ以外の場合、まず、対称軸の傾き \alphaと、切片 \betaを求める。
\alpha = \frac{y_2-y_1}{x_2-x_1}, \beta = y_1 - \alpha x_1
次に、 y = \alpha xを対称軸とする線対称変換は、
1次変換 \frac{1}{\alpha^2+1}\left[ \begin{array}{cc} 1-\alpha^2 & 2\alpha \\ 2\alpha & \alpha^2 -1\end{array}\right] で表される。
この問題では、 y = \alpha x + \betaを対称軸とする線対称変換なので、
まず、対称軸が原点を通るような座標系に変換してやり、対称変換を行い、元の座標系に戻す。
\frac{1}{\alpha^2 + 1}\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & \beta \\ 0 & 0 & 1 \end{array}\right] \left[ \begin{array}{ccc} 1-\alpha^2 & 2\alpha & 0 \\ 2\alpha & \alpha^2 -1 & 0 \\ 0 & 0 & \alpha^2 +1\end{array}\right] \left[ \begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & -\beta \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{c} x \\ y \\ 1 \end{array} \right] = \frac{1}{\alpha^2 + 1}\left[ \begin{array}{ccc} 1-\alpha^2 & 2\alpha & -2\alpha \beta \\ 2\alpha & \alpha^2 -1 & 2\beta \\ 0 & 0 & \alpha^2 + 1 \end{array}\right]\left[ \begin{array}{c}x \\ y \\ 1 \end{array} \right]
あるいは平面幾何(射影、鏡映)を使う。

コード

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0081 {
	static final Scanner stdin = new Scanner(System.in);
	static Solver solver = Solver.Reflection;
	public static void main(String[] args) {
		while(stdin.hasNext()){
			String[] line = stdin.nextLine().split(",");
			double x1 = Double.parseDouble(line[0]), y1 = Double.parseDouble(line[1]);
			double x2 = Double.parseDouble(line[2]), y2 = Double.parseDouble(line[3]);
			double xq = Double.parseDouble(line[4]), yq = Double.parseDouble(line[5]);
			System.out.println(solver.solve(x1, y1, x2, y2, xq, yq));
		}
	}
	enum Solver {
		Reflection { @Override String solve(double x1, double y1, double x2, double y2, double xq, double yq) {
			Point ans = new Point(xq, yq).reflection(new Line(x1, y1, x2, y2));
			return ans.x + " " + ans.y;
		}}, AffineTransformation { @Override String solve(double x1, double y1, double x2, double y2, double xq, double yq) {
			double xr, yr;
			if(x1 == x2){
				xr = xq + 2*(x1-xq); yr = yq;
			}else if(y1 == y2){
				xr = xq; yr = yq + 2*(y1-yq);
			}else{
				double alpha = (y2-y1)/(x2-x1);
				double beta = y1 - alpha*x1;
				double coef = 1/(alpha*alpha + 1);
				xr = coef*((1-alpha*alpha)*xq + 2*alpha*yq - 2*alpha*beta);
				yr = coef*(2*alpha*xq + (alpha*alpha-1)*yq + 2*beta);
			}
			return xr + " " + yr;
		}};
		String solve(double x1, double y1, double x2, double y2, double xq, double yq) { return ""; }
	}
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,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 double normsq(){ return x*x + y*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 Point reflection(Line l){ return projection(l).mul(2).sub(this); }
	} //class Point
	public static class Line{
		private final Point start;
		private final Point end;
		public Point dirV() { return end.sub(start); } //directional vector
		public Line(double sx, double sy, double ex, double ey){ start = new Point(sx,sy); end = new Point(ex,ey); }
	}
}

Flying Jenny(AOJ No.0082)

メリーゴーランドに乗り物が8台あり、0〜7版乗り場に止まっている乗り物のキャパシティーは、4, 1, 4, 1, 2, 1, 2, 1人で、円形に並んでいる。
同じ順に、各乗り場に、客がそれぞれ c_0, c_1, \cdots , c_7人並んでいる。
乗れない客が最小になるように、メリーゴーランドを回して、止め、その時の0〜7番乗り場に止まっている乗り物のキャパシティーの系列 c_0, c_1, \cdots , c_7を求める。
乗れない客が最小となる止まり方が複数ある場合、系列 c_0, c_1, \cdots , c_7を7桁の整数とみて最小のものを出力する。

コード

はじめに、キャパシティーの系列を回転させたもの8パターンを求めておくだけ。
8パターンなので、じか打ちで良かったかもしれない。

import java.util.*;
public class aoj0082 {
	static final Scanner stdin = new Scanner(System.in);
	static final int[] RIDE = {4, 1, 4, 1, 2, 1, 2, 1};
	static final int[][] PAT = new int[8][8];
	static final String[] sPAT = new String[8];
	public static void main(String[] args) {
		int[] c = new int[8];
		for(int i = 0; i < 8; ++i){
			StringBuilder s = new StringBuilder();
			for(int j = 0; j < 8; ++j){
				PAT[i][j] = RIDE[(i+j)%8];
				s.append(' ');
				s.append(PAT[i][j]);
			}
			sPAT[i] = s.substring(1);
		}
		while(stdin.hasNext()){
			String minstr = sPAT[0];
			int min = 0;
			for(int i = 0; i < 8; ++i){
				c[i] = stdin.nextInt();
				min += (RIDE[i]-c[i] < 0 ? c[i] - RIDE[i] : 0);
			}		
			for(int i = 1; i < 8; ++i){
				int temp = 0;
				for(int j = 0; j < 8; ++j)
					temp += (PAT[i][j]-c[j] < 0 ? c[j] - PAT[i][j] : 0);
				if(temp < min || (temp == min && sPAT[i].compareTo(minstr) < 0)){
					minstr = sPAT[i];
					min = temp;
				}
			}
			System.out.println(minstr);
		}
	}
}

Era Name Transformation(AOJ No.0083)

元号 期間
meiji 1868. 9. 8 〜 1912. 7.29
taisho 1912. 7.30 〜 1926.12.24
showa 1926.12.25 〜 1989. 1. 7
heisei 1989. 1. 8 〜

年月日が与えられて、年号,年,月,日を答える。明治以前ならpre-meijiと答える。

コード

以前日付関連で作った修正Julius日を求める関数で、条件分けした。

import java.util.*;
public class aoj0083 {
	static final Scanner stdin = new Scanner(System.in);
	static Solver solver = Solver.GregToJulianDay;
	static final int premeiji = solver.solve(1868, 9, 8);
	static final int meiji = solver.solve(1912, 7, 29);
	static final int taisho = solver.solve(1926, 12, 24);
	static final int showa = solver.solve(1989, 1, 7);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			int y = stdin.nextInt(), m = stdin.nextInt(), d = stdin.nextInt();
			int jd = solver.solve(y,m,d);
			if(jd < premeiji) System.out.println("pre-meiji");
			else if(jd <= meiji) System.out.println("meiji "+(y-1868+1) + " " + m + " " + d);
			else if(jd <= taisho) System.out.println("taisho "+(y-1912+1) + " " + m + " " + d);
			else if(jd <= showa) System.out.println("showa "+(y-1926+1) + " " + m + " " + d);
			else System.out.println("heisei "+(y-1989+1) + " " + m + " " + d);
		}
	}
	static enum Solver {
		GregToJulianDay{ @Override int solve(int y, int m, int d){ return GregToJulianDay(y,m,d,true); }}, 
		GregToJD{ @Override int solve(int y, int m, int d){ return GregToJD(y,m,d,true); }};
		int solve(int y, int m, int d){ return 0; }
	}
	public static final int GregToJulianDay(int y, int m, int d, boolean modflag) { //Ver. 1
		y += 4800; //※負の数に対する除算や剰余の計算結果は、言語あるいは処理系によって異なるので注意
		if (m < 3){ --y; m += 12; }
		return 365*y + y/4 - y/100 + y/400 + (153*m - 457)/5 + d-32045 - (modflag ?  2400001 : 0);
	}
	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);
	}
}

Search Engine(AOJ No.0084)

英文1行が与えられて、3文字以上6文字以下の単語を切り出す。
デリミタは' ', '.', ','

コード

正規表現でsplitするだけだが、.がメタ文字なのでエスケープしないといけない。
\Q\Eで囲むやり方もあるみたい。

import java.util.*;
public class aoj0084 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		StringBuilder sb = new StringBuilder();
		String[] line = stdin.nextLine().split(",|\\.| ");
		for(String s: line)
			if(3 <= s.length() && s.length() <= 6){
				sb.append(' ');
				sb.append(s);
			}
		System.out.println(sb.substring(1));
	}
}

Joseph's Potato(AOJ No.0085)

n人が円形(1の右が2, その右が3, ... その右がn, その右が1)に座っている。
nから右にm人目が、円から抜け、そこから右にm人が抜ける.これを繰り返し最後に残る人を求める。

コード

抜けた人からm人右の人が抜けるので→抜けた人の右隣の人からm-1人右の人が抜ける

import java.util.*;
public class aoj0085 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			int n = stdin.nextInt();
			int m = stdin.nextInt();
			if(n==0 && m==0) break;
			ArrayList<Integer> l = new ArrayList<Integer>();
			for(int i = 0; i < n; ++i) l.add(i+1);
			int idx = 0;
			while(l.size() > 1){
				idx = (idx + m-1)%l.size();
				l.remove(idx);
				idx %= l.size();
			}
			System.out.println(l.get(0));
		}
	}
}

Patrol(AOJ No.0086)

辺(端点の対)の系列が与えられる。スタート地点を頂点1、ゴール地点を頂点2とし、全経路を同じ辺を通らないように周遊すことができるかどうかを答える。

アルゴリズム

この問題ではスタートとゴールが決まっており、異なる頂点なので、順オイラーグラフになっているかどうかを調べればよい。
準オイラーグラフは奇頂点が2個かつスタート地点およびゴール地点が奇頂点なら準オイラーグラフ
ちなみに、奇頂点が0個(すべての頂点が偶頂点)ならオイラーグラフとなる。
準オイラーグラフとオイラーグラフはどちらも一筆書き可能で、スタートとゴールが同じかどうかの違いである。

コード

次数を調べるだけなのでもっとコンパクトにかけるが、ライブラリのテストも兼ねて、無駄にパスも求めている。

import java.util.*;
public class aoj0086 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 101;
	public static void main(String[] args) {
		while(stdin.hasNext()){
			List<List<Edge>> list = new ArrayList<List<Edge>>(N);
			for(int i = 0; i < N; ++i) list.add(new ArrayList<Edge>(N));
			while(true){
				int src = stdin.nextInt(), dst = stdin.nextInt();
				if(src==0 && dst==0) break;
				list.get(src).add(new Edge(src, dst, 1)); 
				if (src != dst) list.get(dst).add(new Edge(dst, src, 1));
			}
			System.out.println(eulerPath(list, 1, 2).isEmpty() ? "NG" : "OK" );
		}
	}
	public static class Edge {
		protected int s, d, w;
		Edge(int s, int d, int w){ set(s, d, w); }
		public final void set(int s, int d, int w){ this.s = s; this.d = d; this.w = w; }
	}
	private static class Result {
		int terminal1 = -1, terminal2 = -1, edgeNum = 0;
		public boolean isEulerGraph() { return terminal1 == -1 /*&& terminal2 == -1*/; }
	}
	public static final List<Integer> eulerPath(List<List<Edge>> adjList, int s) {
		return buildEulerPath(adjList, s, isEulerGraph(adjList));
	}
	public static final List<Integer> eulerPath(List<List<Edge>> adjList, int s, int g) {
		List<Integer> path = buildEulerPath(adjList, s, isEulerGraph(adjList));
		return !path.isEmpty() && path.get(path.size()-1) == g ? path : Collections.<Integer>emptyList();
	}
	public static final Result isEulerGraph(List<List<Edge>> adjList){
		int odd = 0, n = adjList.size();
		Result ret = new Result();
		for(int i = 0; i < n; ++i){
			int deg = 0;
			for (Edge e: adjList.get(i)) deg += (e.s == e.d ? 2 : 1);
			ret.edgeNum += deg;
			if((deg&1) == 1){
				++odd;
				if (ret.terminal1 == -1) ret.terminal1 = i;
				else ret.terminal2 = i;
			}
		}
		if (odd == 0 || odd == 2) {
			ret.edgeNum /= 2; //because include outer and inner degree.
			return ret;
		}
		return null;
	}
	private static List<Integer> buildEulerPath(List<List<Edge>> adjList, int s, Result result){
		int n = adjList.size();
		if (result != null && (result.isEulerGraph() || (result.terminal1 == s || result.terminal2 == s))) {
			LinkedList<Integer> path = new LinkedList<Integer>();
			int[][] adj = new int[n][n];
			for(List<Edge> l: adjList) for(Edge e: l) ++adj[e.s][e.d];
			visit(adjList, adj, s, path);
			if(path.size() == result.edgeNum + 1) return path; //connected
		}
		return Collections.<Integer>emptyList();
	}
	private static void visit(List<List<Edge>> adjList, int[][] adjMatrix, int s, LinkedList<Integer> path) {
		for(final Edge e: adjList.get(s)) if(adjMatrix[e.s][e.d] != 0) {
			--adjMatrix[e.s][e.d];
			if (e.d != e.s) --adjMatrix[e.d][e.s];
			visit(adjList, adjMatrix, e.d, path);
		}
		path.addFirst(s);
	}	
}

Strange Mathematical Expression(AOJ No.0087)

逆ポーランド記法の式を計算する

import java.util.*;
public class aoj0087 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			Stack<Double> stack = new Stack<Double>();
			String[] line = stdin.nextLine().split(" ");
			for(String str: line){
				if(str.equals("+")){
					stack.add(stack.pop()+stack.pop());
				}else if(str.equals("-")){
					double b = stack.pop(), a = stack.pop();
					stack.add(a-b);
				}else if(str.equals("*")){
					stack.add(stack.pop()*stack.pop());
				}else if(str.equals("/")){
					double b = stack.pop(), a = stack.pop();
					stack.add(a/b);
				}else{
					stack.add(Double.parseDouble(str));
				}
			}
			System.out.println(stack.get(0));
		}
	}
}

The Code A Doctor Loved(AOJ No.0088)

文字→01の数字列のエンコード表と01の数字列(5文字)→文字のデコード表がある。
エンコード表で、文字列をデコードし、5文字毎に分割する、最後の文字が5文字より少ないなら0を加えて5文字になるようにする。
それをデコード表で変換したものを出力する。

コード

またかい。0を余った文字列の末尾に加えるのか、先頭に加えるのか書いてなない。
問題文の例も、余った文字列が"0"だからどちら側に加えてるのかわからんじゃないか。
表の入力が大変だのう。コピペして、適当に編集した文字列を張り付けて、パースした。

import java.util.*;
public class aoj0088 {
	static final Scanner stdin = new Scanner(System.in);
	static final String strENC = " _101_'_000000_,_000011_-_10010001_._010001_?_000001_A_100101_B_10011010_C_0101_D_0001_E_110_F_01001_G_10011011_H_010000_I_0111_J_10011000_K_0110_L_00100_M_10011001_N_10011110_O_00101_P_111_Q_10011111_R_1000_S_00110_T_00111_U_10011100_V_10011101_W_000010_X_10010010_Y_10010011_Z_10010000";
	static final String strDEC = "00000_A_00001_B_00010_C_00011_D_00100_E_00101_F_00110_G_00111_H_01000_I_01001_J_01010_K_01011_L_01100_M_01101_N_01110_O_01111_P_10000_Q_10001_R_10010_S_10011_T_10100_U_10101_V_10110_W_10111_X_11000_Y_11001_Z_11010_ _11011_._11100_,_11101_-_11110_'_11111_?";
	static public void main(String[] args) {
		HashMap<Character, String> enc = new HashMap<Character, String>();
		HashMap<String, Character> dec = new HashMap<String, Character>();
		String[] e = strENC.split("_");
		String[] d = strDEC.split("_");
		for(int i = 0; i<64; i+=2){
			enc.put(e[i].charAt(0), e[i+1]);
			dec.put(d[i], d[i+1].charAt(0));
		}
		while(stdin.hasNext()){
			char[] line = stdin.nextLine().toCharArray();
			StringBuilder sb = new StringBuilder();
			for(char ch: line) sb.append(enc.get(ch));
			while(sb.length()%5 != 0) sb.append('0');
			for(int i=0; i < sb.length(); i+=5)
				System.out.print(dec.get(sb.substring(i, i+5)));
			System.out.println("");
		}
	}
}

The Shortest Path on A Rhombic Path(AOJ No.0089)

パスカルの三角形みたいなのが上下にくっついて、ひし形みたいになったやつを考える。
頂点にに数字が与えられて、一番上から、斜め下に向かって進み、一番下にたどり着いたとき、通った頂点の和の最大値を求める。

コード

各点で、そこに到達するまでの和の最大値を記録してけば勝つる

import java.util.*;
public class aoj0089 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n = 1;
		int[][] DP = new int[2][101];
		Arrays.fill(DP[0], 0); Arrays.fill(DP[1], 0);
		DP[0][0] = stdin.nextInt(); stdin.nextLine();//改行
		int j = 1, k = 0;
		while(stdin.hasNext()){
			String[] instr = stdin.nextLine().split(",");
			int[] in = new int[instr.length];
			for(int i=0; i < instr.length; ++i) in[i] = Integer.parseInt(instr[i]);
			if(n < in.length){
				DP[j][0] = DP[k][0] + in[0];
				DP[j][n] = DP[k][n-1] + in[n];
				for(int i = 1; i < n; ++i) DP[j][i] = in[i] + Math.max(DP[k][i], DP[k][i-1]);
			}else{
				for(int i = 0; i < n-1; ++i) DP[j][i] = in[i] + Math.max(DP[k][i], DP[k][i+1]);
			}
			n = in.length;
			j = k;
			k = (k+1)%2;
		}
		System.out.println(DP[k][0]);
	}
}