kanetaiの二次記憶装置

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

Spiral Pattern(AOJ No.0141), Nature of Prime Numbers(AOJ No.0142), Altair and Vega(AOJ No.0143), Packet Transportation(AOJ No.0144), Cards(AOJ No.0145)

Online Judge

リポジトリ

Spiral Pattern(AOJ No.0141)

nが与えられて、n×nの中にぐるぐる模様を書く。
ぐるぐる模様は、左下から始まって１行または１列分開けて中心に向かって'#'で描かれる。↑のリンク参照

アルゴリズム

進行方向とその４近傍(自分がいる位置を除く)を見て'#'なら方向転換、' 'なら進む。
方向転換した後、上の操作で進めないならそこで終了。

コード

方向ベクトルを作っとけば多少楽になる
番兵として' 'で囲んだ後に、さらに'#'で囲んでいる。

import java.util.*;
public class aoj0141 {
	static final Scanner stdin = new Scanner(System.in);
	static final int dx[] = {0, 1, 0, -1};
	static final int dy[] = {-1, 0, 1, 0};
	static char[][] map;
	static boolean check(int x, int y, int dir){
		int nx = x + dx[dir], ny = y + dy[dir];
		if(map[ny][nx] == '#') return false; //この条件多分いらない
		for(int i = 0; i < 4; ++i){
			if(nx + dx[i] == x && ny + dy[i] == y) continue;
			if(map[ny + dy[i]][nx + dx[i]] == '#') return false;
		}
		return true;
	}
	public static void main(String[] args) {
		int d = stdin.nextInt();
		while(d-- > 0){
			int n = stdin.nextInt();
			map = new char[n+4][n+4];
			for(int i = 0; i < n+4; ++i)
				for(int j = 0; j < n+4; ++j)
					map[i][j] = (i == 0 || j ==0 || i == n+3 || j == n+3) ? '#' : ' ';

			int dir = 0, x = 2, y = n+2;
			boolean flag = false; //方向転換したかどうか
			while(true){
				if(check(x, y, dir)){
					x += dx[dir]; y += dy[dir];
					flag = false; map[y][x] = '#';
				}else if(flag){
					break;
				}else{
					dir = (dir + 1) % 4;
					flag = true;
				}			
			}
			for(int i = 2; i < n+2; ++i){
				for(int j = 2; j < n+2; ++j) System.out.print(map[i][j]);
				System.out.println();
			}
			if(d > 0) System.out.println();
		}
	}
}

Nature of Prime Numbers(AOJ No.0142)

nが与えれる。
S = \{ i^2 \bmod n | 1\leq i < n \}
(i, j)　 i\in S, j\in S, i\neq j について、
x \leftarrow i-j
x \leftarrow x + n　 (x<0)
x \leftarrow n - x 　 (x > (n-1)/2)
の操作を行い、xの頻度表を作る。
制約
n < 10000
nは奇数

コード

O(n^2) = 10^8
普通にやるだけでは駄目だと思い込んでいたが、そんなことは無かった。

import java.util.*;
public class aoj0142 {
	static final Scanner stdin = new Scanner(System.in); 
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt();
			if(n == 0) break;
			int[] freq = new int[(n-1)/2+1];
			Arrays.fill(freq, 0);
			Set<Integer> set = new HashSet<Integer>();
			for(int i = 1; i < n; ++i) set.add(i*i%n);
			Integer[] a = set.toArray(new Integer[set.size()]);
			for(int i = 0; i < a.length; ++i){
				for(int j = 0; j < a.length; ++j){
					if(i == j) continue;
					int x = a[i] - a[j];
					if(x < 0) x += n;
					if(x > (n-1)/2) x = n - x;
					freq[x]++;
				}
			}
			for(int i = 1; i < freq.length; ++i) System.out.println(freq[i]);
		}
	}
}

Altair and Vega(AOJ No.0143)

三角形の3頂点の位置P1(xp1,yp1), P2(xp2,yp2), P3(xp3,yp3)
牽牛の位置K(xk,yk)
織女の位置S(xs,ys)
が与えられ、三角形の内側と外側で領域が分かれている。
牽牛と織女が同じ領域にいるかどうかを判定する。

アルゴリズム

以前作った点が多角形の内部にあるかどうかを判定するライブラリ(http://kanetai.hatenablog.com/entry/20120610/1339328126)を使う。
あるいは、面積△P1P2P3 = △xP2P3 + △P1xP3 + △P1P2x となるかどうかで判定

コード

import java.util.*;
import java.awt.geom.*;
public class aoj0143 {
	static final Scanner stdin = new Scanner(System.in);
	static final double EPS = 1e-10;
	static final Solver solver = Solver.CONTAINS;
	public static void main(String[] args) {
		int n = stdin.nextInt();
		while(n-- > 0){
			Point[] p = new Point[3];
			for(int i = 0; i < 3; ++i) p[i] = new Point(stdin.nextDouble(), stdin.nextDouble());
			Point k = new Point(stdin.nextDouble(), stdin.nextDouble());
			Point s = new Point(stdin.nextDouble(), stdin.nextDouble());
			System.out.println(solver.solve(p, k, s) ? "OK" : "NG");
		}
	}
	static enum Solver {
		CONTAINS {
			@Override boolean solve(Point[] p, Point k, Point s){ return contains(p, k) != contains(p, s);}
		}, SQUARE {
			@Override boolean solve(Point[] p, Point k, Point s){
				double S = square(p), Sk = 0, Ss = 0;
				for(int i = 0; i < 3; ++i){
					Point temp = p[i];
					p[i] = k; Sk += square(p);
					p[i] = s; Ss += square(p);
					p[i] = temp;
				}
				return equal(S, Sk) != equal(S, Ss);
			}
		};
		boolean solve(Point[] p, Point k, Point s){ return true; }
	}
	public static boolean equal(double a, double b){ return Math.abs(a-b) < EPS; }
	public static boolean leq(double a, double b){ return a - b < EPS; }
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,y); }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		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; }
	} //class Point
	public static boolean contains(Point[] polygon, Point p) {
		boolean in = false;
		for (int i = 0, n = polygon.length; i < n; ++i) {
			Point a = polygon[i].sub(p), b = polygon[(i+1)%n].sub(p);
			if (a.y > b.y){ Point temp = b; b = a; a = temp; }
			if (a.y <= 0 && 0 < b.y) //点pからxの正方向への半直線が多角形の頂点をとおるとき、最終的に交差数を偶数回にするためどちらかを<=ではなく、<にする
				if (a.cross(b) < 0) in = !in; //=0 -> a//b -> on 
			if (equal(a.cross(b), 0) && leq(a.dot(b), 0)) return true; //on edge
		}
		return in; //in out
	}
	public static double square(Point[] polygon){
		int n = polygon.length;
		double res = 0.0;
		for(int i = 0; i < n; ++i){
			Point cur = polygon[i], next = polygon[(i+1)%n];
			res += (cur.x + next.x)*(cur.y - next.y);
		}
		return Math.abs(res/2.0);
	}
}

Packet Transportation(AOJ No.0144)

有向グラフと、パケットの始点s, 終点e, TTL(Time to Live)が与えられて、
sからeに到達する最短時間(ホップ数+1)を求める。最短到達時間>TTLなら"NA"と答える。

コード

ワーシャルフロイドでおk
ノード数nのとき、ノード番号が1〜nまでの自然数で振られるとは問題に書いてなかったので、名前表を作った。

import java.util.*;
public class aoj0144 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2;
	static int idx = 0;
	static Map<String, Integer> name;
	static int[][] M;
	static int get(String s){
		if(name.containsKey(s)) return name.get(s);
		name.put(s, idx);
		return idx++;
	}
	public static void main(String[] args) {
		int n = stdin.nextInt(); stdin.nextLine();
		name = new HashMap<String, Integer>(n+n);
		M = new int[n][n];
		for(int i = 0; i < n; ++i){
			Arrays.fill(M[i], INF);
			M[i][i] = 0;
		}
		for(int i = 0; i < n; ++i){
			String[] s = stdin.nextLine().split(" ");
			int src = get(s[0]);
			for(int j = 2; j < s.length; ++j) M[src][get(s[j])] = 1;
		}
		APSPResult res = FloydWarshall(M);
		int p = stdin.nextInt(); stdin.nextLine();
		for(int i = 0; i < p; ++i){
			String[] s = stdin.nextLine().split(" ");
			int ans = res.getDist(get(s[0]), get(s[1])) + 1;
			System.out.println(ans >= INF || ans > Integer.parseInt(s[2]) ? "NA" : ans );
		}
	}
	@SuppressWarnings("unused") public static class APSPResult{
		private int[][] dist; // dist[d]:= shortest path to d
		private int[][] prev; // back pointers
		private boolean hasNegativeCycle;
		public APSPResult(int[][] dist, int[][] prev, boolean hasNegativeCycle){ set(dist, prev, hasNegativeCycle); }
		final private void set(int[][] dist, int[][] prev, boolean hasNegativeCycle){ this.dist = dist; this.prev = prev; this.hasNegativeCycle = hasNegativeCycle; }
		final public int getDist(int i, int j){ return dist[i][j]; }
	}
	public static APSPResult FloydWarshall(int[][] G){
		int n = G.length;
		int[][] prev = new int[n][n], dist = new int[n][n];
		for(int i = 0; i < n; ++i){
			System.arraycopy(G[i], 0, dist[i], 0, n);
			dist[i][i] = 0;
			for(int j = 0; j < n; ++j) prev[i][j] = (G[i][j] != INF ? i : -1);
		}
		for(int k = 0; k < n; ++k){
			for(int i = 0; i < n; ++i){
				if(dist[i][k] >= INF) continue;
				for(int j = 0; j < n; ++j){
					int newDist = dist[i][k] + dist[k][j];
					if(dist[i][j] > newDist){
						dist[i][j] = newDist;
						prev[i][j] = prev[k][j];
					}
				}
			}
		}
		boolean hasNegativeCycle = false;
		for(int i = 0; i < n; ++i) if(dist[i][i] < 0){ hasNegativeCycle = true; break; }
		return new APSPResult(dist, prev, hasNegativeCycle);
	}
}

Cards(AOJ No.0145)

数字が書かれたカードの山iがn個ある。
山の一番上のカードの数字 a_iと一番下のカードの数字 b_iが与えられる。( 0\leq i < n)
隣り合う山iとi+1をマージすると一番上のカードが a_i, 一番したのカードが b_{i+1}になって、マージコストに a_i b_i a_{i+1} b_{i+1}かかる。
全てマージして山を一つにしたときの最小コストを求める。
制約
n \leq 100
最大マージコスト \leq 2^{31}-1

アルゴリズム

DP_{i, j}を山iから山jをマージするための最大コストとする。
初期値は、 DP_{i,j} = \left\{ \begin{array}{lr} \infty & (i\neq j) \\ 0 & (i=j) \end{array} \right.
計算は、 0\leq i < n, 0 \leq j < n, i \leq k < jについて、
DP_{i,j} = \min \{ DP_{i, j}, DP_{i, k} + DP_{k+1, j} + a_i b_k a_{k+1} b_j \}

コード

ループでDPしようとしたら、ループの順序間違って、WAだした。
となり同士をマージして段々i,jの範囲(d)を広げながら、一番内側でkをまわさないといけない(solve1)
この場合、メモ化再帰で解く方が簡単かなぁ(solve2)

import java.util.*;
public class aoj0145 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2;
	static int n, a[], b[], dp[][];
	static Solver solver = Solver.SOLVE1;
	public static void main(String[] args) {
		n = stdin.nextInt(); dp = new int[n][n];
		a = new int[n]; b = new int[n];
		for(int i = 0; i < n; ++i){
			a[i] = stdin.nextInt();
			b[i] = stdin.nextInt();
			for(int j = 0; j < n; ++j) dp[i][j] = (i == j ? 0 : INF);
		}
		System.out.println(solver.solve());
	}
	static enum Solver {
		SOLVE1 { @Override int solve(){
			for(int d = 0; d < n; ++d){
				for(int i = 0; i+d < n; ++i){
					int j = i + d;
					for(int k = i; k < j; ++k){
						dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + a[i]*b[k]*a[k+1]*b[j] );
					}
				}
			}
			return dp[0][n-1];
		}}, SOLVE2 { @Override int solve(){ return rec(0, n-1); }
		int rec(int i, int j){
			if(i == j) return 0;
			if(dp[i][j] < INF) return dp[i][j];
			for(int k = i; k < j; ++k) dp[i][j] = Math.min(dp[i][j], rec(i, k) + rec(k+1, j) + a[i]*b[k]*a[k+1]*b[j]);
			return dp[i][j];
		}
		};
		int solve(){ return 0;}
	}
}