Eleven Puzzle(AOJ No.0190), Baby Tree(AOJ No.0191), Tsuruga Parking(AOJ No.0192), Deven-Eleven(AOJ No.0193)

Eleven Puzzle(AOJ No.0190)

		■
	1	2	3
4	5	6	7	8
	9	10	11
		■

の形に持っていく11パズルの最小ステップ数を答える。
ただし、20ステップ以内で解けなければNAと答える。

■の上下左右で次の状態は多くて8個ある。
２０ステップ考えたとき、全状態数は、最悪 $8^{20} \approx 10^{18}$ ぐらいのオーダーになる。
幅優先なんかしたら終わらない。つーかメモリがヤバい。
なんで $A^*$ を使う。
$g^*(n)=$ 状態 $n$ になるまでのステップ数(探索木の深さ), $h^*(n)=$ マンハッタン距離(の和)
Manhattan距離(市街地距離(city block distance)) $d(a,b)=|x_a-x_b|+|y_a-y_b|$
$h^*(n)=g^*(n)+h^*(n)$ が20を超えたら枝刈りすればいい。
計算量よく分からん。
ちなみに、もうちょい効率化するには、両側探索すればいいはず。
終了状態は決まっているので、終了状態から例えば10ステップ分計算して置けばもっと速く終了する(オーバヘッドを考慮すると5stepぐらいがいいのかもしれない).
これくらいなら( $8^{10} = 1,073,741,824$ )計算量的には何とかなりそう?

コード

Javaで00.17 secならそこそこなのでは？
両側探索はしてない。めんどいから。状態は16進数にしてつなげた文字列。範囲外のところは' 'にしてある。

import java.util.*;
public class aoj0190 {
	static final Scanner stdin = new Scanner(System.in);
	static final String goal = "  0   123 45678 9ab   0  ";
	static final boolean f[] = {false, false, true, false, false,
				    false, true,  true, true,  false,
				    true,  true,  true, true,  true,
				    false, true,  true, true,  false,
				    false, false, true, false, false};
	static final int M = 5, D = 4;
	static final int gx[]={2,1,2,3,0,1,2,3,4,1,2,3,2};
	static final int gy[]={0,1,1,1,2,2,2,2,2,3,3,3,4};
	static final int ManhattanDistance(int x, int y, int g){ return Math.abs(x-gx[g]) + Math.abs(y-gy[g]); }
	static final int dx[]={0, 1, 0,-1};
	static final int dy[]={-1,0, 1, 0};
	static final boolean check(int x, int y){
		int i = y*M+x;
		return 0 <= i && i < goal.length() && f[i];
	}
	static class T implements Comparable<T>{
		String state;
		int step;
		int score;
		T(String state, int step){
			this.state = state;
			this.step = step;
			score = step;
			for(int i = 0; i < state.length(); ++i){
				char c = state.charAt(i);
				if(c == '0' || c==' ') continue;
				int g = (Character.isDigit(c) ? c - '0' : c - 'a' + 10);
				int y = i/M, x = i - M*y;
				score += ManhattanDistance(x, y, g);
			}
		}
		@Override public int compareTo(T o) { return score - o.score; }
	}
	public static void main(String[] args) {
		int i;
		while((i = stdin.nextInt())!= -1){
			StringBuilder sb = new StringBuilder("  "); sb.append(Integer.toHexString(i)); sb.append("  ");
			for(int y = 1; y < M; ++y)
				for(int x = 0; x < M; ++x)
					sb.append(f[y*M+x] ? Integer.toHexString(stdin.nextInt()): " ");
			int ans = AStar(sb.toString());
			System.out.println(ans < 0 ? "NA" : ans);
		}
	}
	static int AStar(String s){
		Queue<T> q = new PriorityQueue<T>();
		Set<String> closed = new HashSet<String>();
		int[] zero = new int[2], zx = new int[2], zy = new int[2];
		q.add(new T(s, 0));
		while(!q.isEmpty()){
			T e = q.poll();
			if(e.state.equals(goal)) return e.step;
			if(closed.contains(e.state)) continue;
			closed.add(e.state);
			zero[0] = e.state.indexOf("0"); zero[1] = e.state.indexOf("0", zero[0]+1);
			zy[0] = zero[0]/M; zx[0] = zero[0] - zy[0]*M; zy[1] = zero[1]/M;  zx[1] = zero[1] - zy[1]*M;
			for(int k = 0; k < 2; ++k){
				for(int i = 0; i < D; ++i){
					int nx = zx[k]+dx[i], ny = zy[k]+dy[i], n = ny*M + nx;
					if(check(nx, ny)){
						char[] nstate = e.state.toCharArray();
						nstate[zero[k]] = nstate[n]; nstate[n] = '0';
						T nt = new T(new String(nstate), e.step+1);
						if(nt.score <= 20) q.add(nt);
					}
				}
			}
		}
		return -1;
	}
}

Baby Tree(AOJ No.0191)

与える肥料をj, 以前に与えた肥料をkとしたとき、苗木がf(k,j)倍の大きさになる。
肥料[0,n)をm回使って、苗木が何倍の大きさになるかを答える。
ただし、初回はどの肥料を使っても、苗木の大きさは変わらない。

アルゴリズム

$DP_{i,j}:=i$ 番目に肥料 $j$ を与えたときの最大の大きさ(倍率)
$DP_{1,j}= 1$ で初期化
$2\leq i\leq m, 0\leq j < n$ について $DP_{i,j} = \min_{k}\{ f(k,j)DP_{i-1,k}\}$ で反復
答えは $\min_j \{ DP_{m,j}\}$
$O(mn^2)$

コード

import java.util.*;
public class aoj0191 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt(), m = stdin.nextInt();
			if((n|m) == 0) break;
			double[][] factor = new double[n][n];
			for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) factor[i][j] = stdin.nextDouble();
			double[][] DP = new double[2][n]; Arrays.fill(DP[0], 1.0);
			for(int i = 0; i < m-1; ++i){
				Arrays.fill(DP[(i+1)%2], -1);
				for(int j = 0; j < n; ++j) //j:current state
					for(int k = 0; k < n; ++k) //k:previous state
						DP[(i+1)%2][j] = Math.max(DP[(i+1)%2][j], factor[k][j]*DP[i%2][k]);
			}
			double ans = -1;
			for(int j = 0; j < n; ++j) ans = Math.max(ans, DP[(m-1)%2][j]);
			System.out.printf("%.2f\n", ans);
		}
	}
}

Tsuruga Parking(AOJ No.0192)

鶴ヶ駐車場の設備
- 駐車スペースは1つ以上あり、全て2段式駐車装置が設置されています。
- 各駐車スペースには1から順に番号が割り振られています。
- 初めは駐車場に1台も駐車していないものとします。
車を止める時
- 駐車する車の駐車時間が管理人に知らされます。
- 1台も駐車されていない駐車スペースから先に駐車していきます。
- 1台も駐車されていない駐車スペースがない場合には、空いている駐車スペースに駐車します。ただし、そのような駐車スペースが複数あるときは以下の手順で駐車します。
  - 駐車してある車の残り駐車時間が駐車しようとしている車の駐車時間以上のものがある場合、その差が一番小さい駐車スペースに駐車します。
  - 駐車してあるどの車の残り駐車時間も駐車しようとしている車の駐車時間未満である場合、その差が一番小さい駐車スペースに駐車します。
- 満車(空いている駐車スペースがない)の場合、駐車しようとする車は駐車スペースが空くまで順番に待ちます。空いたと同時に、最初に待っていた車から順に駐車します。

※各条件において、該当する駐車スペースが複数ある場合は駐車スペース番号の最も小さいところに駐車することとします。また、同時刻に出庫する車がある場合は、出庫する車がすべて出てから駐車を始め、待っている車がある限り、駐車できるだけの車が同時刻に駐車することとします。

車が出る時
- 管理人に知らされた駐車時間を過ぎた車は出庫します。
- 複数の駐車スペースで同時に駐車時間を過ぎた車があった場合、駐車スペース番号の小さい車から先に出庫します。
- 上段に駐車した車の駐車時間が過ぎた場合、下段の車が出庫するまで待たなければなりません。上段の車は下段の車が出庫した後、同時刻に出庫します。

駐車スペースの数 m、駐車する車の台数 n、各車の駐車時間 t を入力とし、駐車場から出てくる順番に車の整理番号を出力する

コード

実装ゲー　ツマンネ
駐車出来なかった車が10分おきに駐車しに来るんじゃなくて、10分ごとに駐車権利を持つ車が待ち行列に並んで、空きができ次第、待ち行列から車(複数台もあり得る)を出す。

import java.util.*;
public class aoj0192 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE;
	public static void main(String[] args) {
		while(true){
			int m = stdin.nextInt(), n = stdin.nextInt();
			if((m|n) == 0)break;
			int[] t = new int[n+1];
			for(int i = 1; i <= n; ++i)t[i] = stdin.nextInt();
			int[][] P = new int[m][2];
			for(int i = 0; i < m; ++i) Arrays.fill(P[i], 0);
			List<Integer> ans = new LinkedList<Integer>();
			Queue<Integer> q = new LinkedList<Integer>();
			int r = 10;
			while(ans.size() < n){
				if(r%10 == 0 && 1 <= r/10 && r/10 <= n) q.add(r/10);
				for(int i = 0; i < m; ++i) for(int j = 0; j < 2; j++) if(P[i][j] > 0) t[P[i][j]]--;
				for(int i = 0; i < m; ++i){
					if(P[i][0] > 0 && t[P[i][0]] <= 0){
						ans.add(P[i][0]); P[i][0] = P[i][1]; P[i][1] = 0;
						if(P[i][0] > 0 && t[P[i][0]] <= 0){ //出した後にもう一回確認
							ans.add(P[i][0]); P[i][0] = 0; 
						}
					}
				}
				boolean flag = true;
				while(!q.isEmpty() && flag){
					flag = false;
					int dm = INF, um = INF, di = -1, ui = -1;
					for(int i = 0; i < m; i++){
						if(P[i][0] == 0){
							flag = true;
							P[i][0] = q.poll();
							break;
						}
						if(P[i][1]==0){
							if(t[P[i][0]] >= t[q.peek()]){
								if(t[P[i][0]]-t[q.peek()] < um){ um = t[P[i][0]]-t[q.peek()]; ui = i; }
							}else{
								if(t[q.peek()]-t[P[i][0]] < dm){ dm = t[q.peek()]-t[P[i][0]]; di = i; }
							}
						}
					}
					if(flag)continue;
					if(ui >= 0){
						P[ui][1] = P[ui][0]; P[ui][0] = q.poll(); flag = true;
					}else if(di >= 0){
						P[di][1] = P[di][0]; P[di][0] = q.poll(); flag = true;
					}
				}
				r++;
			}
			for(int i = 0; i < n; ++i) System.out.print(ans.get(i) + (i == n-1 ? "\n" : " "));
		}
	}
}

Deven-Eleven(AOJ No.0193)

この図のような六角座標系を考える。
既設コンビニの座標 $(x_i, y_i), 0 \leq i < s$ と、新店舗建設候補地座標 $(p_j, q_j), 0 \leq j < t$ が与えられる。ここで、与えられる座標の最大値は $m,n$ ( $0 < x_i, p_j \leq m$ 、 $0 < y_i, q_j \leq n$ )。
座標上のマスは、マスからの距離(あるマスと隣接するマスの間の距離は１)が最も小さいコンビニによってカバーされていると考える(最近いコンビニが複数ある場合は、どのコンビニにもカバーされていないと考える)。新店舗建設候補地のうち最も広いカバー範囲を答える。
制約
$1 < m, n \leq 100$
$0 < s, t \leq 10$

アルゴリズム

やるだけ。
はじめに、各マスから最短の既設コンビ二までの距離をBFSで求めておく。
次に、各新店舗建設候補座標からの距離が先ほど求めた近接コンビにまでの距離より小さければカバー範囲としてカウントする。こちらもBFSで求める。一番カバー範囲が大きいのが答え。
$O(nm(s+t))$
座標系は、奇数行と偶数行で１つずらしたタイプの六角座標系なので、近傍座標を求めるため方向ベクトルについては、奇数行用のものと偶数行用のものを用意しとけばいい。

コード

フラグでBFSが最短距離を更新するか、カバー範囲を求めるのかを切り替えるようにした。
座標は、0スタートになるように入力から-1してる。

import java.util.*;
public class aoj0193 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2, X = 0, Y = 1, D = 2, HEX = 6;
	static final int dx[][] = { {-1, 0, 1, 0,-1,-1}, {0,  1, 1, 1, 0,-1} };
	static final int dy[][] = { {-1,-1, 0, 1, 1, 0}, {-1,-1, 0, 1, 1, 0} };
	static int m, n;
	static int[][] d;
	public static void main(String[] args) {
		while(true){
			m = stdin.nextInt(); n = stdin.nextInt();
			if((m|n) == 0) break;
			d = new int[n][m]; for(int i = 0; i < n; ++i) Arrays.fill(d[i], INF);
			int s = stdin.nextInt();
			for(int i = 0; i < s; ++i) BFS(stdin.nextInt()-1, stdin.nextInt()-1, true);
			int ans = 0, t = stdin.nextInt();
			for(int i = 0; i < t; ++i) ans = Math.max(ans, BFS(stdin.nextInt()-1, stdin.nextInt()-1, false));
			System.out.println(ans);		
		}
	}
	static int BFS(int x, int y, boolean calcMinDist){
		int res = 0;
		Queue<int[]> q = new LinkedList<int[]>();
		boolean[][] closed = new boolean[n][m]; for(int i = 0; i < n; ++i) Arrays.fill(closed[i], false); 
		q.add(new int[]{x, y, 0});
		while(!q.isEmpty()){
			int[] e = q.poll();
			if(closed[e[Y]][e[X]]) continue;
			closed[e[Y]][e[X]] = true;
			if(d[e[Y]][e[X]] > e[D]){
				if(calcMinDist) d[e[Y]][e[X]] = e[D];
				res++;
			}
			for(int i = 0; i < HEX; ++i){
				int nx = e[X] + dx[e[Y]%2][i], ny = e[Y] + dy[e[Y]%2][i];
				if(0 <= nx && nx < m && 0 <= ny && ny < n) q.add(new int[]{nx, ny, e[D]+1});
			}
		}
		return res;
	}
}

kanetaiの二次記憶装置

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

Eleven Puzzle(AOJ No.0190), Baby Tree(AOJ No.0191), Tsuruga Parking(AOJ No.0192), Deven-Eleven(AOJ No.0193)

Eleven Puzzle(AOJ No.0190)

アルゴリズム

コード

Baby Tree(AOJ No.0191)

アルゴリズム

コード

Tsuruga Parking(AOJ No.0192)

コード

Deven-Eleven(AOJ No.0193)

アルゴリズム

コード