Sale Result(AOJ No.0100), Aizu PR(AOJ No.0101), Matrix-like Computation(AOJ No.0102), Baseball Simulation(AOJ No.0103), Magical Tiles(AOJ No.0104), Book Index(AOJ No.0105), Discounts of Buckwheat(AOJ No.0106), Carry a Cheese(AOJ No.0107), Operation of Fre

Sale Result(AOJ No.0100)

i(社員id),p(販売商品価格),q(販売数)のレコードがn個与えられたとき、
合計売り上げが1000000以上の社員idを答える。
一人も売り上げが1000000以上の人がいなかったらNAと答える。
制約
$p \leq 1,000,000$
$q \leq 100,000$
$n \leq 4000$

コード

なんかこの問題正解率がかなり低い。
原因の一つは、値がやたら大きいからだと思う。
最大の原因は、問題の日本語がひどい(英語の問題文と意味が異なるところがある。)

import java.util.*;
public class aoj0100 {
	static final Scanner stdin = new Scanner(System.in);
	static final long MAX = 1000000;
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt(); stdin.nextLine();
			if(n==0) break;
			ArrayList<String> order = new ArrayList<String>(n);
			HashMap<String, Long> table = new HashMap<String, Long>(n);
			for(int i = 0; i < n; ++i){
				String[] line = stdin.nextLine().split(" ");
				long v = Long.parseLong(line[1]) * Long.parseLong(line[2]);
				if(!table.containsKey(line[0])){
					order.add(line[0]);
					if(v > MAX) v = MAX;
				}else{
					v += table.get(line[0]);
					if(v > MAX) v = MAX;
				}
				table.put(line[0], v);
			}
			boolean flag = false;
			for(String id: order){
				long v = table.get(id);
				if(v == MAX){
					System.out.println(id);
					flag = true;
				}
			}
			if(!flag) System.out.println("NA");
		}
	}

}

Aizu PR(AOJ No.0101)

n個の英文が与えられて、"Hoshino"を"Hoshina"に置換した英文を出力する。
制約
1文は1000文字以下

コード

import java.util.*;
public class aoj0101 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n = stdin.nextInt(); stdin.nextLine();
		while(n-- > 0){
			String line = stdin.nextLine();
			while(line.indexOf("Hoshino") >= 0)
				line = line.replace("Hoshino", "Hoshina");
			System.out.println(line);
		}
	}
}

Matrix-like Computation(AOJ No.0102)

$n\times n$ の行列が与えられて、各行、各列の和を追加した $n+1\times n+1$ 行列を求める

コード

import java.util.*;
public class aoj0102 {
	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[] a = new int[n];
			int sum;
			Arrays.fill(a, 0);
			for(int i = 0; i < n; ++i){
				sum = 0;
				for(int j = 0; j < n; ++j){
					int m = stdin.nextInt();
					System.out.printf("%5d", m);
					a[j] += m;
					sum += m;
				}
				System.out.printf("%5d\n", sum);
			}
			sum = 0;
			for(int i: a){
				System.out.printf("%5d", i);
				sum += i;
			}
			System.out.printf("%5d\n", sum);
		}
	}
}

Baseball Simulation(AOJ No.0103)

HOMERUN, OUT, HITの系列が与えられて、1イニングごとに獲得された点数を出力する。

コード

ビットシフトでやった

import java.util.*;
public class aoj0103 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int count = 0, cond = 0, point = 0;
		int p = 1<<3;
		stdin.nextInt(); stdin.nextLine();
		while(stdin.hasNext()){
			String l = stdin.nextLine();
			if(l.equals("OUT")){
				if(++count == 3){
					System.out.println(point);
					cond = point = count = 0;
				}
			}else if(l.equals("HIT")){
				cond <<= 1;
				if((cond & p) == p) point++;
				cond |= 1;
			}else{
				for(int i = 0; i < 3; ++i){
					cond <<= 1;
					if((cond & p) == p) point++;
				}
				point++;
			}
		}
	}
}

Magical Tiles(AOJ No.0104)

ドラクエとかにある乗ると矢印の方向に移動するタイルを含むマップが与えられて、
座標0,0に乗った時、到達する座標を答える。ループするときはLOOPと答える。

コード

import java.util.*;
public class aoj0104 {
	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 == 0 && m ==0) break;
			char[][] map = new char[n][];
			for(int i = 0; i < n; ++i) map[i] = stdin.next().toCharArray();
			int i = 0, j = 0;
			END: while(true){
				switch(map[i][j]){
				case '<': map[i][j--] = ' '; break;
				case '>': map[i][j++] = ' '; break;
				case '^': map[i--][j] = ' '; break;
				case 'v': map[i++][j] = ' '; break;
				case ' ': System.out.println("LOOP"); break END;
				case '.': System.out.println(j+" "+i); break END;
				}
			}
		}
	}
}

コード

import java.util.*;
public class aoj0105 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		TreeMap<String, TreeSet<Integer>> m = new TreeMap<String, TreeSet<Integer>>();
		while(stdin.hasNext()){
			String w = stdin.next();
			int n = stdin.nextInt();
			if(m.containsKey(w)) m.get(w).add(n);
			else{
				TreeSet<Integer> s = new TreeSet<Integer>();
				s.add(n);
				m.put(w, s);
			}
		}
		for(String w: m.keySet()){
			System.out.println(w);
			StringBuilder o = new StringBuilder();
			for(int i: m.get(w)) o.append(' ').append(i);
			System.out.println(o.substring(1));
		}
	}
}

Discounts of Buckwheat(AOJNo.0106)

	A店	B店	C店
1袋あたりの量	200g	300g	500g
1袋の単価(定価)	380円	550円	850円
割引が適用される単位	5袋毎	4袋毎	3袋毎
割引率	20%引き	15%引き	12%引き

A, B, C店で $n$ ｇのそば粉を買うときにかかる最小のお金を求める
制約
$500\leq n\leq 5000$
$n$ は10の倍数

$DP_i :=$ そば粉 $i$ gを買うのに必要な最小のお金
とすると、
$DP_i = \begin{array}{cc} \infty & (i < 0)\end{array}$
$DP_0 = 0$
$DP_i = \min \left\{ \begin{array}{l} DP_{i-200} + 380 \\ DP_{i-300} + 550\\ DP_{i-500} + 850\\ DP_{i-1000} + 380\times 5 \times 0.8\\ DP_{i-1200} + 550\times 4\times 0.85\\ DP_{i-1500} + 850\times 3\times 0.88 \end{array} \right.$
というDPで定式化できる( $O(n)$ )。
$n$ の制約があるので、添え字は1/100にして考えればよい。

コード

実はこの問題 $DP_n$ を出力するようにしているが、
本当はもっと値が小さくなる可能性がある。
セットで買って、買ったそば粉の量 $> n$ gとなる時、割引で $DP_n$ より安くなる場合がある。
問題からは読み取れないが、そば粉は $n$ ｇピッタリになるようにするということらしく、 $DP_n$ を出力しなければならない。

import java.util.*;
public class aoj0106 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
                int[] DP = new int[51];
		while(true){
			int n = stdin.nextInt()/100;
			if(n == 0)break;
			Arrays.fill(DP, Integer.MAX_VALUE/2);
			DP[0] = 0;
			for(int i = 2; i <= n; ++i){
				int m = Integer.MAX_VALUE/2;
				if(i-2 >= 0) m = Math.min(m, DP[i-2] + 380);
				if(i-3 >= 0) m = Math.min(m, DP[i-3] + 550);
				if(i-5 >= 0) m = Math.min(m, DP[i-5] + 850);
				if(i-10 >= 0) m = Math.min(m, DP[i-10] + 1520);
				if(i-12 >= 0) m = Math.min(m, DP[i-12] + 1870);
				if(i-15 >= 0) m = Math.min(m, DP[i-15] + 2244);
				DP[i] = m;
			}
			System.out.println(DP[n]);
		}
	}
}

Carry a Cheese(AOJ No.0107)

parallelepiped

$A\times B\times C$ の直方体が、半径 $R$ の球の中に入れることができるかを調べる。

コード

parallelepipedをアルクで調べてみると平行6面体となっていたんだが、
単にparallelepipedと書いていたら、直方体のことを指すのが普通なの？英語よくわからん。
まあ、斜平行6面体だったら、角度が分らんと計算のしようがないんだがね。

import java.util.*;
public class aoj0107 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int a[]={stdin.nextInt(), stdin.nextInt(), stdin.nextInt()};
			if(a[0] == 0 && a[1] == 0 && a[2] == 0) break;
			Arrays.sort(a);
			int n = stdin.nextInt();
			while(n-- > 0)
				System.out.println( 2*stdin.nextInt() > Math.hypot(a[0], a[1]) ? "OK" : "NA" );
		}
	}
}

Operation of Frequency of Appearance(AOJ No.0108)

$S=\{ s_1, s_2, \cdots , s_n \}$ に対する出現頻度操作を行うと、同じ長さの数列 $C$ ( $c_i = s_i$ の頻度)となる。これを繰り返していくと、出現頻度操作の前後で数列が変化しなくなる。
その時の数列と、変換回数を求める。

コード

import java.util.*;
public class aoj0108 {
	static final Scanner stdin = new Scanner(System.in);
	static void add(HashMap<Integer, Integer> h, int x){ h.put(x, h.containsKey(x) ? h.get(x)+1 : 1); }
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) > 0){
			int[][] l = new int[2][n];
			HashMap<Integer, Integer> h = new HashMap<Integer, Integer>(n);
			for(int i = 0; i < n; ++i){
				l[0][i] = stdin.nextInt();
				add(h, l[0][i]);
			}
			int count = 0;
			int cur = 1, pre = 0;
			while(true){
				for(int i = 0; i < n; ++i) l[cur][i] = h.get(l[pre][i]);
				h.clear();
				boolean flag = true;
				for(int i = 0; i < n; ++i){
					add(h,l[cur][i]);
					if(l[cur][i] != l[pre][i]) flag = false;
				}
				if(flag) break;
				cur = (cur + 1) % 2;
				pre = (pre + 1) % 2;
				count++;
			}
			System.out.println(count);
			for(int i = 0; i < n-1; ++i) System.out.print(l[cur][i] + " ");
			System.out.println(l[cur][n-1]);
		}
	}
}

Smart Calculator(AOJ No.0109)

与えられた数式を構文解析して、int型で計算したら勝ち。0除算はない。

コード

構文解析(Syntactic Analysis)を使う。
'＝'は必ず最後に来るので無視。

import java.util.*;
public class aoj0109 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) { 
		int n = stdin.nextInt();
		while(n-->0)
			System.out.println(equation(stdin.next().toCharArray(), 0).value);
	}
	public static class Result{
		int value, pos;
		Result(int value, int pos){this.value = value; this.pos = pos;}
	}
	public static Result equation(char[] str, int pos){
		Result left = factor(str, pos);
		while(str[left.pos] == '+' || str[left.pos] == '-'){
			Result right = factor(str, left.pos+1);
			if(str[left.pos] == '+') left.value += right.value;
			else left.value -= right.value;
			left.pos = right.pos;
		}
		return left;
	}
	private static Result factor(char[] str, int pos){
		Result left = term(str, pos);
		while(str[left.pos] == '*' || str[left.pos] == '/'){
			Result right = term(str, left.pos+1);
			if(str[left.pos] == '*') left.value *= right.value;
			else left.value /= right.value;
			left.pos = right.pos;
		}
		return left;
	}
	private static Result term(char[] str, int pos){
		if(str[pos] == '('){
			Result res = equation(str, pos+1);
			assert str[res.pos] == ')';
			res.pos += 1; //skip ')'
			return res;
		}else{
			int value = 0;
			while(Character.isDigit(str[pos]))
				value = value * 10 + (str[pos++] - '0');
			return new Result(value, pos);
		}
	}
}

Alphametic(AOJ No.0110)

a+b=cが与えられて、a, b, cが虫食いになっている。虫食いになっているところは全部Xで共通の数字'0'〜'9'が入る。一番上の桁を'0'できない。
Xを求める。ない場合はNAと答える。Xは一意に決まる。

コード

多倍長演算しないとダメ。
眠い。へぼいコードになってるけど気にしたら負け。パトラッシュ、僕はもう疲れたよ...

import java.util.*;
import java.math.*;;
public class aoj0110 {
	static final Scanner stdin = new Scanner(System.in);
	static final boolean headIsX(String str){ return str.charAt(0) == 'X' && str.length() > 1;}
	public static void main(String[] args) {
		while(stdin.hasNext()){
			String[] l = stdin.next().split("\\+|=");
			boolean flag = false;
			boolean zero = false;
			if(headIsX(l[0]) || headIsX(l[1]) || headIsX(l[2])) zero = true;
			for(int i = 0; i < 10; ++i){
				if(i==0 && zero) continue;
				StringBuilder temp = new StringBuilder(l[0]);
				int idx;
				while((idx = temp.indexOf("X")) >= 0) temp.setCharAt(idx, (char)('0'+i));
				BigInteger left = new BigInteger(temp.toString());
				temp = new StringBuilder(l[1]);
				while((idx = temp.indexOf("X")) >= 0) temp.setCharAt(idx, (char)('0'+i));
				left = left.add(new BigInteger(temp.toString()));
				temp = new StringBuilder(l[2]);
				while((idx = temp.indexOf("X")) >= 0) temp.setCharAt(idx, (char)('0'+i));
				if(left.equals(new BigInteger(temp.toString()))){
					System.out.println(i);
					flag = true;
					break;
				}
			}
			if(!flag) System.out.println("NA");
		}
	}
}

kanetaiの二次記憶装置

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