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)
Traveling Alone: One-way Ticket of Youth(AOJ No.0200)
グラフG(V,E)が与えられる。エッジのコストは料金(cost)と時間(time)の2種類ある。
クエリがk個、(スタートノードs、ゴールノードg、cost or time)の形で与えられて、再短時間または最小料金を求める。
制約
0 < エッジコスト < 1,001
コード
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)
練金釜でアイテムを錬成するか、購入するかしてアイテムを手に入れることができる。
アイテムの売価のリスト
錬金レシピ
が与えられたとき、アイテムtを手に入れるための最小コストを求める。
制約
各アイテムの数量に限りはない。
アイテムは複数のレシピに使われることがあるが、1 つのアイテムを作るためのレシピはたかだか1。
アルゴリズム
各アイテムの手に入れるためのコストv(アイテム)の基底をアイテムの売価として、錬成できる場合は、
v(アイテム)=v(材料)で更新する。
更新が行われなくなるまで反復更新する。反復が終了したら、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)
料理の金額表と予算額が与えられて、予算額以内で料理を注文する。
どんな人数でも割り勘できない、かつ、できるだけ高くなるように注文したときの金額pを答える。
そのようなpが求まらない場合はNAと答える。
※とする。
制約
料理は同じ物をいくつ頼んでも良い
アルゴリズム
上記※を呼び飛ばしてて、(゚Д゚≡゚д゚)エッ!?ってなった。
要するに、料理をいくつか注文して予算額以内で、金額を素数にしたときの最大値を求める。
エラトステネスの篩で[0, 1000000]の素数を求めておく。
で初期化し、
で更新する。
コード
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)
のマップが与えられて、マップにはSAFE(何も無い)、UNSAFE(障害物)、JUMP(ジャンプ台)の属性がある。マップの左右にはみ出しては行けない。
下、右下、左下に進行可能。ただしジャンプ台は真上から乗らないといけない。ジャンプ代に乗るとさらに2マス下にすすむ。
から初めて、に侵入する経路は行くつかるかを答える。
制約
にはジャンプ台は無い。
コード
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); } } }