Life Game(AOJ No.0232), Book Arrangement(AOJ No.0233), Aizu Buried Treasure(AOJ No.0234)

リポジトリ

Life Game(AOJ No.0232)

人生ゲームをやって、ゴールしたときの金の期待値(小数点以下切り捨て)を求める。
進むマスを決めるルーレットは、X 等分に区分され、それぞれに V1、V2、...、Vx という値が記入されている。
ボードには、0 番、1 番、...、Y 番と番号がふられたマス目があり、順番につながっている。
マス目の中には、イベントマスと呼ばれる特別なマスが Z 個あり、そこに到達すると特別な動作を行う。
イベントマスのマス目の番号、イベントの種類、値が で与えられる。

E	イベント	値A
1	指定の数値だけ先へ進む	1~10
2	指定の数値の金額を得る	1~100
3	指定の数値の金額を支払う	1~100

最初の所持金は 0 円で、第 0 マス目からスタートし、第 Y マス目に到達するとゴールとなる。
ゴールを越えた場合もゴールと見なす。
スタートとゴールにイベントは無く、1 マスに複数のイベントが重ならない。
イベントによって進んだ先のマスのイベントは無視する。
所持金が 0円より少なくなる場合は 0 円とする。
制約
0 < X < 5
0 < Vi < 11

アルゴリズム

:=止まったマスp、所持金mになる確率
としてDPを解く。
状態(p, m)から状態(p', m')に遷移するパスがある場合、

していけばいい。
位置はイベントにより後ろに戻ること無く、必ず１以上進むので、
p=0から遷移できる状態の確率をインクリメントして、次にp=1から遷移できる状態の確率をインクリメントする...としていけば良い。
ゴールしたときの所持金の期待値は。

コード

進んだマスの先に、進むイベントマスがあったら...とか考えていた...
問題に"イベントによって進んだ先のマスのイベントは無視する。"って書いてんだダルルォ

import java.util.*;
public class aoj0232 {
	static final Scanner stdin = new Scanner(System.in);
	static final int NONE = 0, MOVE = 1, GET = 2, PAY = 3, MAX = 5001; // = 50 * 100 + 1
	public static void main(String[] args) {
		while (true) {
			int X = stdin.nextInt(), Y = stdin.nextInt(), Z = stdin.nextInt();
			if ((X|Y|Z) == 0) break;
			int[] V = new int[X];
			for (int i = 0; i < X; ++i) V[i] = stdin.nextInt();
			T[] map = new T[Y+1];
			for (int i = 0; i < map.length; ++i) map[i] = new T();
			for (int i = 0; i < Z; ++i) map[stdin.nextInt()].set(stdin.nextInt(), stdin.nextInt());
			double[][] DP = new double[Y+1][MAX];
			DP[0][0] = 1;
			for (int i = 0; i < Y; ++i) {
				for (int j = 0; j < MAX; ++j) {
					if (DP[i][j] == 0) continue;
					for (int k = 0; k < X; ++k) {
						int ni = Math.min(Y, i+V[k]), nj = j;
						T next = map[ni];
						switch(next.E) {
						case MOVE: ni = Math.min(Y, ni+next.A); break;
						case GET: nj += next.A; break;
						case PAY: nj = Math.max(0, nj-next.A); break;
						case NONE: default: break;
						}
						DP[ni][nj] += DP[i][j]/X;
					}
				}
			}
			double ans = 0;
			for (int j = 0; j < MAX; ++j) ans += j*DP[Y][j];
			System.out.println((int)ans);
		}
	}
	static class T {
		int E = NONE, A = 0;
		void set(int e, int a) { E = e; A = a; }
	}
}

Book Arrangement(AOJ No.0233)

マイナス10進数の()は、10進数では、

となる。
10進数の数字が与えられ、それをマイナス10進数になおす。
制約
マイナス十進数表示は 以上 未満に収まる

アルゴリズム

剰余を使えば直感的にできるかもしれないが、負数の剰余の結果は言語によって違ったり、不定だったりするのであまり使いたくない。
まず、基数を10にして、係数を-9 〜 9で表す。
次に、基数を-10にして、係数を-9 〜 9で表す。
最後に、基数を-10のままにして、負になっている係数は上位桁を繰り下げて?、係数を0 〜 9で表す。
例
与えられた十進数が-1944のとき、

	-(1,9, 4, 4)
	(-1,-9,-4,-4)
	(1, -9, 4,-4)
	(2, 1, 5, 6)

コード

import java.util.*;
public class aoj0233 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			String s = stdin.next();
			if (s.charAt(0) == '0') break;
			int sign = 1;
			if (s.charAt(0) == '-') {
				sign = -1;
				s = s.substring(1, s.length());
			}
			int[] a = new int[s.length()+2];
			for (int i = 0; i < s.length(); ++i, sign *= -1) a[i] = sign * (s.charAt(s.length()-1-i) - '0');
			for (int i = 0; i < a.length; ++i) {
				if (a[i] < 0) {
					a[i] += 10;
					a[i+1]++;
					if (a[i+1] >= 10) {
						a[i+1] -= 10;
						a[i+2]--;
					}
				}
			}
			int ans = 0;
			for (int i = 0, base = 1; i < a.length; ++i, base*=10) ans += base*a[i];
			System.out.println(ans);
		}
	}
}

Aizu Buried Treasure(AOJ No.0234)

容量m、初期酸素残量oの酸素ボンベがあり、初期発掘予算をfとし、地上の好きな位置から地層の最下層まで掘り進める。
地層の状態は W×Hの2 次元格子状に配置されたセルで表わされる。
セルの状態

• 土の詰まったセル。掘るのに、セルごとに決められた費用がかかる。
• 酸素のたまったセル。掘る必要はなく、セルごとに決まった量の酸素を補給できる。一度酸素を補給したセルの酸素はなくなり、再度の補給はできない。また、このセルに辿りついたら必ず酸素の補給をしなければならない。

あるセルから掘ることができるのは左右と下方向のセルのみ。
一度掘ったセルを左右に移動することはできるが上に移動することはできない。
酸素ボンベの残量がセルを移動するたびに 1 減る。
酸素ボンベの残量が0になった場合、その時点で到達失敗。
酸素ボンベの残量が 0 で埋蔵金の埋まっている深さまで到達しても、到達したとみなされない。
また、酸素のたまったセルでは酸素を補給することができるが、容量を超えた分は廃棄される。
W, H, f, m, o, セルの状態が与えられたとき、最下層にたどり着くための最小の発掘費用を答える。最小費用が発掘費用を超えてしまう場合または最下層に到達できない場合はNAと答える。
制約
2 < W, H < 11
0 < f < 10,001

アルゴリズム

(X, Y, O, C, S)
X, Y: 現在の座標
O：酸素残量
C:発掘費用
S: 深さYの層の発掘状況
として、Dijkstraで最小コストをもとめる。
一度掘った場所も左右に移動できることに注意する。
酸素ボンベの容量制限があるので、左右に掘った後、酸素を補給しにいくと良い場合がある。

コード

何度やってもWAなので、検索したところ、
のはずなのに、この制約が守られておらず、o < 3が入力されたりするみたい。
なので、o < 2が入力されたときは、必ずNAになる。
わかるわけないだろ...

import java.util.*;
public class aoj0234 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2, dx[] = {0,1,-1}, dy[] = {1,0,0};
	static class T implements Comparable<T>{
		int c, y, x, o, s;
		public T(int X, int Y, int O, int C, int S) { x = X; y = Y; o = O; c = C; s = S; }		
		@Override public int compareTo(T o) { return c - o.c; }
	}

	public static void main(String[] args) {
		while(true){
			final int W = stdin.nextInt(), H = stdin.nextInt();
			if((W|H) == 0) break;
			final int f = stdin.nextInt(), m = stdin.nextInt(), o = stdin.nextInt();
			int [][] air = new int[W][H], cost = new int[W][H];
			for(int y = 0; y < H; ++y) for(int x = 0; x < W; ++x) {
				int tmp = stdin.nextInt();
				if (tmp >= 0) air[x][y] = tmp;
				else cost[x][y] = -tmp;
			}
			System.out.println(solve(W,H,m,o,f,cost,air));
		}
	}
	static String solve(int W, int H, int m, int o, int f, int[][] cost, int[][] air) {
		int [][][][] minCost = new int[W][H][m + 1][1 << W];
		for(int x = 0; x < W; ++x) for(int y = 0; y < H; ++y) for(int o2 = 0; o2 <= m; ++o2) Arrays.fill(minCost[x][y][o2], INF);
		PriorityQueue<T> open = new PriorityQueue<T>();
		for(int x = 0; x < W; ++x) open.add(new T(x, -1, o, 0, 1 << x));

		String ans = "NA";
		while(!open.isEmpty()) {
			final T p = open.poll();
			if(p.y == H - 1) { ans = "" + p.c; break; }

			for(int i = 0; i < 3; i++){
				int ny = p.y + dy[i], nx = p.x + dx[i];
				if(ny == -1) continue;
				if(nx < 0 || nx >= W) continue;

				int nc = p.c, no = p.o - 1;
				if(no <= 0) continue;
				int ns = ((i == 0 ? 0 : p.s) | (1<<nx));
				if(i == 0 || ns != p.s) {
					nc += cost[nx][ny];
					no = Math.min(no + air[nx][ny], m);
				}
				if(nc > f) continue;
				if(minCost[nx][ny][no][ns] <= nc) continue;
				open.add(new T(nx, ny, no, nc, ns));
				minCost[nx][ny][no][ns] = nc;
			}
		}
		return ans;
	}
}