Rank Checker(AOJ No.0061), What is the Bottommost?(AOJ No.0062), Palindrome(AOJ No.0063), Secret Number(AOJ No.0064), Trading(AOJ No.0065), Tic Tac Toe(AOJ No.0066), The Number of Island(AOJ No.0067), Enclose Pins with a Rubber Band(AOJ No.0068), Drawing

アルゴリズム

整理番号→得点のマッピングを入力し、得点→順位のマッピングを作って答える。
得点→順位のマッピングは、得点を高い順にソートして作る。

コード

Collections.reverseOrder()をTreeMapのコンストラクタに渡すと降順にソートされる。
問題文に、同一順位の扱いが書かれていない(sample inputで予想できますが)。
パソコン甲子園の問題って、全体的に問題定義が曖昧なものが多い希ガス。
ちなみに、同一順位の次の順位が連番になるようにすればおｋ。

import java.util.*;
public class aoj0061 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args){
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		TreeMap<Integer, Integer>rmap = new TreeMap<Integer, Integer>(Collections.reverseOrder());
		while(true){
			String[] record = stdin.nextLine().split(",");
			if(record[0].equals("0") && record[1].equals("0")) break;
			int num = Integer.parseInt(record[1]);
			map.put(record[0], num);
			rmap.put(num, 1);
		}
		Iterator<Integer> itr = rmap.keySet().iterator();
		int rank = 1;
		while(itr.hasNext()) rmap.put(itr.next(), rank++);
		while(stdin.hasNext())
			System.out.println( rmap.get( map.get(stdin.nextLine()) ) );
	}
}

What is the Bottommost?(AOJ No.0062)

$\begin{array}{cccccc}x_{1,1} & x_{1,2} & x_{1,3} & \cdots & x_{1,n-1} & x_{1,n} \\ & x_{2,2} & x_{2,3} & \cdots & x_{2,n-1} & x_{2,n} \\ & & & \vdots & & \\ & & & & x_{n-1,n-1}& x_{n-1,n}\\ & & & & & x_{n,n} \end{array}$
規則：

A	B
	C

C:= A+Bの１の位
$\{ x_{1,i} | 1\leq i \leq n \}$ が与えられたときの、 $x_{n,n}$ を答える。

コード

左に詰めてやってます。

import java.util.*;
public class aoj0062 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			char[] a = stdin.nextLine().toCharArray();
			for(int i =  1; i < a.length; ++i)
				for(int j = 0; j <= a.length - i - 1; ++j)
					a[j] = (char)((a[j]-'0'+a[j+1]-'0')%10 + '0');
			System.out.println(a[0]);
		}
	}
}

Palindrome(AOJ No.0062)

palindrome

文字列の系列が与えられて、回文になっている文字列の数を答える。

コード

import java.util.*;
public class aoj0063 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int ans = 0;
		while(stdin.hasNext()){
			char[] str = stdin.nextLine().toCharArray();
			boolean flag = true;
			for(int i = 0; i < str.length/2; ++i)
				if(str[i] != str[str.length-i-1]) flag = false;
			if(flag) ans++;
		}
		System.out.println(ans);
	}
}

Secret Number(AOJ No.0064)

英文章が与えられ、その中に現れる数字の総和を求める。
数字が連続している場合は、1つの１０進数としてカウントする。

コード

前の数字を10倍して足していく。文の最後が数字の足し忘れが無いように注意する。

import java.util.*;
public class aoj0064 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int ans = 0;
		while(stdin.hasNext()){
			char[] line = stdin.nextLine().toCharArray();
			int temp = 0;
			for(char ch: line){
				if(Character.isDigit(ch)){
					temp = 10*temp + ch-'0';
				}else{
					ans += temp;
					temp = 0;
				}
			}
			ans += temp;
		}
		System.out.println(ans);
	}
}

Trading(AOJ No.0065)

取引先の顧客番号（正の整数）と取引日を月ごとに記録したデータがある。
今月のデータと先月のデータが与えられ、先月から２ヶ月連続で取引のある会社の顧客番号と取引のあった回数を求める。
制約
顧客番号 $\leq 1000$
月々の取引先は1000以内

コード

顧客番号の昇順で出力するので、TreeMapでやればおｋ

import java.util.*;
public class aoj0065 {
	static final Scanner stdin = new Scanner(System.in);
	@SuppressWarnings("serial") public static class TreeFreqTable<K> extends TreeMap<K,Integer>{
		TreeFreqTable(){ super(); }
		public Integer add(K key) { return put(key, containsKey(key) ? get(key) + 1 : 1); }
	}
	public static void main(String[] args) {
		boolean[] flag = new boolean[1001];
		Arrays.fill(flag, false);
		TreeFreqTable<Integer> map = new TreeFreqTable<Integer>();
		while(true){
			String record = stdin.nextLine();
			if(record.isEmpty()) break;
			String[] temp = record.split(",");
			int id = Integer.parseInt(temp[0]);
			map.add(id);
		}
		while(stdin.hasNext()){
			String[] temp = stdin.nextLine().split(",");
			int id = Integer.parseInt(temp[0]);
			if(map.containsKey(id)){
				flag[id] = true;
				map.add(id);
			}
		}
		Iterator<Integer> itr = map.keySet().iterator();
		while(itr.hasNext()){
			int id = itr.next();
			if(flag[id]) System.out.println(id+" "+map.get(id));
		}
	}
}

Tic Tac Toe(AOJ No.0066)

oxの盤面が与えられて、どちらか勝ちか判定する。ルール上不可能な入力はない。
o→○, x→×, s→空白, d→引き分け

コード

縦、横、斜めのパターン作っといた。

import java.util.*;
public class aoj0066 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int[][] pat = { {0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, 
				{1,4,7}, {2,5,8}, {0,4,8}, {2,4,6} };
		while(stdin.hasNext()){
			char[] l = stdin.nextLine().toCharArray();
			char out = 'd';
			for(int i = 0; i<pat.length; ++i){
				if(l[pat[i][0]] != 's' && l[pat[i][0]] == l[pat[i][1]]&& l[pat[i][1]] == l[pat[i][2]]){
					out = l[pat[i][0]];
					break;
				}
			}
			System.out.println(out);
		}
	}
}

The Number of Island(AOJ No.0067)

0海、1島、12×12, 4近傍、島数え

コード

12×12なのでDFSでもおｋ

import java.util.*;
public class aoj0067 {
	static final Scanner stdin = new Scanner(System.in);
	static final boolean[][] map = new boolean[14][14];
	public static void main(String[] args) { 
		while(stdin.hasNext()){
			Arrays.fill(map[0], false);
			for(int i = 1; i <= 12; ++i){
				Arrays.fill(map[i], false);
				char[] temp = stdin.next().toCharArray();
				for(int j=0; j<12; ++j)
					if(temp[j]=='1') map[i][j+1] = true;
			}
			Arrays.fill(map[13], false);
			System.out.println(solve());
		}
	}
	static int solve(){
		int res = 0;
		for(int i = 1; i <= 12; ++i)
			for(int j = 1; j <= 12; ++j)
				if(map[i][j]){ res++; DFS(i,j); }
		return res;
	}
	static void DFS(int i, int j){
		map[i][j] = false;
		if(map[i-1][j]) DFS(i-1,j);
		if(map[i][j+1]) DFS(i,j+1);
		if(map[i+1][j]) DFS(i+1,j);
		if(map[i][j-1]) DFS(i-1,j-1);
	}
}

Enclose Pins with a Rubber Band(AOJ No.0068)

要するに、頂点集合 $V$ の中で、凸包の頂点に含まれない頂点の数を求める。
凸包を形成する辺上に3点以上の頂点は存在しないと仮定してよい。
制約
$-1000.0\leq x,y \leq 1000.0$
$3\leq |V| \leq 100$

コード

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0068 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt();
			if(n==0) break;
			Point[] V = new Point[n];
			for(int i = 0; i < n; ++i){
				String[] coord = stdin.next().split(",");
				V[i] = new Point(Double.parseDouble(coord[0]), Double.parseDouble(coord[1]));
			}
			System.out.println(n-convexHull(V).length);
		}
	}
	public static final double EPS = 1e-10;
	public static boolean less(double a, double b){ return a - b < -EPS; }			// a < b
	public static boolean greater(double a, double b){ return less(b,a); }			// a > b
	@SuppressWarnings("serial") public static class Point extends Point2D.Double implements Comparable<Point>{
		public Point(double x, double y){ super(x,y); }
		public final double normsq(){ return x*x + y*y; }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		public final int compareTo(Point o){
			return (this.x != o.x) ? java.lang.Double.compare(this.x, o.x) : java.lang.Double.compare(this.y, o.y);
		}
		public final double cross(Point p){ return x * p.y - y * p.x; }
		public final double dot(Point p){ return x * p.x + y * p.y; }
		public final int ccw(Point b, Point c) {
			Point ab = b.sub(this);
			Point ac = c.sub(this);
			if (greater(ab.cross(ac), 0))		return +1;	// counter clockwise
			if (less(ab.cross(ac), 0))			return -1;	// clockwise
			if (less(ab.dot(ac), 0))			return +2;	// (c--a--b or b--a--c) on line
			if (less(ab.normsq(), ac.normsq()))	return -2;	// (a--b--c or c--b--a) on line (b≠c, includes a=b)
			return 0;									// (a--c--b or b--c--a) on line (includes c=b, a=c, a=b=c)
		}
	} //class Point
	public static final Point[] convexHull(Point[] V) {
		int n = V.length;
		if(n < 3) return null;
		Arrays.sort(V); //sorts based on x coordinate in ascending order
		int k = 0; //index of C
		Point[] C = new Point[2*n];
		/* lower-hull */
		for(int i = 0; i < n; C[k++] = V[i++])
			while(k >= 2 && C[k-2].ccw(C[k-1], V[i]) <= 0) --k;
		/* upper-hull */
		// t=|lower-hull|+1
		for(int i = n-2, t = k + 1; i >= 0; C[k++] = V[i--])
			while(k >= t && C[k-2].ccw(C[k-1], V[i]) <= 0) --k;
		return Arrays.copyOf(C, k-1); //C[k-1] is start point of lower-hull.
	}
}

Drawing Lots II(AOJ No.0069)

縦糸 $n$ 本(左から番号1,2,...)、 $d$ 段、当たり１つ、斜め線なし、横糸は隣り合う縦糸にしかつながらないあみだくじがある。開始番号 $m$ が与えられたとき、ゴールにたどり着けるかどうか、また、１本横線を足してゴールできる場合は、何段目の左から何番目の位置から右に横線を足せばよいかを答える。
制約
$1 < n < 10$
$1\leq m \leq n$
$1\leq d \leq 30$

アルゴリズム

横糸が連続しないように気を付けて、すべての位置に対して、横糸がつけれるならつけて探索してみる。
探索に $O(d)$ 、横糸の挿入位置を決めるのに $O(nd)$ なので、 $O(nd^2 )$

コード

index管理が少しややこしい。入力の左右に、番兵を配置した。

import java.util.*;
import java.util.*;
public class aoj0069 {
	static final Scanner stdin = new Scanner(System.in);
	static final boolean[][] map = new boolean[30][12];
	public static void main(String[] args) { 
		while(true){
			int n = stdin.nextInt();
			if(n==0) break;
			int m = stdin.nextInt();
			int goal = stdin.nextInt();
			int d = stdin.nextInt();
			for(int i = 0; i < d; ++i){
				Arrays.fill(map[i], false);
				char[] line = stdin.next().toCharArray();
				for(int j = 0; j < n-1; ++j)
					map[i][j+1] = (line[j]=='1');
			}
			System.out.println(solve(n, m, goal, d));
		}
	}
	static String solve(int n, int m, int goal, int d){
		if(search(n,m,goal,d)) return "0";
		for(int i = 0; i < d; ++i){
			for(int j = 1; j < n; ++j){
				if(!map[i][j] && !map[i][j-1] && !map[i][j+1]){
					map[i][j] = true;
					if(search(n,m,goal,d)) return (i+1)+" "+j;
					map[i][j] = false;
				}
			}
		}
		return "1";
	}
	static boolean search(int n, int m, int goal, int d){
		for(int i = 0; i < d; ++i){
			if(map[i][m]) m++;
			else if(map[i][m-1]) m--;
		}
		return m == goal;
	}
}

Combination of Number Sequences(AOJ No.0070)

$s, n$ が与えられて、次式を満たす $k_i$ の組み合わせの数を求める。
ただし、 $k_i$ は互いに異なる数字をとる。
$s = \sum_{i=1}^n ik_i$
$k_i \in \{0, 1, 2, \cdots , 9 \}$

アルゴリズム

全探索でも10!=3,628,800なので、あらかじめ
$0 < n \leq 10, 0\leq s \leq 330=\sum_{i=1}^{10} i(i-1)$
について組み合わせ数を計算しとけばおｋ。順列は深さが10なので、再帰DFSで簡単に生成できる。

コード

問題文に、入力の範囲が明記されてないから、本当は $0 < n \leq 10$ とか $0\leq s$ の条件とか必要だけど、通っちゃったよ。

import java.util.*;
public class aoj0070 {
	static final Scanner stdin = new Scanner(System.in);
	static final boolean[] flag = new boolean[10];
	static final int[][] table = new int[11][331];
	public static void main(String[] args) { 
		for(int i = 0; i < 11; ++i) Arrays.fill(table[i], 0);
		DFS(10, 0, 0);
		while(stdin.hasNext()){
			int n = stdin.nextInt(), s = stdin.nextInt();
			System.out.println(s<331 ? table[n][s] : 0);
		}
	}
	static void DFS(int max, int depth, int sum){
		table[depth][sum]++;
		if(depth == max) return;
		for(int i = 0; i < 10; ++i){
			if(!flag[i]){
				flag[i] = true;
				DFS(max, depth+1, sum+i*(depth+1));
				flag[i] = false;
			}
		}
	}
}

kanetaiの二次記憶装置

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

Rank Checker(AOJ No.0061), What is the Bottommost?(AOJ No.0062), Palindrome(AOJ No.0063), Secret Number(AOJ No.0064), Trading(AOJ No.0065), Tic Tac Toe(AOJ No.0066), The Number of Island(AOJ No.0067), Enclose Pins with a Rubber Band(AOJ No.0068), Drawing

Rank Checker(AOJ No.0061)

アルゴリズム

コード

What is the Bottommost?(AOJ No.0062)

コード

Palindrome(AOJ No.0062)

コード

Secret Number(AOJ No.0064)

コード

Trading(AOJ No.0065)

コード

Tic Tac Toe(AOJ No.0066)

コード

The Number of Island(AOJ No.0067)

コード

Enclose Pins with a Rubber Band(AOJ No.0068)

コード

Drawing Lots II(AOJ No.0069)

アルゴリズム

コード

Combination of Number Sequences(AOJ No.0070)

アルゴリズム

コード