Lupin The 4th(AOJ No.0146), Fukushimaken(AOJ No.0147), Candy and Class Flag(AOJ No.0148), Eye Test(AOJ No.0149)

Lupin The 4th(AOJ No.0146)

屋敷から $x_i$ mの距離の蔵iに１個20kgの宝が $w_i$ 個ある。
蔵は全て、屋敷から同じ方向に向かって一直線上にある。
蔵にある宝を拾いながら、全ての蔵をまわる。
始点と終点はどこでも良い。
宝を $w$ kg持っているときの移動速度は $2,000/(70+w)$ m/分。
最短移動時間となる経路を求める。
制約
$0 \leq i < n$
$i < 15$
$w_i < 10000$

アルゴリズム

$O(2^n n^2)$ のビットDP
状態 $(S, v)$
$S$ : 到達済み頂点集合, $v$ : 最後に到達した頂点
$W_S = \sum_{v\in S} 20w_v$
$d(S, i, j) = \frac{|x_i - x_j|}{2000/(70+W_S)}$ : 状態 $(S,i)$ から $(S\cup j, j)$ に遷移するのにかかる時間
$DP_{S,v}$ : 状態 $(S, v)$ になるまでの最短時間
と定義する。
初期化
$DP_{S,v} = \left\{ \begin{array}{ll} 0 & (v \in V, S=\{v\} )\\ \infty & (otherwise) \end{array}\right.$
更新
$DP_{S\cup j, j} = \min\{ DP_{S,i} + d(S, i,j) | i\in S, j\not \in S \}$
経路はminをとるとき、バックポインタを記憶して、あとでバックトレースする。
初期化をちょっと変更すると、巡回セールスマン問題になる。

コード

移動距離をMath.abs(d[i]-d[j])*(70+W[S])/2000.0とすると誤差?でWrongAnswerになった。

import java.util.*;
public class aoj0146 { //状態(S, v) S: 到達済み頂点集合, v: 最後に到達した頂点
	static final Scanner stdin = new Scanner(System.in);
	static final double INF = 1e15; 
	static int[] name; //name[i]: ノードiの倉番号
	static int[] d; //d[i]: 屋敷からノードiへの距離
	static int[] w; //w[i]: ノードiの宝の総重量
	static int[] W; //W[S]: 状態Sでの宝の総重量 
	static double[][] DP; //DP[S][v]: 状態(S, v)になるまでの最短時間
	static int[][] B; //B[S][v]: バックポインタ
	static double getTime(int i, int j, int S){ //状態(S,i)から(S∪j, j)に遷移するのにかかる時間
		return Math.abs(d[i]-d[j])/(2000.0/(70+W[S])); //Math.abs(d[i]-d[j])*((70+W[S])/2000.0)
	}
	public static void main(String[] args) {
		int n = stdin.nextInt();
		name = new int[n]; d = new int[n]; w = new int[n];
		DP = new double[1<<n][n]; B = new int[1<<n][n];
		W = new int[1<<n];
		for(double[] i: DP) Arrays.fill(i, INF);
		for(int i = 0; i < n; ++i){
			name[i] = stdin.nextInt();
			d[i] = stdin.nextInt(); w[i] = 20 * stdin.nextInt();
			DP[1<<i][i] = 0; B[1<<i][i] = -1;
		}
		//W[S]: 状態Sでの重さ
		for(int S = 0; S < (1<<n); ++S){
			W[S] = 0;
			for(int i = 0; i < n; ++i) if((S>>i & 1) == 1) W[S] += w[i];
		}
		List<Integer> ans = solve1(n);
		for(int i = 0; i < ans.size(); ++i) System.out.print(name[ans.get(i)] + (i < ans.size()-1 ? " " : "\n"));
	}
	static List<Integer> solve1(int n){
		int N = 1<<n;
		for(int S = 1; S < N; ++S){
			for(int i = 0; i < n; ++i){
				if( (S & (1<<i)) == 0) continue;
				for(int j = 0; j < n; ++j){
					if((S & (1<<j)) == 0){
						double temp = DP[S][i] + getTime(i, j, S);
						if(DP[S|(1<<j)][j] > temp){
							DP[S|(1<<j)][j] = temp;
							B[S|(1<<j)][j] = i;
						}
					}
				}
			}
		}
		ArrayList<Integer> res = new ArrayList<Integer>(n);
		double m = INF;
		int x = -1;
		for(int i = 0; i < n; ++i) if(m > DP[N-1][i]){
			m = DP[N-1][i];
			x = i;
		}
		buildPath(x, N-1, res);
		return res;
	}
	static void buildPath(int s, int S, List<Integer> path){
		if(S != 0) buildPath(B[S][s], S & ~(1<<s), path);
		else return; //B[0][s] = -1はpathに加えない
		path.add(s);
	}
}

Fukushimaken(AOJ No.0147)

0番から99番までの100組のグループが来ます。
i番目のグループは正午から 5i 分後にお店に到着します。
i番目のグループの人数は i%5 が 1 のとき5人、それ以外のときは2人です。
i番目のグループは、席に着くと 17(i%2)+3(i%3)+19 分間で食事を済ませます。
席には0から16までの番号が付いています。
x人のグループは連続してx個あいている席があった時だけ着席できます。
お客さんは1分単位で出入りします。各時刻には次の順序でお客さんを案内します。
前のグループの離席と同時に次のグループの着席が可能となります。
お客さんを着席させる際には、行列の先頭にいるグループから順に、できる限り多くのグループを同じ時刻に着席させます。行列の順序を追い越すことはしません。つまり、先頭のグループが着席できなければ、行列内の他のグループが着席できたとしても、着席させません。

nが与えられて、グループnの待ち時間を求める。
制約
$n < 100$

コード

ただのシミュレーション。
グループの到来時間、人数、食事時間をグループごとに求めておく。
着席するときに、現在時間 - 到来時間で待ち時間を求める。
現在時間のインクリメントのタイミングを間違えないようにする。

import java.util.*;
public class aoj0147 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 100, M = 17;
	static final int[] ans = new int[N], q = new int[M];
	static Group[] g = new Group[N];
	public static void main(String[] args){
		for(int i = 0; i < N; ++i) g[i] = new Group(i);
		Arrays.fill(q, 0); Arrays.fill(ans, 0);
		int time = 0, cur = 0;
		while(cur < N){
			while(cur < N && g[cur].hitting <= time){ //次の人が到来している
				int i = insIndex(g[cur].n);
				if(i != -1){
					for(int j = i; j < i+g[cur].n; ++j) q[j] = g[cur].meal; //着席
					ans[g[cur].id] = time - g[cur].hitting;
					cur++;
				}else{
					break;
				}
			}
			time++;
			for(int i = 0; i < M; ++i) if(q[i] > 0) q[i]--;
		}
		while(stdin.hasNext()) System.out.println(ans[stdin.nextInt()]);
	}
	static int insIndex(int length){
		int count = 0;
		for(int i = 0; i < M; ++i){
			if(q[i] == 0){
				if(++count == length) return i - length + 1;
			}else{
				count = 0;
			}
		}
		return -1; //挿入不可
	}
	static class Group{
		int id, n, hitting, meal;
		Group(int i){
			id = i; //グループ番号
			n = (i%5 == 1 ? 5 : 2); //人数
			hitting = 5 * i; //到達時刻
			meal = 17*(i%2) + 3*(i%3) + 19; //食事時間
		}
	}
}

Candy and Class Flag(AOJ No.0148)

nが与えられる。
「次にお前はprintf("3C%02d\n", (n-1)%39+1)と言う」
「printf("3C%02d\n", (n-1)%39+1) …ハッ!」

コード

import java.util.*;
public class aoj0148 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 39;
	public static void main(String[] args) {
		while(stdin.hasNext()) System.out.printf("3C%02d\n", (stdin.nextInt()-1)%N+1);
	}
}

Eye Test(AOJ No.0149)

複数の左右の目の視力が与えられて、

A 1.1以上
B 0.6以上1.1未満
C 0.2以上0.6未満
D 0.2未満

で左右の目を視力検査し、左右それぞれについてA〜D判定になった人数を答える。

コード

import java.util.*;
public class aoj0149 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 4;
	static int[] l = new int[N], r = new int[N];
	static int eyesight(double x){ return (x >= 1.1 ? 0 : x >= 0.6 ? 1 : x >= 0.2 ? 2 : 3); }
	public static void main(String[] args) {
		Arrays.fill(l, 0); Arrays.fill(r, 0);
		while(stdin.hasNext()){
			l[eyesight(stdin.nextDouble())]++;
			r[eyesight(stdin.nextDouble())]++;
		}
		for(int i = 0; i < N; ++i) System.out.println(l[i] + " " + r[i]);
	}
}

kanetaiの二次記憶装置

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