kanetaiの二次記憶装置

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

Time to Study(AOJ No. 0238), Calorie Counting(AOJ No. 0239), Interest Rates(AOJ No. 0240), Quaternion Multiplication(AOJ No. 0241), Input Candidates(AOJ No. 0242), Filling Game(SOJ No. 0243), Hot Spring Trip(AOJ No. 0244)

Online judge

リポジトリ

Time to Study(AOJ No. 0238)

要するに n, t, s_i, e_i (1\leq i \leq n)が与えられて、 t-\sum_{i=1}^{n} (s_i - e_i) \leq 0かどうかを答える。

コード

import java.util.*;
public class aoj0238 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int t = stdin.nextInt();
			if (t == 0) break;
			int n = stdin.nextInt();
			while (n-- > 0) t += (stdin.nextInt() - stdin.nextInt());
			System.out.println(t <= 0 ? "OK" : t);
		}
	}
}

Calorie Counting(AOJ No. 0239)

要するにP, Q, R, C, nとn個のレコード(i p q r)が与えられて、 p \leq P, q \leq Q, r \leq R, 4p+9q+4r \leq Cを満たしている場合iを出力する。
満たしている物が一つもない場合はNAと答える。

コード

import java.util.*;
public class aoj0239 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			List<int[]> l = new ArrayList<int[]>();
			while (n-- > 0) {
				int[] a = { stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), 0 };
				a[4] = 4 * a[1] + 9 * a[2] + 4 * a[3];
				l.add(a);
			}
			int b[] = {0, stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), stdin.nextInt()};
			boolean f = true;
			LOOP: for (int[] a : l) {
				for (int i = 1; i < a.length; ++i) if (a[i] > b[i]) continue LOOP;
				System.out.println(a[0]); f = false;
			}
			if (f) System.out.println("NA");
		}
	}
}

Interest Rates(AOJ No. 0240)

要するに年数とnとn個のレコード(銀行番号、金利の種類(単利 or 複利)、年利率(%)）が与えられて、最も元利が高くなる銀行番号を答える。
元利が最大となる銀行は１つしかない。

コード

import java.util.*;
public class aoj0240 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			int y = stdin.nextInt(), ans = -1;
			double max = -1, charge = -1;
			while (n-- > 0) {
				int b = stdin.nextInt(), r = stdin.nextInt(), t = stdin.nextInt();
				charge = t == 1 ? (1 + y * r/100.) : Math.pow(1 + r/100., y);
				if (charge > max) { max = charge; ans = b; }
			}
			System.out.println(ans);
		}
	}
}

Quaternion Multiplication(AOJ No. 0241)

４元数(Quaternion)が２つ与えられて、その積を答える。

コード

x_1 x_2 - y_1 y_2 - z_1 z_2 - w_1 w_2 + (x_1 y_2 + y_1 x_2 + z_1 w_2 - w_1 z_2)i + (x_1 z_2 - y_1 w_2 + z_1 x_2 + w_1 y_2)j + (x_1 w_2 + y_1 z_2 - z_1 y_2 + w_1 x_2)k

import java.util.*;
public class aoj0241 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			while (n-- > 0) {
				int x1 = stdin.nextInt(), y1 = stdin.nextInt(), z1 = stdin.nextInt(), w1 = stdin.nextInt(), x2 = stdin.nextInt(), y2 = stdin.nextInt(), z2 = stdin.nextInt(), w2 = stdin.nextInt();
				System.out.println(String.format("%d %d %d %d", x1*x2 - y1*y2 - z1*z2 - w1*w2, x1*y2 + y1*x2 + z1*w2 - w1*z2, x1*z2 - y1*w2 + z1*x2 + w1*y2, x1*w2 + y1*z2 - z1*y2 + w1*x2));
			}
		}
	}
}

Input Candidates(AOJ No. 0242)

アルファベットの単語列とアルファベットcが与えられて、頭文字がcの単語列のうち最も出現頻度が高い物を答える。該当単語が複数ある場合は、辞書順で答える。

コード

import java.util.*;
public class aoj0242 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			stdin.nextLine();
			Map<String, Integer> freq = new HashMap<String, Integer>();
			while (n-- > 0) for (String s : stdin.nextLine().split(" ")) freq.put(s, (freq.containsKey(s) ? freq.get(s) : 0) + 1);
			char ch = stdin.next().charAt(0);
			List<T> l = new ArrayList<T>();
			for (Map.Entry<String, Integer> e : freq.entrySet()) if (e.getKey().charAt(0) == ch) l.add(new T(e.getKey(), e.getValue()));
			StringBuilder sb = new StringBuilder();
			if (l.isEmpty()) sb.append(" NA");
			else Collections.sort(l);
			for (T t : l) sb.append(" ").append(t.str);
			System.out.println(sb.substring(1));
		}
	}
	static class T implements Comparable<T>{
		String str; int freq;
		T(String s, int f) { str = s; freq = f; }
		@Override public int compareTo(T o) { return freq != o.freq ? o.freq - freq : str.compareTo(o.str); }
	}
}

Filling Game(SOJ No. 0243)

画面にはx列×y行の2次元グリッドが与えられる。

  • グリッドのセルは赤(R)、緑(G)、茶(B)の3色のいずれかで塗られている。
  • セルの色を変更するボタンR、G、Bがあり、このボタンが押下されると一番左上(0,0)のセルがその色に変更される。
  • 一番左上のセルの色が変更されると、そのセルの元の色と同じ色に塗られた隣接するすべてのセルが指定された色に変わる(元の色が同じ色のセルでつながったセルはすべて指定された色に変更される)。

すべてのセルを同一色にするために必要な選択ボタンの操作回数の最小値を出力する。
制約
1 < x,y < 11

アルゴリズム

深さ、計算量の見積もりができなかったので、反復深化深さ優先探索（IDDFS: Iterative Deepening Depth-First Search）で解いた。
分岐係数をb, 深さをdとすると、IDDFSの空間計算量はO(bd), 時間計算量は O(b^d)。
この問題の場合、現在の(0, 0)の色と同じ色のボタンを押しても意味が無いので、他の２色のボタンを押すことになり、b=2となる。
また、色を変える操作がO(xy)なので、時間計算量は 10^2 2^d程度?

コード

java.awt.Point使ってやってたら、Memory Limit Exceededになったので、x, yをint変数一つで表すように変更した。
結局深さはどんくらいなのかな?

import java.util.*;
public class aoj0243 {
	static final Scanner stdin = new Scanner(System.in);
	static int W, H, lim;
	static final char map[][] = new char[20][20];
	static final int dx[] = {-1, 1, 0, 0};
	static final int dy[] = {0, 0, -1, 1};
	public static void main(String[] args) { 
		while (true) {
			W = stdin.nextInt(); H = stdin.nextInt();
			if ((W|H) == 0) break;
			for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) map[i][j] = stdin.next().charAt(0);
			for (lim = 0; !rec(0); ++lim);
			System.out.println(lim);
		}
	}
	static boolean rec(int depth) {
		char precolor = map[0][0];
		if (check()) return true;
		if (depth >= lim) return false;
		for (char color : "RGB".toCharArray()) {
			if (color == precolor) continue;
			List<Integer> list = new ArrayList<Integer>();
			changeColor(0, 0, color, list);
			if (rec(depth + 1)) return true;
			for (int p: list) map[p/W][p%W] = precolor;
		}
		return false;
	}
	static boolean check() {
		char c = map[0][0];
		for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) if (map[i][j] != c) return false;
		return true;
	}
	static void changeColor(int y, int x, char color, List<Integer> list) {
		char precolor = map[y][x];
		map[y][x] = color;
		list.add(y*W+x);
		for (int k = 0; k < 4; ++k) {
			int nx = x + dx[k], ny = y + dy[k];
			if (0 <= nx && nx < W && 0 <= ny && ny < H && map[ny][nx] == precolor) changeColor(ny, nx, color, list);
		}
	}
}

Hot Spring Trip(AOJ No. 0244)

出発地、目的地、及び中継地点の総数nと路線の数m、路線の接続情報、各区間の料金とスタートおよびゴールのバス停が与えられる。
好きな２区間を無料にすることができる。途中で目的地を通過しても、目的地にたどり着いたことにはならない。
出発地から目的地にたどり着くのに必要な最低料金を答える。
制約
出発地から目的地までの経路は必ず存在する。
1 < n < 101
0 < 区間料金 < 1, 001

アルゴリズム

チケットの使用状況と、現在位置を状態として持ったDijkstra。チケット使って途中下車しないように注意するだけ。

コード

import java.util.*;
public class aoj0244 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2, T = 2;
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt(), m = stdin.nextInt();
			if ((n|m) == 0) break;
			List<List<Edge>> adjList = new ArrayList<List<Edge>>();
			for (int i = 0; i < n; ++i) adjList.add(new ArrayList<Edge>());
			for (int i = 0; i < m; ++i) {
				int src = stdin.nextInt()-1, dst = stdin.nextInt()-1, cost = stdin.nextInt();
				adjList.get(src).add(new Edge(dst, cost, 0));
				adjList.get(dst).add(new Edge(src, cost, 0));
			}
			System.out.println(solve(adjList));
		}
	}
	public static int solve(List<List<Edge>> list) {
		int n = list.size();
		int[][] dist = new int[T+1][n]; 
		for(int i = 0; i <= T; ++i) Arrays.fill(dist[i], INF);
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		dist[T][0] = 0;
		q.add(new Edge(0, 0, T));
		while(!q.isEmpty()){
			Edge p = q.poll();
			int v = p.dst;
			if(dist[p.ticket][v] < p.cost) continue;
			if(v == n-1 && p.ticket != 1) return p.cost;
			if (1 <= p.ticket) for(final Edge u: list.get(v)) { 
				int newTicket = p.ticket - 1, newDist = dist[p.ticket][v];
				if(dist[newTicket][u.dst] > newDist){
					dist[newTicket][u.dst] = newDist;
					q.add(new Edge(u.dst, newDist, newTicket));
				}
			}
			if (p.ticket != 1) for(final Edge u: list.get(v)) { 
				int newTicket = p.ticket, newDist = dist[p.ticket][v] + u.cost;
				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;
		}
	}
}