kanetaiの二次記憶装置

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

Traveling Alone: One-way Ticket of Youth(AOJ No.0200), Wrought Gold Master(AOJ No.0201), At Boss's Expense(AOJ No.0202), A New Plan of Aizu Ski Resort(AOJ No.0203)

Online Judge

リポジトリ

Traveling Alone: One-way Ticket of Youth(AOJ No.0200)

グラフG(V,E)が与えられる。エッジのコストは料金(cost)と時間(time)の２種類ある。
クエリがk個、(スタートノードs、ゴールノードg、cost or time)の形で与えられて、再短時間または最小料金を求める。
制約
0 < |V|\leq 100
0 < |E|\leq 3,000
0 < エッジコスト < 1,001
0 < k \leq 200

コード

Floyd-Warshall

import java.util.*;
public class aoj0200 {
	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;
			int[][] T = new int[m][m], C = new int[m][m];
			for(int i = 0; i < m; ++i){ Arrays.fill(T[i], INF); Arrays.fill(C[i], INF); }
			for(int i = 0; i < n; ++i){
				int a = stdin.nextInt()-1, b = stdin.nextInt()-1;
				int cost = stdin.nextInt(), time = stdin.nextInt();
				T[a][b] = T[b][a] = time;
				C[a][b] = C[b][a] = cost;
			}
			int k = stdin.nextInt();
			APSPResult t = FloydWarshall(T), c = FloydWarshall(C);
			for(int i = 0; i < k; ++i){
				int p = stdin.nextInt()-1, q = stdin.nextInt()-1, r = stdin.nextInt();
				System.out.println(r == 0 ? c.getDist(p, q) : t.getDist(p, q));
			}
		}
	}
	static final int INF = Integer.MAX_VALUE/2;
	@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);
	}
}

Wrought Gold Master(AOJ No.0201)

練金釜でアイテムを錬成するか、購入するかしてアイテムを手に入れることができる。
アイテムの売価のリスト (item_i price_i) (0 < i \leq n)
錬金レシピ (item_j, \{material_j\} ) (0 < j \leq m), |\{material_j\}|=k
が与えられたとき、アイテムtを手に入れるための最小コストを求める。
制約
0 < n,k \leq 100
0 \leq m \leq 100
0\leq price_i \leq 1,000,000
各アイテムの数量に限りはない。
アイテムは複数のレシピに使われることがあるが、1 つのアイテムを作るためのレシピはたかだか1。

アルゴリズム

各アイテムの手に入れるためのコストv(アイテム)の基底をアイテムの売価として、錬成できる場合は、
v(アイテム)= \sumv(材料)で更新する。
更新が行われなくなるまで反復更新する。反復が終了したら、v(t)を答えとして出力する。
関係ないアイテムの最小コストも求めていることになる。
本来ならメモ化再帰で必要なアイテムだけのv[アイテム]を求めればよいが、以前↑の方法で、解いてたので同じように解いた。

コード

売価リストに含まれないアイテムが錬成レシピに含まれる可能性もあるので、
Mapから値をとるときに、注意する。

import java.util.*;
public class aoj0201 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n;
		Map<String, Integer> value = new HashMap<String, Integer>();
		Map<String, ArrayList<String>> recipe = new HashMap<String, ArrayList<String>>();
		while((n = stdin.nextInt()) != 0){
			value.clear(); recipe.clear();
			while(n-- > 0) value.put(stdin.next(), stdin.nextInt());
			n = stdin.nextInt();
			while(n-- > 0){
				String dst = stdin.next();
				int m = stdin.nextInt();
				ArrayList<String> materials = new ArrayList<String>(m<<1);
				while(m-- > 0) materials.add(stdin.next());
				recipe.put(dst, materials);
			}
			String target = stdin.next();
			boolean flag = true;
			while(flag){
				flag = false;
				LOOP: for(String item: recipe.keySet()){
					int S = 0;
					for(String material: recipe.get(item)){
						if(!value.containsKey(material)) continue LOOP;
						S += value.get(material);
					}
					if(!value.containsKey(item) || value.containsKey(item) && value.get(item) > S){
						value.put(item, S);
						flag = true;
					}
				}
			}
			System.out.println(value.get(target));
		}
	}
}

At Boss's Expense(AOJ No.0202)

料理の金額表 c_iと予算額 xが与えられて、予算額以内で料理を注文する。
どんな人数でも割り勘できない、かつ、できるだけ高くなるように注文したときの金額pを答える。
そのようなpが求まらない場合はNAと答える。
※ p \neq 1,xとする。
制約
0 < i \leq 30
0 < x \leq 1000000
料理は同じ物をいくつ頼んでも良い

アルゴリズム

上記※を呼び飛ばしてて、(ﾟДﾟ≡ﾟдﾟ)ｴｯ!?ってなった。
要するに、料理をいくつか注文して予算額以内で、金額を素数にしたときの最大値を求める。
エラトステネスの篩で[0, 1000000]の素数を求めておく。
F_{c_i} \leftarrow true で初期化し、
F_{j} \leftarrow true if(F_{j} = false, F_{j-k} = true, k \in c)で更新する。

コード

import java.util.*;
public class aoj0202 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 1000000;
	static final boolean[] table = sieve(N);
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt(), x = stdin.nextInt();
			if((n|x) == 0) break;
			boolean[] flag = new boolean[x+1]; Arrays.fill(flag, false);
			int[] menu = new int[n];
			for(int i = 0; i < n; ++i){
				menu[i] = stdin.nextInt();
				if(menu[i] <= x) flag[menu[i]] = true;
			}
			for(int i = 0; i <= x; ++i){
				if(flag[i]) continue;
				for(int p: menu) if(i-p >= 0 && flag[i-p]) flag[i] = true;
			}
			int ans = -1;
			for(int i = x; i >= 0; --i) if(flag[i] && table[i]){ ans = i; break; }
			System.out.println(ans == -1 ? "NA" : ans);
		}
	}
	public static boolean[] sieve(int n){
		boolean[] ret = new boolean[n+1];
		Arrays.fill(ret, true);
		ret[0] = ret[1] = false;
		for(int i = 2; i*i <= n; ++i)
			if(ret[i]) for(int j = i*i; j <= n; j+=i) ret[j] = false;
		return ret;
	}
}

A New Plan of Aizu Ski Resort(AOJ No.0203)

X\times Yのマップが与えられて、マップにはSAFE(何も無い)、UNSAFE(障害物)、JUMP(ジャンプ台)の属性がある。マップの左右にはみ出しては行けない。
下、右下、左下に進行可能。ただしジャンプ台は真上から乗らないといけない。ジャンプ代に乗るとさらに２マス下にすすむ。
(1\leq x \leq X, 1)から初めて、 (1\leq x \leq X, y \geq Y,) に侵入する経路は行くつかるかを答える。
制約
1\leq X, Y \leq 15
(x, 1)にはジャンプ台は無い。

アルゴリズム

map_{x, y} \leftarrow \left\{ \begin{array}{lr} 1 & (y=1) \\ 0 & (otherwise) \end{array} \right.
で初期化。以下を 1\leq x \leq X, 2\leq y \leq Yについて、

  • (map_{x, y} = SAFE \vee map_{x,y}=JUMP) \wedge map_{x, y-1} = SAFE
    • DP_{x,y} += DP_{x,y-1}
  • map_{x, y} = SAFE \wedge map_{x-1, y-1} = SAFE
    • DP_{x,y} += DP_{x-1,y-1}
  • map_{x, y} = SAFE \wedge map_{x-1, y-1} = SAFE
    • DP_{x,y} += DP_{x+1,y-1}
  • (map_{x, y} = SAFE \vee map_{x,y} = JUMP) \wedge map_{x, y-2} = JUMP
    • DP_{x,y} += DP_{x, y-2}

を計算。
答えは、 \sum_{\{ x| map_{x,Y-1} = JUMP \} } DP_{x,Y-1} + \sum_{x} DP_{x,Y}

コード

import java.util.*;
public class aoj0203 {
	static final Scanner stdin = new Scanner(System.in);
	static final int SAFE = 0, UNSAFE = 1, JUMP = 2;
	static final int dx[] = {-1, 0, 1};
	static final int dy[] = {1, 1, 1};
	public static void main(String[] args) {
		while(true){
			int X = stdin.nextInt(), Y = stdin.nextInt();
			if((X|Y) == 0) break;
			int[][] map = new int[Y+1][X+2], DP = new int[Y+1][X+2];
			Arrays.fill(map[0], UNSAFE); Arrays.fill(DP[0], 0);
			for(int i = 1; i <= Y; ++i){
				for(int j = 1; j <= X; ++j){
					map[i][j] = stdin.nextInt();
					DP[i][j] = i == 1 && map[i][j] == SAFE ? 1 : 0;
				}
				map[i][0] = map[i][X+1] = DP[i][0] = map[i][X+1] = 0; //UNSAFE
			}
			for(int y = 2; y <= Y; ++y){
				for(int x = 1; x <= X; ++x){
					if(map[y][x] == SAFE){
						for(int k = 0; k < 3; ++k)
							if(map[y-dy[k]][x-dx[k]] == SAFE) DP[y][x] += DP[y-dy[k]][x-dx[k]];
						if(map[y-2][x] == JUMP) DP[y][x] += DP[y-2][x];
					}
					if(map[y][x] == JUMP){
						if(map[y-1][x] == SAFE) DP[y][x] += DP[y-1][x];
						if(map[y-2][x] == JUMP) DP[y][x] += DP[y-2][x]; 
					}
				}
			}
			int ans = 0;
			for(int j = 1; j <= X; ++j){
				ans += DP[Y][j];
				if(map[Y-1][j] == JUMP) ans += DP[Y-1][j];
			}
			System.out.println(ans);
		}
	}
}