Mode Value(AOJ No.0028), English Sentence(AOJ No.0029), Sum of Integers(AOJ No.0030), Weight(AOJ No.0031), Plastic Board(AOJ No.0032), Ball(AOJ No.0033), Railway Lines(AOJ No.0034)

リポジトリ

Mode Value(AOJ No.0028)

1〜100の整数がn個与えられて、その最頻値(mode)を答える。
最頻値が複数ある場合は、昇順で出力する。
制約
n≦100

コード

C++みたいにt[key]++みたいにできんのか?
整数が1〜100なんで、普通の配列で頻度表を作ってもいい。
この場合、どうやって求めるのが一番早いんかな?

import java.util.*;
public class aoj0028 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		TreeMap<Integer, Integer> t = new TreeMap<Integer, Integer>();
		int max = 0;
		while(stdin.hasNext()){
			int k = stdin.nextInt();
			t.put(k, t.containsKey(k) ? t.get(k)+1 : 1);
			max = Math.max(max, t.get(k));
		}
		for(Integer k: t.keySet()) if( t.get(k) == max ) System.out.println(k);
	}
}

English Sentence(AOJ No.0029)

英文が与えられて、最頻のワードと最長のワードを出力する。
ただし、最頻のワードと最長のワードは一意に定まる入力であることが保証されている。
制約
文章の文字数は 1000 文字以下。
一つの単語の文字数は 32 文字以下。

コード

HashMapに入れてった。
英文の頭の大文字を小文字化したりしてないけど、アクセプトされるみたい。

import java.util.*;
public class aoj0029 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		HashMap<String,Integer> t = new HashMap<String,Integer>();
		int max_len = 0, max_freq=0;
		String longstr="", mode="";
		while(stdin.hasNext()){
			String k = stdin.next();
			t.put(k, t.containsKey(k) ? t.get(k) + 1 : 1);
			if(max_len < k.length()){ max_len = k.length(); longstr = k; }
			if(max_freq < t.get(k)){ max_freq = t.get(k); mode = k; }
		}
		System.out.println(mode+" "+longstr);
	}
}

Sum of Integers(AOJ No.0030)

0〜9の整数の中から、異なるn個の整数を選び、その和がsになるようにする。
その時の整数の選び方は何通りか?

アルゴリズム

深さ優先で調べていき、和がsを超えたらバックトラック。

コード

和がsを超えたらバックトラック -> (s-現在までの和)<0になったらバックトラック

import java.util.*;
public class aoj0030 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt(), s = stdin.nextInt();
			if(n==0 && s==0) break;
			System.out.println( solve(n,s,0) );
		}
	}
	static int solve(int n, int s, int c){
		if(n == 0) return (s==0 ? 1 : 0);
		int d = Math.min(10, s+1);
		int res = 0;
		for(int i = c; i < d; ++i) res += solve(n-1, s-i, i+1);
		return res;
	}
}

Weight(AOJ No.0031)

• weight
• scale
• scalepan
• tip
• weigh
• adjacent

整数nが与えられて、gの重りで天秤が釣り合うようにするとき、
使用する重りの重さを昇順に答える。
制約

コード

import java.util.*;
public class aoj0031 {
	static final Scanner stdin = new Scanner(System.in);
	final static int[] b = {1,2,4,8,16,32,64,128,256,512};
	public static void main(String[] args) {
		while(stdin.hasNext() ){
			ArrayList<Integer> a = new ArrayList<Integer>();
			solve( a, stdin.nextInt() );
			for(int i=0; i<a.size(); ++i) System.out.print( a.get(i)+(a.size()-1 == i ? "\n" : " ") );
		}
	}
	static void solve(ArrayList<Integer> a, int n){
		for(int i=0; i<10; ++i){
			if( (n & 1) == 1) a.add(b[i]);
			n >>= 1;
		}
	}
}

Plastic Board(AOJ No.0032)

• mold
• parallelogram
• rectangle
• lozenge

いくつかの平行四辺形の隣り合う2辺と対角線の長さが与えられて、
そのうち、長方形のものの数と、ひし形のものの数を答える。

アルゴリズム

長方形
ひし形

コード

平行四辺形にならないような入力()は無いみたい。
まあ、平行四辺形の隣り合う2辺と対角線の長さが与えられるといっているんだから、そりゃそうか。

import java.util.*;
public class aoj0032 {
	static final Scanner stdin = new Scanner(System.in);;
	public static void main(String[] args) {
		int rect_count = 0, lozenge_count = 0;
		while(stdin.hasNext()){
			String e[] = stdin.nextLine().split(",");
			int e1 = Integer.parseInt(e[0]), e2 = Integer.parseInt(e[1]), ed = Integer.parseInt(e[2]);
			if( is_rect(e1,e2,ed) ) rect_count++;
			if( is_lozenge(e1,e2,ed) ) lozenge_count++;
		}
		System.out.println(rect_count+"\n"+lozenge_count);
	}
	static boolean is_rect(int e1, int e2, int ed){ return e1*e1+e2*e2 == ed*ed; }
	static boolean is_lozenge(int e1, int e2, int ed){ return e1==e2; }
}

Ball(AOJ No.0033)

1〜10の番号が振られたボールがあって、ボールの並びが与えられる。
その並び順に、左か右の容器に入れる。
このとき、それぞれの容器で、最後に入れたボールの数字より大きい数字のボールしか入れることができない。
10個のボールをすべて容器の中に入れられるかどうかを答える。

アルゴリズム

ボールの数が少ないので幅優先でもいいが、グリーディに解ける。
例えば、左側に入る場合は左に入れて、
左に入らない場合、右に入るなら右に入れる。

コード

C++11では、BOOST_FOREACHを使わずに、こういう省略形forループが使えるみたい。

import java.util.*;
public class aoj0033 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int A[] = new int[10], n = stdin.nextInt();
		while(n-- > 0){
			for(int i=0; i<10; ++i) A[i] = stdin.nextInt();
			System.out.println( solve(A) ? "YES" : "NO");
		}
	}
	static boolean solve(int A[]){
		int b=0, c=0;
		for(int a : A){
			if(b < a) b=a;
			else if(c < a) c=a;
			else return false;
		}
		return true;
	}
}

Railway Lines(AOJ No.0034)

駅の区間距離が(左から)10個と、電車1,2の速度が与えられる。
駅は1直線状に並んでいて、はじめ、電車1,2は一番左の駅と、右の駅にいる。
電車が同時に動き出したとき、すれ違う区間を答える。
駅のところでちょうどすれ違う時は小さい方の区間を答える。

アルゴリズム

電車1,2の位置の式は
、
。
となる時間は。
ここでは左端の駅から右端の駅までの距離。
従って、すれ違う位置は
この位置の区間を２分探索で探す。

コード

区間の番号が１から始まっているので、+1してる

import java.util.*;
public class aoj0034 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			String s[] = stdin.nextLine().split(",");
			Double[] x = new Double[s.length-2];
			x[0] = (double)Integer.parseInt(s[0]);
			for(int i=1; i<x.length; ++i)
				x[i] = x[i-1] + Integer.parseInt(s[i]);
			int v1 = Integer.parseInt( s[s.length-2] );
			int v2 = Integer.parseInt( s[s.length-1] );
			System.out.println( solve(x,v1,v2) );
		}
	}
	static int solve(Double x[], int v1, int v2){
		return lowerBound(x, x[x.length-1]*v1/(v1+v2) )+1;
	}
	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); }
		});
	}
}