kanetaiの二次記憶装置

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

Jogging(AOJ No. 0211), Highway Express Bus(AOJ No. 0212)

Online judge

リポジトリ

Jogging(AOJ No.0211)

生徒の人数 n、生徒iのコースの 1 周の距離 d_i[km] 、各生徒の走る速さ v_i[km/h]を入力とし、全員が小学校を同時にスタートしてから次に同時にスタート地点に位置するのは、各生徒がそれぞれ何周したときかを出力する。
制約
1 < n \leq 10
1\leq d_i, v_i \leq 10,000
答え< 2^{31}-1

アルゴリズム

スタートしてから同時にスタート地点に位置するまでの時間をtとすると、生徒iの時間tでの周回数 a_iは
a_i = t\frac{v_i}{d_i}
v'_i = \frac{v_i}{GCD(v_i, d_i)}, d'_i = \frac{d_i}{GCD(v_i, d_i)}とおくと、
a_i = t \frac{v'_i GCD(v_i, d_i)}{d'_i GCD(v_i, d_i)} = t\frac{v'_i}{d'_i}
答えは、 \hat{a_i} = \min_t a_i = \min_t t\frac{v'_i}{d'_i}
\hat{a_i}は整数でなくてはならないことを考えると、
t = \frac{LCM_k(d'_k)}{GCD_k(v'_k)}

コード

1\leq d_i, v_i \leq 10,000ってお前ら人間じゃねぇ

import java.util.*;
public class aoj0211 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n;
		while ((n = stdin.nextInt()) != 0) {
			long d[] = new long[n], v[] = new long[n];
			for (int i = 0; i < n; ++i) {
				d[i] = stdin.nextLong(); v[i] = stdin.nextLong();
				long gcd = GCD(d[i],v[i]);
				d[i] /= gcd; v[i] /= gcd;
			}
			long D = LCM(d), V = GCD(v);
			for (int i = 0; i < n; ++i) System.out.println(D/d[i]*v[i]/V);
		}
	}
	public static final long GCD(long a, long b){ return b == 0 ? a : GCD(b, a%b); }
	public static final long LCM(long a, long b){ return a / GCD(a, b) * b; }
	public static final long GCD(long[] x){
		long ret = x[0]; for(int i = 1; i < x.length; ++i) ret = GCD(ret, x[i]); return ret;
	}
	public static final long LCM(long[] x){
		long ret = x[0]; for(int i = 1; i < x.length; ++i) ret = LCM(ret, x[i]); return ret;
	}
}

Highway Express Bus(AOJ No. 0212)

割引券の枚数c、バスがつなぐ町の数n、バスの路線数m、各バスの路線情報(接続ノード s_i, d_i,交通費f_i)を入力とし、出発地Sから目的地Dまでの最も安い交通費を求める。割引券を使うと駅間の距離の交通費を半額にすることができる。
制約
1\leq c \leq 10
1 < n \leq 100
1 \leq m \leq 500
1,000 \leq f \leq 10,000 100 刻みの整数
1\leq s_i,d_i,S,D \leq n
S \neq D
Sから Dへの経路は必ず存在する。

アルゴリズム

残りチケット, 町の情報, コストの状態を持たせたDijkstra

コード

import java.util.*;
public class aoj0212 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2;
	public static void main(String[] args) {
		while(true) {
			int c = stdin.nextInt(), n = stdin.nextInt(), m = stdin.nextInt(), s = stdin.nextInt(), d = stdin.nextInt();
			if((c|n|m|s|d) == 0) break;
			--s; --d;
			List<List<Edge>> list = new ArrayList<List<Edge>>(n);
			for(int i = 0; i < n; ++i) list.add(new LinkedList<Edge>());
			for(int i = 0; i < m; ++i) {
				int src = stdin.nextInt()-1, dst = stdin.nextInt()-1, cost = stdin.nextInt();
				list.get(src).add(new Edge(dst, cost, -1));
				list.get(dst).add(new Edge(src, cost, -1));
			}
			System.out.println(solve(list, c, s, d));
		}
	}
	public static int solve(List<List<Edge>> list, int c, int s, int d) {
		int n = list.size();
		int[][] dist = new int[c+1][n]; 
		for(int i = 0; i <= c; ++i) Arrays.fill(dist[i], INF);
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		for(int i = 0; i<=c; ++i) dist[i][s] = 0;
		q.add(new Edge(s, 0, c));
		while(!q.isEmpty()){
			Edge p = q.poll();
			int v = p.dst;
			if(dist[p.ticket][v] < p.cost) continue; //dist[v] < p.weight
			if(v == d) return p.cost;
			int N = (p.ticket > 0 ? 2 : 1);
			for(int k = 0; k < N; ++k){
				for(final Edge u: list.get(v)){ 
					int newTicket = p.ticket - k, newDist = dist[p.ticket][v] + (u.cost>>k);
					if(dist[newTicket][u.dst] > newDist){
						dist[newTicket][u.dst] = newDist;
						q.add(new Edge(u.dst, newDist, newTicket));
					}
				}
			}
		}
		return INF;
	}
	static class Edge implements Comparable<Edge>{
		int dst, cost, ticket;
		Edge(int dst, int cost, int ticket){ this.dst = dst; this.cost = cost; this.ticket = ticket; }
		@Override public int compareTo(Edge o) {
			return cost != o.cost ? cost - o.cost : ticket != o.ticket ? o.ticket - ticket : dst - this.dst;
		}
	}
}