kanetaiの二次記憶装置

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

Expression(AOJ No.0041), A Thief(AOJ No.0042), Puzzle(AOJ No.0043), Prime Number II(AOJ No.0044), Sum and Average(AOJ No.0045), Differential(AOJ No. 0046), Cup Game(AOJ No. 0047), Class(AOJ No. 0048), Blood Groups(AOJ No. 0049), Apple and Peach(AOJ No. 00

Online Judge

リポジトリ

Expression(AOJ No.0041)

4つの整数 I_iが与えられ、
I_1 O_1 I_2 O_2 I_3 O_3 I_4 = 10　 O_j \in \{ +, -, * \}
となる式を1つ答える(ない場合は0を返す)。
ただし、 I_iは入れ替えてもよく、()を好きな位置に挿入してもよい。

アルゴリズム

I_iの順列(4!=24)と、 O_jの重複順列( 3^3 = 27)と括弧の位置(5)を組み合わせて、
最大 24 \times 27 \times 5 = 3240通りを調べる。
括弧の位置は、
(I_1 O_1 I_2) O_2 (I_3 O_3 I_4)
( (I_1 O_1 I_2) O_2 I_3) O_3 I_4
(I_1 O_1 (I_2 O_2 I_3) ) O_3 I_4
I_1 O_1 ( (I_2 O_2 I_3) O_3 I_4)
I_1 O_1 (I_2 O_2 (I_3 O_3 I_4) )
の5通りしかない。

コード

import java.util.*;
public class aoj0041 {
	static final Scanner stdin = new Scanner(System.in);
	static final char[] op = {'+', '-', '*' };
	public static void main(String[] args) {
		Integer[] a = new Integer[4]; 
		while(true){
			for(int i=0; i<4; ++i) a[i] = stdin.nextInt();
			if(a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0 ) break;
			solve(a);
		}
	}
	static int calc(int a, int b, char o ){
		switch(o){
		case '+': return a+b;
		case '-': return a-b;
		case '*': return a*b;
		}
		return 0; //ここには来ない
	}
	static void solve(Integer[] a){
		Arrays.sort(a);
		do{
			for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) for(int k = 0; k < 3; ++k){
				if(calc(calc(a[0], a[1], op[i]), calc(a[2], a[3], op[k]), op[j]) == 10 ){
					System.out.printf("(%d%c%d)%c(%d%c%d)\n", a[0], op[i], a[1], op[j], a[2], op[k], a[3] );
					return;
				}else if(calc(calc(calc(a[0], a[1], op[i]), a[2], op[j]), a[3], op[k]) == 10 ){
					System.out.printf("((%d%c%d)%c%d)%c%d\n", a[0], op[i], a[1], op[j], a[2], op[k], a[3] );
					return;
				}else if(calc(calc(a[0], calc(a[1], a[2], op[j]), op[i]), a[3], op[k]) == 10 ){
					System.out.printf("(%d%c(%d%c%d))%c%d\n", a[0], op[i], a[1], op[j], a[2], op[k], a[3] );
					return;
				}else if(calc(a[0],calc(calc(a[1],a[2],op[j]),a[3], op[k]),op[i]) == 10 ){
					System.out.printf("%d%c((%d%c%d)%c%d)\n", a[0], op[i], a[1], op[j], a[2], op[k], a[3] );
					return;
				}else if(calc(a[0], calc(calc(a[1],a[2], op[j]), a[3], op[k]), op[i]) == 10 ){
					System.out.printf("%d%c(%d%c%(d%c%d))\n", a[0], op[i], a[1], op[j], a[2], op[k], a[3] );
					return;
				}
			}
		}while(nextPermutation(a));
		System.out.println(0);
	}
	public static <T> boolean nextPermutation(T[] a, int fromIndex, int toIndex, final Comparator<? super T> c){
		for (int i = toIndex - 1; i > fromIndex; --i) {
			if (c.compare(a[i-1], a[i]) < 0) { //[i,toIndex) is arranged in descending order.
				int swapIndex = toIndex;
				while (c.compare(a[i-1], a[--swapIndex]) >= 0);
				//int swapIndex = lowerBound(a, i, toIndex, a[i - 1], new Comparator<T>(){ @Override public int compare(T o1, T o2) { return -(c.compare(o1, o2)); }}) - 1;
				swap(a, i-1, swapIndex);
				reverse(a, i, toIndex);
				return true;
			}
		}
		reverse(a, fromIndex, toIndex); //turn back
		return false;
	}
	public static <T extends Comparable <? super T>> boolean nextPermutation(T[] a){
		return nextPermutation(a, 0, a.length, new Comparator<T>(){
			@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
		});
	}
	public static Object[] swap(Object[] a, int i, int j){ Object tmp = a[i]; a[i] = a[j]; a[j] = tmp; return a; }
	public static void reverse(Object[] a, int fromIndex, int toIndex) {
		for(int n = toIndex - fromIndex, mid = n>>1, i = 0, j = n-1; i < mid; ++i, --j)
			swap(a, fromIndex+i, fromIndex+j); 
	}
}

A Thief(AOJ No.0042)]

ナップザックの最大耐久重み W, 商品 i(価値 v_i,重さ w_i)が与えられる01ナップザック問題
出力は、価値総和の最大値とそのときのナップザックの重さ。
ただし、価値の総和が最大になる組み合わせが複数あるときは、重さの総和が小さいものを出力する。
制約
0 \leq i < N \leq 1000
v_i < 10000
0 < w_i < W \leq 1000

アルゴリズム

VDP_{i,j}:= i-1番目までの品物から重さの総和がj以下になるよう選んだ時の総和価値の最大値
i=0, 0\leq j\leq Wについて、VDP_{0,j} = 0
0< i \leq n, 0\leq j \leq Wについて
{ VDP_{i,j} = \begin{cases} VDP_{i-1,j} && (j < w_{i-1}) \\ \max \{ VDP_{i-1,j}, VDP_{i-1,j-w_{i-1} }+v_{i-1} \} && (otherwise) \end{cases} }
これと同時に、 WDP_{i,j}を更新する。
※ WDP_{i,j}:= VDP_{i,j}での重さの総和の最小値
( j\geq w_{i-1}, VDP_{i-1,j}= VDP_{i-1,j-w_{i-1} }+v_{i-1}となった時は、 WDP_{i,j} = \min\{ WDP_{i-1,j}, WDP_{i-1, j-w_{i-1}} +w_{i-1}\}とする)。
別に、 WDPを使わなくても、
VDP_{i,j}を計算した後に、 \min\{j|VDP_{i,j}=VDP_{N,W}\}を求めればよい。

コード

Case n:のところを0からカウントしていてずっとはまってた

import java.util.*;
public class aoj0042 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) { 
		int W;
		for(int i=1; (W = stdin.nextInt()) != 0; ++i){
			int N = stdin.nextInt(); stdin.nextLine();
			int[] v = new int[N], w = new int[N];
			for(int j=0; j<N; ++j){
				String[] s = stdin.nextLine().split(",");
				v[j] = Integer.parseInt(s[0]); w[j] = Integer.parseInt(s[1]);
			}
			System.out.println("Case " + i +":");
			int[] res = solve(W, N, v, w);
			System.out.println(res[0]); System.out.println(res[1]);
		}
	}
	static int[] solve(int W, int N, int[] v, int[] w){
		int[][] VDP = new int[N+1][W+1]; Arrays.fill(VDP[0], 0);
		int[][] WDP = new int[N+1][W+1]; Arrays.fill(WDP[0], 0);
		for(int i=1; i <= N; ++i){
			for(int j=0; j <= W; ++j){
				if(j < w[i-1] || VDP[i-1][j] > VDP[i-1][j-w[i-1]]+v[i-1]){
					VDP[i][j] = VDP[i-1][j];
					WDP[i][j] = WDP[i-1][j];
				}else if(VDP[i-1][j] == VDP[i-1][j-w[i-1]]+v[i-1]){
					VDP[i][j] = VDP[i-1][j];
					WDP[i][j] = Math.min(WDP[i-1][j], WDP[i-1][j-w[i-1]]+w[i-1]);
				}else{
					VDP[i][j] = VDP[i-1][j-w[i-1]]+v[i-1];
					WDP[i][j] = WDP[i-1][j-w[i-1]]+w[i-1];
				}
			}
		}
		return new int[]{ VDP[N][W], WDP[N][W] };
	}
}

Puzzle(AOJ No.0043)

要するに、
麻雀の手牌が与えられて(1〜9の整数×13)
次に何をツモったら(順子 or 刻子)×4 + 雀頭の和了形になるかを求める。
そもそもテンパっていなかったら0を返す。

アルゴリズム

ごり押し
ツモる牌の選び方(9)と雀頭の選び方(9)と順子/刻子の選び方( 2^4 = 16)を組み合わせて、
最大 9 \times 9 \times 16 = 1296通り調べる。

コード

順子/刻子を選ぶとき、ソートされているとやりやすいので、TreeMapで整列済みの頻度表を作成した。

import java.util.*;
public class aoj0043 {
	static final Scanner stdin =  new Scanner(System.in);
	static final ArrayList<String> pat = new ArrayList<String>(); //順子、刻子のパターン
	public static void main(String[] args) { 
		for(int i=0;i<2;++i)for(int j=0;j<2;++j)for(int k=0;k<2;++k)for(int l=0;l<2;++l)
			pat.add(""+i+j+k+l);
		while(stdin.hasNext()){
			TreeFreqTable<Integer> hand = new TreeFreqTable<Integer>();
			String line = stdin.nextLine();
			for(int i=0; i<13; ++i) hand.add(Integer.parseInt(""+line.charAt(i)));
			System.out.println( solve(hand) );
		}
	}
	@SuppressWarnings("serial") public static class TreeFreqTable<K> extends TreeMap<K,Integer>{
		TreeFreqTable(){ super(); }
		TreeFreqTable(TreeFreqTable<K> f){ super((TreeMap<K, Integer>)f); }
		public Integer add(K key) { return put(key, containsKey(key) ? get(key) + 1 : 1); }
	}
	static private boolean remove(TreeFreqTable<Integer> hand, int k){ //頻度減算 減算できなかったらfalse
		if(!hand.containsKey(k)) return false;
		int n = hand.get(k);
		if(n==1) hand.remove(k);
		else hand.put(k, n-1); //n>0
		return true;
	}
	static String solve(TreeFreqTable<Integer> hand){
		StringBuilder res = new StringBuilder();
		for(int i=1; i<10; ++i){ //ツモ　i
			if(hand.containsKey(i) && hand.get(i) >= 4) continue;
			hand.add(i);
			FOUND:
				for(int j: hand.keySet()){ //雀頭 j
					if(hand.get(j)<2) continue;
					for(int k=0; k<pat.size(); ++k){ //順子/刻子のパターン
						if( check(pat.get(k), hand, j)){
							res.append(' '); res.append(i);
							break FOUND;
						}
					}
				}
			remove(hand, i);
		}
		if(res.length()==0) return "0";
		return res.substring(1);
	}
	static boolean check(String p, TreeFreqTable<Integer> hand, int j){
		TreeFreqTable<Integer>  temp = new TreeFreqTable<Integer>(hand);
		remove(temp, j); remove(temp, j);
		for(int k=0; k<p.length(); ++k){
			int key = temp.firstKey();
			switch(p.charAt(k)){
			case '0': //刻子
				if(temp.get(key)<3) return false;
				remove(temp,key);remove(temp, key);remove(temp, key);
				break;
			case '1': //順子
				if(!remove(temp, key) || !remove(temp, key+1) || !remove(temp,key+2)) return false;
				break;
			}
		}
		return true;
	}
}

Prime Number II(AOJ No.0044)

整数 nが与えられて、 nより小さい最大の素数と nより大きい最小の素数を求める
制約
3\leq n \leq 50000

アルゴリズム

エラストテネスの篩で素数列を作っておいて、２分探索する。

コード

※篩で用意しとくフラグは50000+1じゃない(50000より大きい最小の素数+1)
lower_boundした後の条件式はprimeArray[a]==n, primeArray[b]==nじゃなくて、primeArray[a]>=n, primeArray[b]<=nだった... orz

import java.util.*;
public class aoj0044 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N_MAX = 500001;
	static final boolean[] table = sieve(N_MAX);
	public static void main(String[] args) {
		List<Integer> l = new ArrayList<Integer>(N_MAX);
		for(int i = 0; i < N_MAX; ++i) if(table[i]) l.add(i);
		Integer[] primeArray = (Integer[]) l.toArray(new Integer[l.size()]);
		while(stdin.hasNext()){
			int n = stdin.nextInt();
			int a = lowerBound(primeArray, n-1), b = lowerBound(primeArray, n+1);
			System.out.println(
					(primeArray[a] >= n ? primeArray[a-1] : primeArray[a]) + " "
							+ (primeArray[b] <= n ? primeArray[b+1] : primeArray[b])
					);

		}
	}
	public static final boolean[] sieve(int n){
		boolean[] ret = new boolean[n]; 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;
	}
	public static <T> int lowerBound(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c){
		int lb = fromIndex - 1, ub = toIndex;
		while(ub - lb > 1){ 			//rage of solution > 1
			int mid = (lb + ub) / 2, cmp = c.compare(a[mid], key);
			if( cmp >= 0 )	ub = mid;	//(lb,mid]
			else			lb = mid;	//(mid,ub]
		}
		return ub; 						//(lb, ub], ub = lb + 1 → [ub, ub+1)
	}
	public static <T extends Comparable<? super T>> int lowerBound(T[] a, T key){
		return lowerBound(a, 0, a.length, key, new Comparator<T>(){
			@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
		});
	}
}

Sum and Average(AOJ No.0045)

価格と販売個数の系列が与えられて、合計価格と平均販売数を答える。平均販売個数は小数点第1位を四捨五入する。

コード

最近知ったんだけど、Cでscanf("%d,%d",&v,&n);ってやると、','でパースできるんですね

import java.util.*;
public class aoj0045 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) { 
		int sum = 0, num = 0, count = 0;
		while(stdin.hasNext()){
			String[] s = stdin.nextLine().split(",");
			int v = Integer.parseInt(s[0]), n = Integer.parseInt(s[1]);
			num += n; sum += (v*n); count++;
		}
		System.out.println(sum);
		System.out.println( (int)(0.5+(double)num /count) );
	}
}

Differential(AOJ No. 0046)

実数の系列が与えられて、それらの最大値と最小値の差を求める作業ゲー

コード

import java.util.*;
public class aoj0046{
	static final Scanner stdin = new Scanner(System.in); 
	public static void main(String[] args) {
		double max, min;
		max = min = stdin.nextDouble();
		while(stdin.hasNext()){
			double d = stdin.nextDouble();
			if(max < d) max = d;
			if(min > d) min = d;
		}
		System.out.println(max-min);
	}
}

Cup Game(AOJ No. 0047)

ABCの位置にカップがあって、最初はAのカップにボールが入っている。
入れ替え操作の系列が与えられて、最終的にボールはどの位置にあるかを求める。

コード

ただのシミュレーション

import java.util.*;
public class aoj0047 {
	static final Scanner stdin = new Scanner(System.in);
	public static Object[] swap(Object[] a, int i, int j){	
		Object tmp = a[i]; a[i] = a[j]; a[j] = tmp; return a;
	}
	public static void main(String[] args) {
		Integer[] cup = {1, 0, 0};
		while(stdin.hasNext()){
			String line = stdin.nextLine();
			swap(cup, line.charAt(0)-'A', line.charAt(2)-'A');
		}
		for(int i=0; i<3; ++i){
			if(cup[i]==1){
				System.out.println((char)(i+'A'));
				break;
			}
		}
	}
}

Class(AOJ No. 0048)

体重が与えられて、ボクシングの階級を答える作業ゲー

コード

import java.util.*;
public class aoj0048 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext())
			System.out.println(solve(stdin.nextDouble()));
	}
	static String solve(double d){
		return d <= 48.00 ? "light fly" : d <= 51.00 ? "fly" : d <= 54.00 ? "bantam" : 
			d <= 57.00 ? "feather" : d <= 60.00 ? "light" : d <= 64.00 ? "light welter" :
				d <= 69.00 ? "welter" : d <= 75.00 ? "light middle" : d <= 81.00 ? "middle" : 
					d <= 91.00 ? "light heavy" : "heavy";
	}
}

Blood Groups(AOJ No. 0049)

出席番号と血液型の系列が与えられて、それぞれの血液型の人間が何人いるか求める作業ゲー

コード

import java.util.*;
public class aoj0049 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		@SuppressWarnings("serial") HashMap<String, Integer> freq = new HashMap<String, Integer>(){
			{ put("A", 0); put("B", 0); put("AB", 0); put("O", 0); }
		};
		while(stdin.hasNext()){
			String b = stdin.nextLine().split(",")[1];
			freq.put(b, freq.get(b)+1);
		}
		System.out.println(freq.get("A"));
		System.out.println(freq.get("B"));
		System.out.println(freq.get("AB"));
		System.out.println(freq.get("O"));
	}
}

Apple and Peach(AOJ No. 0050)

英文（半角英数字、空白、記号を含む）1000文字以下の英文が与えられて、appleをpeachに、peachをappleに変換した文字列を求める。

コード

StringのreplaceAllって、perlでいうs/$src/$dest/g;みたいにするものだと勘違いしてた。
replaceも呼び出した文字列自身が置換されるんじゃなくて、置換した文字列を生成するんだった...
変なところではまったorz

import java.util.*;
public class aoj0050 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			StringBuilder res = new StringBuilder();
			String[] line = stdin.nextLine().split(" ");
			for(String s: line){
				if(s.indexOf("peach") >= 0) s = s.replace("peach", "apple");
				else if(s.indexOf("apple") >= 0 ) s = s.replace("apple", "peach");
				res.append(' '); res.append(s);
			}
			System.out.println(res.substring(1));
		}
	}
}