主にコーディング

移転しました

2011-09-25T02:57:00.001+09:00

http://d.hatena.ne.jp/todo314/

Codeforces Beta Round #87 Div. 1 Only

2011-09-18T23:21:00.000+09:00

Codeforces Beta Round #86 Div. 1 Only (9/16 0:00~2:00）

■A. Party

解法

グラフに注目したとき下のような列があったとする．
A₁->A₂->…->A_N
この列の中の任意の2ノードは，同じグループに属することができないため，最低でもNグループ必要だと分かる．
このようなNの中で最大のものN_maxを見つければ，任意の列は，長さが高々N_maxなので，N_max個のグループに高々1人で振り分けることが出来る．
結局，N_maxが答え．
#86 Div. 1 A. Party

■B. Lawnmower

解法

ジグザグに進んでいくため，貪欲に求めることが出来る．
#86 Div. 1 B. Lawnmower

■Result

oo--- 1146pts. 256th
1700→1717

Codeforces Beta Round #86 Div. 1 Only

2011-09-11T16:55:00.000+09:00

Codeforces Beta Round #86 Div. 1 Only (9/9 0:00~2:00）

■A. A Grammar Lessons

問題

解法

書くだけ．StatementのBNFをDFAにしてからコードにすると，機械的に解ける．
#86 Div. 1 A. A Grammar Lessons

■B. Petr#

問題

文字列s，s_begin，s_endが与えられる．
以下を満たす文字列tの個数を求めよ．

tはsの部分文字列
s_beginはtのprefix
s_endはtのsuffix

解法

■Result

o---- 254pts. 215th
1684->1700

TopCoder SRM 517

2011-09-11T04:56:00.016+09:00

TopCoder SRM 517 (9/11 1:00~3:00)

■CompositeSmash(Easy)

問題

ある数xをy≧2，z≧2，yz=xを満たす2つの数に分割する．
この分割操作を再帰的に繰り返す．
e.g., x=12ならば，(y,z)=(3,4) or (2,6)など．
1や素数は，それ以上分割できない．

初期値としてNが与えられる．
Nを任意の方法で分割していき，全ての分割が終了するまでにtargetが出現するかを判定せよ．

解法

全探索．念の為メモ化もしたが，無くても通る様子．
SRM 517 Div. 1 Easy CompositeSmash

■Result

o-- +0/-0
191.33pts. 301th

■Rating

1645->1673

Codeforces Beta Round #85 Div. 1 Only

2011-09-04T00:57:00.001+09:00

Codeforces Beta Round #85 Div. 1 Only (9/4 21:00~23:00）

■A. Petya and Inequiations

問題

n,x,yが与えられる．
a₁²+a₂²+…+a_n²≥x
a₁+a₂+…+a_n≤y
を満たす正整数の列
a₁,a₂,…,a_n
を求めよ．なければ，-1を返せ．

解法

a₁+a₂+…+a_n
の最小値はn．次に，
a₁+a₂+…+a_n=y
としたとき，
a₁²+a₂²+…+a_n²
の最大値は，
a_k=1 (1≤k≤n-1)
a_n=y-(n-1)
のとき，この値（=(n-1)+(y-(n-1))²）がx以上なら数列(a^k)が答え．
#85 Div. 1 A. Petya and Inequiations

■B. Petya and Divisors

問題

2つの数列
x₁,…,x_n
y₁,…,y_n
が与えられる．
各(x_i, y_i)について，
x_i mod k=0 かつ (∀j:i-y_i≤j<i) x_j mod k ≠ 0
なる正整数kの数を求めよ．

解法

x_iの各約数d_i,kについて，
それがx₁,…,x_i-1の約数である最後のインデックスp[d_i,k]を記録しておく．
p[d_i,k]<i-y_iなら条件を満たす．
その後，
p[d_i,k]=i
と更新．
#85 Div. 1 B. Petya and Divisors

■Result

o---- 484pts. 278th
1689 -> 1684

ドカーン．

TopCoder SRM 513

2011-09-03T01:04:00.000+09:00

TopCoder SRM 516(8/31 0:00~2:00)

敗北．

■NetworkXOneTimePad(Easy)

・解法

全探索．
Long.parseLong(str, 2)をLong.parseLong(str)と書いてしまい，終了数分前に直すはめになってしまった．

■Challenge Phase

TLEが狙えるかと思ったが撃墜失敗．むしろ，サンプルの弱さを考慮した撃墜を作っておくべきだった．

■Result

o-- +0/-1
50.0pts. 489th

■Rating

1727 -> 1645
捻挫+打撲．

Codeforces Beta Round #84 Div. 2 Only

2011-09-03T00:55:00.000+09:00

Codeforces Beta Round #84 Div. 2 Only 8/30 1:00~3:00）

■A. Nearly Lucky Number

問題

Lucky Digitを，4または7として定義する．
Lucky Numberは，Lucky Digitのみで表現される（10進）数のことである．
Nearly Lucky Numberとは，ある数に含まれるLucky Digitの個数が，Lucky Numberである数のことである．
与えられた数が，Nearly Lucky Numberかどうかを判定せよ．

解法

やるだけ．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class A{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	void run(){

		long n=sc.nextLong();

		int c=0;

		for(; n>0; n/=10){

			if(n%10==4||n%10==7){

				c++;

			}

		}

		boolean f=c>0;

		for(; c>0; c/=10){

			f&=c%10==4||c%10==7;

		}

		println(f?"YES":"NO");

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new A().run();

	}

}

■B. Lucky String

問題

Lucky Stringとは，ある文字列において出現するアルファベットのインデックスをアルファベット毎に分類・ソートしたときに，隣り合うインデックスの差がLucky Numberである文字列のことである．
長さnのLucky Stringの内，辞書式順で最も早いものを出力せよ．

解法

abcdabcd…
↑これをn文字出力するだけ．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class B{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	void run(){

		int n=sc.nextInt();

		StringBuffer sb=new StringBuffer("");

		for(int i=0; i<n;){

			for(char c='a'; c<='d'&&i<n; c++, i++){

				sb.append(c);

			}

		}

		println(sb.toString());

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new B().run();

	}

}

■C. Lucky Sum of Digits

問題

各桁の総和がnとなる最小のLucky Numberを求めよ．

解法

4の個数と，7の個数が固定ならば，
44…4477…77
という形のLucky Numberが最小であることは明らか．
次に，4の個数をa，7の個数をbとすると，
4a+7b=n
が成立する．
（例えば28で考えれば分かるが）上の条件を満たす(a, b)の中で，bが最大ものが最小のLucky Numberとなることは明らか．
従って，aを0から逐次増やしていき， (n-4a) mod 7=0となればそこで計算を終了すればいい．
そのようなaが見つからずにループが終了したときは，条件を満たすLucky Numberは存在しない．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class C{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	int n;



	void run(){

		n=sc.nextInt();

		for(int a=0; n-4*a>=0; a++){

			if((n-4*a)%7==0){

				int b=(n-4*a)/7;

				StringBuffer sb=new StringBuffer();

				for(int i=0; i<a; i++){

					sb.append('4');

				}

				for(int i=0; i<b; i++){

					sb.append('7');

				}

				println(sb.toString());

				return;

			}

		}

		println("-1");

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new C().run();

	}

}

■E. Lucky Tree

問題

ノード数n，辺の数n-1の非循環無向グラフ（＝全域木）が与えられる．
各辺には，重みがついている．
次の条件を満たす3つ組(i,j,k)の数を求めよ．

iからjの経路にはLucky Numberを重みとして持つ辺が少なくとも1つある．
iからkの経路にはLucky Numberを重みとして持つ辺が少なくとも1つある．

解法

例えば，グラフが以下のようなものだったとする．
ここで，点線になっている辺は，Lucky Numberの重みを持つ．
ポイントは，上の条件を満たさない3つ組みを求める方が簡単だということ．
例えば，グループ1に注目してみる．
グループ1から選んだ3ノードより構成される3つ組み (v₁,v₂,v₃)は，決して上の条件を満たさない．
また，グループ1から2ノード（v₁,v₂とする）を選び，グループ1以外の任意の1ノード（uとする）を選んだとき，
(v₁,v₂,u)，(v₁,u,v₂)
も上の条件を満たさない．
つまり，あるグループkがmノードから構成されているとすれば，
m(m-1)(m-2)+2m(m-1)(n-m)
が，グループkのノードを2つ以上含みかつ上の条件を満たさ「ない」3つ組みの総数となる．
全てのグループについて上式の和を計算したものをsumとする．
最後に，nノードから3つ選ぶ順列の総数はn(n-1)(n-2)であるから，
n(n-1)(n-2)-sumが答えとなる．
さて，どうやってグラフ構造をグループに分け，そのグループのノード数を計算するだが，これについては，Union-Findを用いるのがスマートだと思われる．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class E{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	int n;



	void run(){

		n=sc.nextInt();

		make(n);



		for(int i=0; i<n-1; i++){

			int u=sc.nextInt()-1;

			int v=sc.nextInt()-1;

			int w=sc.nextInt();

			if(!isLucky(w)){

				union(u, v);

			}

		}



		debug(p);



		long ans=0;

		for(int i=0; i<n; i++){

			long s=size(i);

			if(p[i]>=0){

				continue;

			}

			if(s>=3){

				ans+=s*(s-1)*(s-2);

			}

			if(s>=2){

				ans+=s*(s-1)*(n-s)*2;

			}

		}



		// debug(n*(n-1)*(n-2));

		// debug(ans);

		ans=(long)n*(n-1)*(n-2)-ans;

		println(ans+"");

	}



	boolean isLucky(int n){

		for(; n>0; n/=10){

			if(n%10!=4&&n%10!=7){

				return false;

			}

		}

		return true;

	}



	int[] p;



	void make(int n){

		p=new int[n];

		fill(p, -1);

	}



	int find(int x){

		return p[x]<0?x:(p[x]=find(p[x]));

	}



	boolean union(int x, int y){

		x=find(x);

		y=find(y);

		if(x!=y){

			if(p[y]<p[x]){

				int t=x;

				x=y;

				y=t;

			}

			p[x]+=p[y];

			p[y]=x;

		}

		return x!=y;

	}



	int size(int x){

		return -p[find(x)];

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new E().run();

	}

}

■Result

ooo-o 4068pts. 27th
1631 -> 1689

Codeforces Beta Round #83 Div. 2 Only

2011-09-03T00:03:00.000+09:00

Codeforces Beta Round #83 Div. 2 Only 8/24 0:00~2:00）

■A. Palindromic Times

問題

デジタル時計の時刻が与えられる（HH:MMの形式）．
その時刻以降で，時刻が回文になるものを求めよ．

解法

高々24x60回の計算で終わるので，逐一試す．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class A{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	void run(){

		String[] ss=sc.next().split(":");

		int h=Integer.parseInt(ss[0]);

		int m=Integer.parseInt(ss[1]);

		for(;;){

			if(++m==60){

				m=0;

				if(++h==24){

					h=0;

				}

			}

			String s=String.format("%02d:%02d", h, m);

			if(new StringBuffer(s).reverse().toString().equals(s)){

				println(s);

				return;

			}

		}

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new A().run();

	}

}

■C. Dorm Water Supply

問題・解法

ある有向グラフが与えられる．
頂点には，多くとも1つの入る/出る辺があり，辺には情報として容量が与えられる．
以下を満たす（頂点V，頂点U，容量C）を求めよ．

Vには入る辺がない．
Uには出る辺がない．
Vから辺を辿ることで，Uに到着する．
Cは，VからUに至る辺の容量で最小のもの．

問題を意訳すると以上のようになるため，あとは書くだけです．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class C{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	int n, p;

	E[] es;

	int[] parent;

	LinkedList<E> answers;

	boolean[] visited;



	class E{

		int from, to, cap;



		E(int from, int to, int cap){

			this.from=from;

			this.to=to;

			this.cap=cap;

		}

	}



	void run(){

		n=sc.nextInt();

		p=sc.nextInt();

		es=new E[n];

		answers=new LinkedList<E>();

		parent=new int[n];

		fill(parent, -1);

		for(int i=0; i<n; i++){}

		for(int i=0; i<p; i++){

			int a=sc.nextInt()-1;

			int b=sc.nextInt()-1;

			int d=sc.nextInt();

			es[a]=new E(a, b, d);

			parent[b]=a;

		}

		solve();

	}



	void solve(){

		visited=new boolean[n];

		for(int i=0; i<n; i++){

			if(visited[i]){

				continue;

			}

			int k=i;

			boolean loop=false;

			for(; parent[k]>=0;){

				k=parent[k];

				if(k==i){

					loop=true;

					break;

				}

			}

			if(loop){

				continue;

			}

			if(es[k]!=null){

				visited[k]=true;

				dfs(es[k].to, k, es[k].cap);

			}

		}

		E[] anss=answers.toArray(new E[0]);

		sort(anss, new Comparator<E>(){

			@Override

			public int compare(E e1, E e2){

				return e1.from-e2.from;

			}

		});

		println(anss.length+"");

		for(E e : anss){

			println(e.from+" "+e.to+" "+e.cap);

		}

	}



	void dfs(int v, int tank, int diameter){

		visited[v]=true;

		if(es[v]==null){

			answers.add(new E(tank+1, v+1, diameter));

			return;

		}

		dfs(es[v].to, tank, min(diameter, es[v].cap));

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		// System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new C().run();

	}

}

■D. Basketball Team

問題

N人からなるチームを作りたい．
候補は全部でS人であり，Herr Wafaには仲間がK人いる．
S人からN人をランダムに選ぶとき，
Herr Wafaが少なくとも一人の仲間と一緒になる確率を求めよ．
N人を選べない（候補の人数が足りない）場合は-1とせよ．

解法

Herr Wafaがチームに選ばれなかった状態は省く．
(N, R)を二項係数（＝N個からR個を選ぶ組み合わせの総数）とする．
Herr Wafaがチームに選ばれたとして，残りのN-1人を選ぶ方法は(S-1, N-1)通り．
その内，仲間が一人も居ない場合は(S-1-K, N-1)通り．すなわち，
1-{(S-1-K, N-1)/(S-1, N-1)}
が答え．
左の項はもっと簡単に，
(S-N)(S-N-1)…(S-N-K+1)
-----------------------
(M-1)(M-2)…(M+K)
と表せるので，ループ一つで求められる．
但し，精度が落ちないように工夫して計算する必要がある（下記コード参照）．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class D{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	int n, m, h;

	int[] s;



	void run(){

		n=sc.nextInt();

		m=sc.nextInt();

		h=sc.nextInt()-1;

		s=new int[m];

		for(int i=0; i<m; i++){

			s[i]=sc.nextInt();

		}

		solve();

	}



	void solve(){

		int sum=0;

		for(int i=0; i<m; i++){

			sum+=s[i];

		}

		if(sum<n){

			println("-1.0");

			return;

		}

		int k=s[h]-1;

		double ans=1;

		for(int i=0; i<k; i++){

			ans*=(double)(sum-n-i)/(sum-1-i);

		}

		println((1-ans)+"");

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new D().run();

	}

}

■Result

oxoo- 2816pts. 78th
1562 -> 1631
次回でDiv.1に戻れるかも知れないがしかし…．

CodeChef August Cook-off 2011

2011-08-25T18:06:00.001+09:00

CodeChef August Cook-off 2011（8/22 1:00~3:30）

■Open the Dragon Scroll

問題

A，B，Nが与えられる．
（2進数で）A，BのビットをNビットに収まる範囲で自由に並び替える．
A xor B = Cの最大値を求めよ．

解法

A，Bにおける1のビットの数を|A|，|B|とする．

1.|A|+|B|≦N

この時は，以下のようにビットを並び替えれば最大値になる．
A→11…1100…0000…00
B→00…0011…1100…00
C→11…1111…1100…00
（1が|A|+|B|個，0がN-(|A|+|B|)個）

2.|A|+|B|>N

xorをとると，どうしてもどこかでAの1とBの1が相殺して0になってしまう．
そのため，ビットを下のように並びかえる．
A→11…1100…0011…11
B→00…0011…1111‥11
この時，1 xor 1 = 0で相殺されてしまう1（右端の1のこと）の個数をXとすれば，
|A|+|B|-X=N
∴X=|A|+|B|-N
C→11…1111…1100…00
（1が2|N|-(|A|+|B|)個，0が|A|+|B|-N個）


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class Main{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	int t, n, a, b;



	void run(){

		t=sc.nextInt();

		for(int i=0; i<t; i++){

			n=sc.nextInt();

			a=sc.nextInt();

			b=sc.nextInt();

			solve();

		}

	}



	void solve(){

		int ans=0;

		int bitA=Integer.bitCount(a);

		int bitB=Integer.bitCount(b);

		if(bitA+bitB<=n){

			for(int i=0; i<n; i++){

				ans<<=1;

				if(i<bitA+bitB){

					ans++;

				}

			}

		}else{

			for(int i=0; i<n; i++){

				ans<<=1;

				if(i<2*n-(bitA+bitB)){

					ans++;

				}

			}

		}

		println(ans+"");

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new Main().run();

	}

}

■Vote for the Noodle Soup

問題

ある投票システムがある．
投票する際のスコアは+1/-1で，一度投票したら無効には出来ない．
スコアを見るためには，上記のスコアで投票する必要がある．
Poは，（+1/-1に）複数回投票し，スコアを記録した．
得られたスコアから，（Poを除いた）総投票者の最小数を求めよ．

解法

得られたスコアをscore[i]と表す．
Poが入れたポイント（vote[i]とする）は計算の邪魔なので，score[i]から予め引いておく．
score[0]～score[n-1]まで逐一見ていく．
i番目まで見たときの投票者数の最小値をnUsers[i]とする．
明らかなのは，
nUsers[0]=0
nUsers[i+1]=max(nUsers[i], |score[i+1]|)
ということ．投票者数は，最低でもスコアの絶対値だけ必要．
次に，nUsers[i]+score[i+1]が奇数だった場合は，
nUsers[i+1]=nUsers[i]+1
とする必要がある．何故なら，
nUsers[i]が偶数/奇数⇔score[i]が偶数/奇数
だから．そして，投票者数は減らないから，+1する．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;



import static java.lang.Math.*;

import static java.util.Arrays.*;



public class Main{

	Scanner sc=new Scanner(System.in);



	int INF=1<<28;

	double EPS=1e-9;



	int n;

	int[] vote, ps;



	void run(){

		for(;;){

			n=sc.nextInt();

			if(n==0){

				break;

			}

			vote=new int[n];

			ps=new int[n];

			for(int i=0; i<n; i++){

				vote[i]=sc.next().equals("P")?+1:-1;

				ps[i]=sc.nextInt()-vote[i];

			}

			solve();

		}

	}



	void solve(){

		int min=0;

		for(int i=0; i<n; i++){

			if(abs(ps[i]+min)%2==1){

				min++;

			}

			min=max(min, abs(ps[i]));

		}

		println(min+"");

	}



	void println(String s){

		System.out.println(s);

	}



	void print(String s){

		System.out.print(s);

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	public static void main(String[] args){

		new Main().run();

	}

}

■Result

o-o--
実に不本意な結果…．

京都大学プログラミングコンテスト KUPC 2011

2011-08-10T00:32:00.001+09:00

京都大学プログラミングコンテスト KUPC 2011(8/6 13:00~18:00)

久しぶりに，非定期コンテストに参加．

■A KUPC

文字ごとの出現回数をカウントして，
min(count['K'], count['U'], count['P'], count['C'])
が答え．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;

import static java.lang.Math.*;

import static java.util.Arrays.*;



public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;

	double EPS=1e-12;



	void run(){

		String s=sc.next();

		int[] count=new int[256];

		for(char c : s.toCharArray()){

			count[c]++;

		}

		int ans=min(count['K'], min(count['U'], min(count['P'], count['C'])));

		println(ans+"");

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	void print(String s){

		System.out.print(s);

	}



	void println(String s){

		System.out.println(s);

	}



	public static void main(String[] args){

		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));

		new Main().run();

	}

}

■B 蝉

典型的なDP．
dp[y][x] := (x,y)に到達までに出会う蝉の数の最小値
右か下にしかいけないので，(x,y)の左と上を見ればdp[y][x]を決定できる．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;

import static java.lang.Math.*;

import static java.util.Arrays.*;



public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;

	double EPS=1e-12;



	int n, m;

	int[][] a;



	void run(){

		n=sc.nextInt();

		m=sc.nextInt();

		a=new int[n][m];

		for(int j=0; j<n; j++){

			String s=sc.next();

			for(int i=0; i<m; i++){

				a[j][i]=s.charAt(i)-'0';

			}

		}



		int[][] dp=new int[n][m];

		for(int j=0; j<n; j++){

			fill(dp[j], INF);

		}

		dp[0][0]=0;

		for(int j=0; j<n; j++){

			for(int i=0; i<m; i++){

				if(j>0){

					dp[j][i]=min(dp[j][i], dp[j-1][i]+a[j][i]);

				}

				if(i>0){

					dp[j][i]=min(dp[j][i], dp[j][i-1]+a[j][i]);

				}

			}

		}

		println(dp[n-1][m-1]+"");

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	void print(String s){

		System.out.print(s);

	}



	void println(String s){

		System.out.println(s);

	}



	public static void main(String[] args){

		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));

		new Main().run();

	}

}

■C しりとり

'xa'と尋ね続ければ，その内，'a'で始まる文字列が無くなることを利用する．
途中で，不正な返答が来た時の処理等を忘れてWAを食らいまくる．


package c;



import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;

import static java.lang.Math.*;

import static java.util.Arrays.*;



public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;

	double EPS=1e-12;



	void run(){

		TreeSet set=new TreeSet();

		println("?a");

		System.out.flush();

		set.add("a");

		String next="";

		char ch='a';

		for(; sc.hasNext();){

			String s=sc.next();

			boolean out=false;

			out|=s.charAt(0)!='a';

			out|=set.contains(s);

			if(out){

				println("!OUT");

				break;

			}

			set.add(s);

			println("?"+s.charAt(s.length()-1)+next+ch+"a");

			if(ch++=='z'){

				next+='z';

				ch='a';

			}

			System.out.flush();

		}

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	void print(String s){

		System.out.print(s);

	}



	void println(String s){

		System.out.println(s);

	}



	public static void main(String[] args){

		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));

		new Main().run();

	}

}

■D 列の構成

ずっとやり方を考えていたが，DFS+適当な枝刈りで通ってしまった．想定解法は乱択アルゴリズムという珍しい問題．


import java.util.*;

import java.lang.*;

import java.math.*;

import java.io.*;

import static java.lang.Math.*;

import static java.util.Arrays.*;



public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;

	double EPS=1e-12;



	int n, k;

	int[][] a, sum;

	int[] count, seq;

	boolean[] brank;

	boolean end=false;



	void run(){

		n=sc.nextInt();

		k=sc.nextInt();

		a=new int[k][n];

		brank=new boolean[n];

		sum=new int[k][n+1];

		fill(brank, true);

		for(int j=0; j<k; j++){

			for(int i=0; i<n/2; i++){

				int k=sc.nextInt();

				a[j][k-1]=1;

				brank[k-1]=false;

			}

			for(int i=0; i<n; i++){

				sum[j][i+1]=sum[j][i]+a[j][i];

			}

		}

		count=new int[k];

		seq=new int[n];

		rec(0);

	}



	void rec(int x){

		if(end){

			return;

		}



		// 枝刈り

		for(int j=0; j<k; j++){

			int rem=sum[j][n]-sum[j][x];

			if(count[j]+rem<n/8){

				return;

			}

			if(count[j]>3*n/8){

				return;

			}

		}



		if(x==n){

			end=true;

			for(int i=0; i<n; i++){

				print(seq[i]+"");

			}

			println("");

			return;

		}



		if(brank[x]){

			rec(x+1);

			return;

		}



		seq[x]=0;

		rec(x+1);



		seq[x]=1;

		for(int j=0; j<k; j++){

			count[j]+=a[j][x];

		}

		rec(x+1);

		for(int j=0; j<k; j++){

			count[j]-=a[j][x];

		}



	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	void print(String s){

		System.out.print(s);

	}



	void println(String s){

		System.out.println(s);

	}



	public static void main(String[] args){

		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));

		new Main().run();

	}

}

■E Fox Number

Fox Numberでない数を列挙する． n=p₁p₂²は条件を満たさないことを使う（p₁，p₂は素数）．
kn∈[A-B, A+B]となる最小のkを以下で求める．
k=max([(A-B)/n], 1)
そして，kn∈[A-B, A+B]である間，kをインクリメント．
ここで，kn=p₁^1+r_kp₂^2+s_km と表わすことが出来る．
1+r_k < 2+s_k
ならば，knはFox Numberでないので，
isNotFoxNumber[kn]=true
これを妥当な範囲内の素数全てについて行う．


import java.util.*;

import java.util.Map.Entry;

import java.lang.*;

import java.math.*;

import java.io.*;

import static java.lang.Math.*;

import static java.util.Arrays.*;



public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;

	double EPS=1e-12;



	long a;

	int b;

	int p, m;

	int[] prime;

	boolean[] isPrime;

	boolean[] fox;



	void run(){

		a=sc.nextLong();

		b=sc.nextInt();



		fox=new boolean[2*b+1];

		fill(fox, true);

		

		for(int i=0;i<2*b+1;i++){

			if(i-b+a<2){

				fox[i]=false;

			}

		}



		m=(int)sqrt(a+b)+10;

		p=0;

		prime=new int[m];

		isPrime=new boolean[m+1];

		Arrays.fill(isPrime, true);

		isPrime[0]=isPrime[1]=false;

		for(int i=2; i<=m; i++){

			if(isPrime[i]){

				prime[p++]=i;

				for(int j=2*i; j<=m; j+=i)

					isPrime[j]=false;

			}

		}



		int e1=1, e2=2;

		for(int p2=0; p2<p; p2++){

			long n2=(long)prime[p2]*prime[p2];

			if(n2>a+b){

				break;

			}

			for(int p1=0; p1<p2; p1++){

				long n1=prime[p1];

				long n=n1*n2;

				if(n<0){

					debug(n);

				}

				if(n>a+b){

					break;

				}



				int c=0;

				for(long k=max((a-b)/n, 1); k*n<=a+b; k++){

					c++;

					int pc1=0;

					for(long i=k; i%prime[p1]==0; i/=prime[p1]){

						pc1++;

					}

					int pc2=0;

					for(long i=k; i%prime[p2]==0; i/=prime[p2]){

						pc2++;

					}



					if(e1+pc1<e2+pc2){

						if(k*n>=a-b){

							fox[(int)(k*n-a+b)]=false;

						}

					}

				}

			}

		}



		int c=0;

		for(int i=0; i<2*b+1; i++){

			if(fox[i]){

				c++;

			}

		}



		println(c+"");

	}



	void debug(Object... os){

		System.err.println(Arrays.deepToString(os));

	}



	void print(String s){

		System.out.print(s);

	}



	void println(String s){

		System.out.println(s);

	}



	public static void main(String[] args){

		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));

		new Main().run();

	}

}

■結果

ooooo----- 500pts. 17th
まぁまぁの成績．

TopCoder SRM 513

2011-07-27T06:21:00.000+09:00

TopCoder SRM 513(7/26 20:00~22:00)

珍しい時間帯のSRM．夕飯後は眠くなるので辛い．

■YetAnotherIncredibleMachine(Easy)

・解法

全探索．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class YetAnotherIncredibleMachine {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int countWays(int[] mount, int[] length, int[] balls) {
  int n=length.length;
  int m=balls.length;
  long res=1;
  long mod=1000000009;
  for(int j=0;j<n;j++){ 
   int c=0;
   for(int x=-length[j];x<=0;x++){
    boolean f=true;
    for(int i=0;i<m;i++){
     if(mount[j]+x<=balls[i]&&balls[i]<=mount[j]+x+length[j]){
      f=false;
     }
    }
    if(f){
     c++;
    }
   }
   res=(res*c)%mod;
  }
  return (int)res;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

■PerfectMemory(Medium)

n(：偶数)枚のカードで神経衰弱を行う．一度めくったカードを全て記憶しておくことができるとしたとき，最適な戦略を用いた場合のゲーム終了までにめくる回数の期待値を求めよ．

解法

(残り枚数, 既に知っているカードの枚数)で期待値のDP．
既に知っているカードには，ペアは含まれない（=どの2枚も異なる）とする．
状態が(n, m)の時，n-mから1枚引く．

図では，暗い赤が知っているm枚（引かれないカード），明るい赤は暗い赤のカードに対応するペアの片割れ．

1.明るい赤を引いた時(m枚)

対応するカードを暗い赤から選ぶ．つまり，1ターンで，状態が(n-2,m-1)になる．よって，この時の期待値は1+dp(n-2,m-1)．

2.青を引いた時(n-2m枚)

引いたカードを暗い紫とする．この時対応するカードは青にある（明るい紫）．次に，n-m-1(青+明るい赤+明るい紫)から1枚引く．

2.1.明るい赤を引いたとき(m枚)

次のターンで，対応する赤のペアを引く．この時の期待値は，2+dp(n-2,m)．

2.2.青を引いたとき(n-2m-2枚)

既に知っているカードが2枚増えるだけなので，この時の期待値は，1+dp(n,m+2)．

2.3.明るい紫を引いたとき(1枚)

紫ペアがなくなるので，この時の期待値は，1+(n-2,m)．

これらからDPテーブルを更新していきます．初期値の与え方が面倒なので，メモ化再帰でもいいかも知れません．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class PerfectMemory {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public double getExpectation(int N, int M) {
  int n=N*M;
  double[][] dp=new double[n+1][n+1];
  for(int j=2;j<=n;j+=2){
   for(int i=j;i>=j/2;i--){
    dp[j][i]=j/2;
   }
   for(int i=j/2-1;i>=0;i--){
    double p1=(double)(j-2*i)/(j-i);
    double p2=(double)i/(j-i);
    double q1=(double)i/(j-i-1);
    double q2=(double)(j-2*i-2)/(j-i-1);
    double q3=(double)1/(j-i-1);
    dp[j][i]+=(2+dp[j-2][i])*p1*q1;
    dp[j][i]+=(1+dp[j][i+2])*p1*q2;
    dp[j][i]+=(1+dp[j-2][i])*p1*q3;
    if(i>0){
     dp[j][i]+=(1+dp[j-2][i-1])*p2;
    }
   }
  }
  for(int i=0;i<=n;i+=2){
   // debug(i, dp[i]);
  }
  return dp[n][0];
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

■Challenge Phase

撃墜無し．

■Result

oo- +0/-0
429.5pts. 104th
おそらくDiv.1では過去最高の成績です．加えてMediumを解けたのが初めてです．

■Rating

1620 -> 1727
大幅上昇．

TopCoder SRM 511

2011-07-04T02:24:00.000+09:00

TopCoder SRM 511(7/3 1:00~3:00)

YellowCoderとしては初のSRM．

■Zoo(Easy)

・問題

うさぎと猫がN匹いる．きつねは，うさぎと猫の区別が分からない．
そこで，N匹のそれぞれに「自分と同じ種類でかつ自分より背の高い動物は何匹いますか？」と尋ねた．
この情報のみを用いて，N匹へのうさぎと猫の割り当て方の総数を求めよ．

・解法

N匹の答えをa[0],…,a[N-1]とし，
配列countを配列aに出てきた数字の個数とする．
例えば，a={0,1,0,1,2,3}
だったら，
count={2,2,1,1,0,0,…}
となる．
上の例では，一方が2匹，もう一方が4匹いると分かる．
まず，うさぎが2匹，猫が4匹とする．
このとき，a[i]が0または1のときに関しては，うさぎと猫をどのように割り当てても良い．
具体的には，
RRCC|CC
CCRR|CC
RCCR|CC
CRRC|CC
こんな感じ（2²通り）．
逆に，うさぎが4匹，猫が2匹としても，上と同じよう構成ができるので，
結局2*2²=8通り．
これは，5匹と2匹，6匹と2匹，…でも変わらない．
そのため，N=m+nと分かれる場合，
m≠nならば，2*2^min(m,n)通り，
m=nならば，2^m通り．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Zoo {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public long theCount(int[] a) {
  int n=a.length;
  int[] count=new int[n];
  for(int i:a){
   if(i>=n){
    return 0;
   }
   if(++count[i]>2){
    return 0;
   }
  }
  int p=0, q=0;
  int k=0;
  // debug(count);
  for(int i=n-1;i>=0;i--){
   if(count[i]==k+2){
    p=q=i+1;
   }
   else if(count[i]==k+1){
    if(k==0){
     p=i+1;
    }else if(k==1){
     q=i+1;
    }
   }
   else if(count[i]==k){
   }
   else{
    return 0;
   }
   k=count[i];
  }
  // debug(p,q);
  long ret=1;
  for(int i=0;i<min(p,q);i++){
   ret*=2;
  }
  return ret*(p!=q?2:1);
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■FiveHundredElevenAdd(Medium)

本番は解けませんでしたので，simezi_tanさんの記事を参照下さい．
SRM 511 Div1 Medium FiveHundredEleven - simezi_tanの日記


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class FiveHundredEleven {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 int[][] memo; // 0:win, 1:lose
 int[] cards;
 int n;

 int rec(int step,int mem){
  if(memo[step][mem]>=0){
   return memo[step][mem];
  }
  if(mem==511){
   // former player loses.
   return memo[step][mem]=0;
  }
  if(step==n){
   // the player can't choose a card.
   return memo[step][mem]=1;
  }
  int not=0;
  for(int i=0;i<n;i++){
   if((mem|cards[i])==mem){
    not++;
   }
  }
  boolean win=false;
  // search : not-step cards that don't affect mem are not used
  if(not>step){
   win|=rec(step+1,mem)==1;
  }
  // search : cards that affect mem.
  for(int i=0;i<n;i++){
   if((mem|cards[i])!=mem){
    win|=rec(step+1,mem|cards[i])==1;
   }
  }
  return memo[step][mem]=win?0:1;
 }

 public String theWinner(int[] cards) {
  this.cards=cards;
  n=cards.length;
  memo=new int[n+1][512];
  for(int i=0;i<n+1;i++){
   fill(memo[i],-1);
  }
  return rec(0,0)==0?"Fox Ciel":"Toastman";
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■Challenge Phase

撃墜無し．撃墜しようと準備していましたが，他の人のコードが中々読めませんでした．

■Result

o-- +0/-0
144.29pts. 491th

■Rating

1532 -> 1527
微減．次は，TCO Round3ですが，個人的には気楽に挑戦したいと思っています．

TCO Algorithm Round2

2011-06-29T04:58:00.000+09:00

TCO Algorithm Round2(6/26 1:00~3:00)

驚異の悪運によりRound1を通過することが出来ていましたが，果してRound2は…．

■GuessTheNumberGame(Easy)

ある数字Mを1~Nまでの数で割り切れるかどうかを表す文字列を考える．例えばM=4，N=5とすると4は1,2,4で割り切れ，3,5では割り切れないので，YYNYNとなる．さて，N=5のとき，YNNYNとなるようなMは存在しないため，この文字列は無効である（4で割り切れて、2で割り切れないから）．長さMの文字列で，有効なものは何種類あるか．2種類以上の素数の積からなる合成数は，素因数のY or Nで一意に決まってしまうので，考慮しない．例えば，YYY--XならX=YYYN--XならX=NYNY--XならX=NYNN--XならX=Nとなる．次に，ある素数の冪乗を考える．例えば，M=9とすると，2の冪乗は2,4,8まで．この3つに着目した有効な文字列は，NNNYNNYYNYYYの4種類．つまり，p¹, p²,…, p^rについて有効な文字列はr+1種類．あとは，それらを掛け合わせるだけ．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class GuessTheNumberGame {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int possibleClues(int n) {
  long res=1;
  long mod=1000000007;
  boolean[] isP=new boolean[n+1];
  int[] p=new int[n+1];
  fill(isP,true);
  isP[0]=isP[1]=false;
  int k=0;
  for(int j=0;j<=n;j++){
   if(!isP[j]){
    continue;
   }
   p[k++]=j;
   for(int i=j*2;i<=n;i+=j){
    isP[i]=false;
   }
  }
  // debug(p);
  for(int i=0;i<k;i++){
   int c=0;
   for(long m=1;m<=n;m*=p[i]){
    c++;
   }
   // debug(i,p[i],c);
   res=(res*c)%mod;
  }
  return (int)res;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■Challenge Phase

撃墜無し．

■Result

o-- +0/-0
196.11pts. 341th
辛くも逃げきることが出来ました．

■Rating

1431 -> 1530
Round3進出+初YellowCoderです．今年のICPCは国内予選で落ちてしまったので，中々にショックでしたが，代わりにGoogleとTopCoder両方のTシャツをゲットできそうです．

Aizu Online Judge 1149 Cut the Cakes

2011-06-23T18:33:00.001+09:00

■1149 Cut the Cakes

やればできる．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, w, h;
 int[] ps, ss;

 void run(){
  for(;;){
   n=sc.nextInt();
   w=sc.nextInt();
   h=sc.nextInt();
   if((n|w|h)==0){
    break;
   }
   ps=new int[n];
   ss=new int[n];
   for(int i=0; i<n; i++){
    ps[i]=sc.nextInt()-1;
    ss[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  LinkedList<R> list=new LinkedList<R>();
  list.add(new R(0, 0, w, h));
  for(int i=0; i<n; i++){
   R r=list.remove(ps[i]);
   debug(i, r.x, r.y, r.w, r.h);
   int x=r.x, y=r.y;
   for(int k=0; k<ss[i]; k++){
    if(y==r.y&&x<r.x+r.w){
     x++;
    }else if(x==r.x+r.w&&y<r.y+r.h){
     y++;
    }else if(y==r.y+r.h&&x>r.x){
     x--;
    }else if(x==r.x&&y>r.y){
     y--;
    }else{
     debug("Error!");
    }
    // debug(x,y);
   }
   debug(x, y);
   R r1=null, r2=null;
   if(x==r.x||x==r.x+r.w){
    r1=new R(r.x, r.y, r.w, y-r.y);
    r2=new R(r.x, r.y+r1.h, r.w, r.h-r1.h);
   }else{
    r1=new R(r.x, r.y, x-r.x, r.h);
    r2=new R(r.x+r1.w, r.y, r.w-r1.w, r.h);
   }
   debug("r1", r1.x, r1.y, r1.w, r1.h);
   debug("r2", r2.x, r2.y, r2.w, r2.h);
   if(r1.w*r1.h<r2.w*r2.h){
    list.add(r1);
    list.add(r2);
   }else{
    list.add(r2);
    list.add(r1);
   }
  }
  R[] rs=list.toArray(new R[0]);
  sort(rs);
  String ans="";
  for(R r : rs){
   ans+=(r.w*r.h)+" ";
   debug(r.x, r.y, r.w, r.h, r.w*r.h);
  }
  println(ans.substring(0, ans.length()-1));
 }

 class R implements Comparable<R>{
  int x, y, w, h;

  R(int x, int y, int w, int h){
   this.x=x;
   this.y=y;
   this.w=w;
   this.h=h;
  }

  @Override
  public int compareTo(R r){
   return w*h-r.w*r.h;
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1131 Unit Fraction Partition

2011-06-23T18:33:00.000+09:00

■1131 Unit Fraction Partition

自明な+ちょっと工夫した枝刈りでAC．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int p0, q0, maxA, maxN;
 int ans;

 void run(){
  for(;;){
   p0=sc.nextInt();
   q0=sc.nextInt();
   maxA=sc.nextInt();
   maxN=sc.nextInt();
   if((p0|q0|maxA|maxN)==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  int gcd=gcd(p0, q0);
  p0/=gcd;
  q0/=gcd;
  ans=0;
  dfs(0, 1, 1, 1, 0);
  // debug(ans);
  println(""+ans);
 }

 void dfs(int p, int q, int qNow, int a, int n){
  if(n>maxN){
   return;
  }
  if(a>maxA){
   return;
  }
  if(p*q0-q*p0>0){
   return;
  }
  {
   int p2=maxN-n;
   int q2=qNow;
   int pp=p*q2+q*p2;
   int qq=q*q2;
   if(pp*q0-qq*p0<0){
    return;
   }
  }
  // debug(p,q,qNow,a,n);
  if(p==p0&&q==q0){
   ans++;
   return;
  }
  for(int i=qNow; i*a<=maxA; i++){
   int p2=p*i+q;
   int q2=q*i;
   int gcd=gcd(p2, q2);
   p2/=gcd;
   q2/=gcd;
   dfs(p2, q2, i, i*a, n+1);
  }
 }

 int gcd(int m, int n){
  for(; m!=0;){
   int t=n%m;
   n=m;
   m=t;
  }
  return n;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1156 Twirling Robot

2011-06-20T20:42:00.000+09:00

■1156 Twirling Robot

(x座標，y座標，方向ベクトル)を状態としたDijkstra．コストのつけ方が特殊だが，少し注意すれば特に問題無い．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int[][] a;
 int[] c;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
    }
   }
   c=new int[4];
   for(int i=0; i<4; i++){
    c[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int[][][] d=new int[n][m][4];
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    fill(d[j][i], INF);
   }
  }
  int[] dx={1, 0, -1, 0};
  int[] dy={0, 1, 0, -1};
  PriorityQueue<P> que=new PriorityQueue<P>();
  que.offer(new P(0, 0, 0));
  d[0][0][0]=0;
  for(; !que.isEmpty();){
   P p=que.poll();
   if(p.d>d[p.y][p.x][p.v]){
    continue;
   }
   int[] cost=c.clone();
   if(a[p.y][p.x]!=4){
    cost[a[p.y][p.x]]=0;
   }
   for(int i=0; i<4; i++){
    P q=new P(p.x, p.y, (p.v+i)%4);
    q.x+=dx[q.v];
    q.y+=dy[q.v];
    if(q.x<0||q.x>=m||q.y<0||q.y>=n){
     continue;
    }
    if(d[q.y][q.x][q.v]>d[p.y][p.x][p.v]+cost[i]){
     q.d=d[q.y][q.x][q.v]=d[p.y][p.x][p.v]+cost[i];
     que.offer(q);
    }
   }
  }
  int ans=INF;
  for(int i=0; i<4; i++){
   ans=min(ans, d[n-1][m-1][i]);
  }
  println(ans+"");
 }

 class P implements Comparable<P>{
  int x, y, v;
  int d;

  P(int x, int y, int v){
   this.x=x;
   this.y=y;
   this.v=v;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1136 Polygonal Line Search

2011-06-20T20:41:00.000+09:00

■1136 Polygonal Line Search

回転および平行移動を適用したということは，各々の線分ベクトルを0,90,180,270°の何れかの角度回転させたことになる．従って，元の折れ線の内の1つの線分ベクトルと，探す対象の折れ線の内の1つの線分ベクトルを見れば何度回転させたか分かる．あとは，残りの線分ベクトルを回転させ，元の折れ線の線分ベクトルに一致するかを見ていけば良い．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] m;
 int[][] xs, ys;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   m=new int[n+1];
   xs=new int[n+1][];
   ys=new int[n+1][];
   for(int j=0; j<=n; j++){
    m[j]=sc.nextInt();
    xs[j]=new int[m[j]];
    ys[j]=new int[m[j]];
    for(int i=0; i<m[j]; i++){
     xs[j][i]=sc.nextInt();
     ys[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  for(int i=1; i<=n; i++){
   if(m[0]==m[i]&&match(m[0], xs[0], ys[0], xs[i], ys[i])){
    println(i+"");
   }
  }
  println("+++++");
 }

 boolean match(int m, int[] xs1, int[] ys1, int[] xs2, int[] ys2){
  int[][][] a={{{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}},
    {{0, 1}, {-1, 0}}};

  int k1=-1, k2=-1;
  for(int j=0; j<4; j++){
   int vx1=xs1[1]-xs1[0];
   int vy1=ys1[1]-ys1[0];
   int vx2=xs2[1]-xs2[0];
   int vy2=ys2[1]-ys2[0];
   if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx2
     &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy2){
    k1=j;
   }
   int vx3=xs2[m-2]-xs2[m-1];
   int vy3=ys2[m-2]-ys2[m-1];
   if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx3
     &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy3){
    k2=j;
   }
  }

  boolean f1=k1!=-1, f2=k2!=-1;
  for(int i=0; i<m-1; i++){
   int vx1=xs1[i+1]-xs1[i];
   int vy1=ys1[i+1]-ys1[i];
   int vx2=xs2[i+1]-xs2[i];
   int vy2=ys2[i+1]-ys2[i];
   int vx3=xs2[m-i-2]-xs2[m-i-1];
   int vy3=ys2[m-i-2]-ys2[m-i-1];
   if(k1!=-1){
    f1&=vx1*a[k1][0][0]+vy1*a[k1][0][1]==vx2
      &&vx1*a[k1][1][0]+vy1*a[k1][1][1]==vy2;
   }
   if(k2!=-1){
    f2&=vx1*a[k2][0][0]+vy1*a[k2][0][1]==vx3
      &&vx1*a[k2][1][0]+vy1*a[k2][1][1]==vy3;
   }
  }

  return f1||f2;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

CodeChef June Cook-off 2011

2011-06-20T04:58:00.000+09:00

CodeChef June Cook-off 2011（6/20 1:00~3:30)

■Correctness of Knight Move

やるだけ．出力をバッファリングしないとTLEします（しました）．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 String s;

 void run(){
  n=sc.nextInt();
  sc.nextLine();
  String[] ans={"Yes", "No", "Error"};
  for(int i=0; i<n; i++){
   s=sc.nextLine();
   println(ans[solve()]);
  }
  System.out.flush();
 }

 int solve(){
  boolean legal=true;
  if(s.length()!=5){
   return 2;
  }
  legal&='a'<=s.charAt(0)&&s.charAt(0)<='h';
  legal&='1'<=s.charAt(1)&&s.charAt(1)<='8';
  legal&=s.charAt(2)=='-';
  legal&='a'<=s.charAt(3)&&s.charAt(3)<='h';
  legal&='1'<=s.charAt(4)&&s.charAt(4)<='8';
  if(!legal){
   return 2;
  }
  int x1=s.charAt(0)-'a';
  int y1=s.charAt(1)-'1';
  int x2=s.charAt(3)-'a';
  int y2=s.charAt(4)-'1';

  int dx=abs(x1-x2);
  int dy=abs(y1-y2);

  return (dx==1&&dy==2)||(dx==2&&dy==1)?0:1;
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

■Super-plane

Dunnoの挙動は分岐無しなので，適当なループで解けます．コンテスト中は勘違いしていて，BFSをしようとしてTLE食らいまくっていました．さらに，Javaの入出力がバッファリングしてなかったため，少し調整しないと通りませんでした．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
 // Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int t, n;
 int cs, ts, cg, tg;
 E[] es;

 void run() throws Exception{
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  t=Integer.parseInt(br.readLine());
  for(; t>0; t--){
   n=Integer.parseInt(br.readLine());
   es=new E[n];
   for(int i=0; i<n; i++){
    String[] ss=br.readLine().split(" ");
    int c1=Integer.parseInt(ss[0])-1;
    int t1=Integer.parseInt(ss[1]);
    int c2=Integer.parseInt(ss[2])-1;
    int t2=Integer.parseInt(ss[3]);
    es[i]=new E(c1, t1, c2, t2);
   }
   sort(es);
   String[] ss=br.readLine().split(" ");
   cs=Integer.parseInt(ss[0])-1;
   ts=Integer.parseInt(ss[1]);
   cg=Integer.parseInt(ss[2])-1;
   tg=Integer.parseInt(ss[3]);
   solve();
  }
  System.out.flush();
 }

 void solve(){
  P p=new P(cs, ts);
  boolean[] visited=new boolean[n];
  int ans=0;
  boolean ok=true;
  E key=new E(p.c, p.t, 0, 0);
  for(;; ans++){
   if(p.c==cg&&p.t<=tg){
    break;
   }
   key.c1=p.c;
   key.t1=p.t;
   int k=binarySearch(es, key);
   if(k<0){
    k=-1-k;
   }
   if(k==n){
    ok=false;
    break;
   }
   if(es[k].c1!=p.c){
    ok=false;
    break;
   }
   if(visited[k]){
    ok=false;
    break;
   }
   visited[k]=true;
   p.c=es[k].c2;
   p.t=es[k].t2;
  }
  if(ok){
   println("Yes "+ans);
  }else{
   println("No");
  }
 }

 class E implements Comparable<E>{
  int c1, t1, c2, t2;

  E(int c1, int t1, int c2, int t2){
   this.c1=c1;
   this.t1=t1;
   this.c2=c2;
   this.t2=t2;
  }

  @Override
  public int compareTo(E e){
   if(c1!=e.c1){
    return c1-e.c1;
   }else{
    return t1-e.t1;
   }
  }
 }

 class P implements Comparable<P>{
  int c, t;

  P(int c, int t){
   this.c=c;
   this.t=t;
  }

  @Override
  public int compareTo(P p){
   if(c!=p.c){
    return c-p.c;
   }else{
    return t-p.t;
   }
  }
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  try{
   new Main().run();
  }catch(Exception e){
   e.printStackTrace();
  }
 }
}

■Result

--o--

またもやこれは酷い…．CodeChefとは相性が悪いようです．C++に乗り換えるのも手だと思われます．

TCO Algorithm Round1

2011-06-19T03:20:00.000+09:00

TCO Algorithm Round1(6/19 1:00~3:00)

■TripleStrings(Easy)

キューA，B，Cがある．最初，キューAには'o'と'x'から構成される文字列(=init)が入っており，キューB，Cは空である．Aからポップした文字は，BとCにプッシュできる．B，Cからポップした文字は，Aにプッシュできる．キューA内の文字列をinitからgoalに変更するためのポップの回数の最小値を返せ．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class TripleStrings {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int getMinimumOperations(String init, String goal) {
  int n=init.length();
  int max=0;
  for(int j=1;j<=n;j++){
   boolean f=true;
   for(int i=0;i<j;i++){
    f&=init.charAt(n-j+i)==goal.charAt(i);
   }
   if(f){
    max=max(max,j);
   }
  }
  return (n-max)*2;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■Challenge Phase

撃墜無し．Challengeボタンをポチるコンマ数秒前に他の人に撃墜されました．

■Result

o-- +0/-0
232.61pts. 837th

■Rating

1414 -> 1431
残念…．

Aizu Online Judge 1155 How can I satisfy thee? Let me count the ways...

2011-06-07T00:22:00.002+09:00

■1155 How can I satisfy thee? Let me count the ways...

構文解析ゲー．変数への数の割り当て方は高々27通りなので，全部試せば良い．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 String s;
 int[] map;

 void run(){
  for(;;){
   s=sc.next();
   if(s.equals(".")){
    break;
   }
   solve();
  }
 }

 void solve(){
  map=new int[256];
  map['0']=0;
  map['1']=1;
  map['2']=2;
  int ans=0;
  for(int p=0; p<3; p++){
   for(int q=0; q<3; q++){
    for(int r=0; r<3; r++){
     map['P']=p;
     map['Q']=q;
     map['R']=r;
     Result res=f(0);
     if(res.value==2){
      ans++;
     }
    }
   }
  }
  println(ans+"");
 }

 Result f(int p){
  // debug("f",p);
  if(Character.isDigit(s.charAt(p))||Character.isUpperCase(s.charAt(p))){
   return new Result(p+1, map[s.charAt(p)]);
  }else if(s.charAt(p)=='-'){
   Result r=f(p+1);
   r.value=2-r.value;
   return r;
  }else{
   Result r=f(p+1);
   Result r2=f(r.p+1); // skip '*' or '+'
   if(s.charAt(r.p)=='*'){
    r.value=min(r.value, r2.value);
   }else{ // '+'
    r.value=max(r.value, r2.value);
   }
   r.p=r2.p+1;
   return r;
  }
 }

 class Result{
  int p, value;

  Result(int p, int value){
   this.p=p;
   this.value=value;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1244 Molecular Formula

2011-06-07T00:22:00.001+09:00

■1244 Molecular Formula

構文解析ゲー．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 HashMap<String, Integer> map;
 String s;
 boolean unknown;

 void run(){
  map=new HashMap<String, Integer>();
  for(;;){
   String s=sc.next();
   if(s.equals("END_OF_FIRST_PART")){
    break;
   }
   int n=sc.nextInt();
   map.put(s, n);
  }
  for(;;){
   s=sc.next();
   if(s.equals("0")){
    break;
   }
   s+='\0';
   unknown=false;
   Result r=molecule(0);
   println(unknown?"UNKNOWN":r.value+"");
   debug(r.p, r.value);
  }
 }

 Result molecule(int p){
  debug("molecule", p);
  Result r=new Result(p, 0);
  for(;;){
   if(s.charAt(r.p)=='\0'||s.charAt(r.p)==')'){
    // end of molecule
    return r;
   }else if(s.charAt(r.p)=='('){
    Result r1=molecule(r.p+1);
    Result r2=number(r1.p+1); // skip '('
    r.value+=r1.value*r2.value;
    r.p=r2.p;
   }else{
    Result r1=atom(r.p);
    Result r2=number(r1.p);
    r.value+=r1.value*r2.value;
    r.p=r2.p;
   }
  }
 }

 Result atom(int p){
  debug("atom", p);
  String atom="";
  if(Character.isUpperCase(s.charAt(p))){
   atom+=s.charAt(p);
   p++;
   if(Character.isLowerCase(s.charAt(p))){
    atom+=s.charAt(p);
    p++;
   }
  }
  debug(atom);
  if(map.containsKey(atom)){
   return new Result(p, map.get(atom));
  }else{
   unknown=true;
   return new Result(p, 0);
  }
 }

 Result number(int p){
  debug("number", p);
  int value=0;
  if(Character.isDigit(s.charAt(p))){
   value=s.charAt(p)-'0';
   p++;
   if(Character.isDigit(s.charAt(p))){
    value=value*10+s.charAt(p)-'0';
    p++;
   }
  }else{
   return new Result(p, 1);
  }
  return new Result(p, value);
 }

 class Result{
  int p, value;

  Result(int p, int value){
   this.p=p;
   this.value=value;
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1012 Operations with Finite Sets

2011-06-07T00:22:00.000+09:00

■1012 Operations with Finite Sets

構文解析ゲー．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;
 TreeSet<Integer>[] sets;
 String exp;
 TreeSet<Integer> U;

 @SuppressWarnings("unchecked")
 void run(){
  for(; sc.hasNext();){
   sets=new TreeSet[256];
   for(char c='A'; c<='E'; c++){
    sets[c]=new TreeSet<Integer>();
   }
   U=new TreeSet<Integer>();
   for(;;){
    char c=sc.next().charAt(0);
    int n=sc.nextInt();
    if(c=='R'&&n==0){
     break;
    }
    for(int i=0; i<n; i++){
     int e=sc.nextInt();
     sets[c].add(e);
     U.add(e);
    }
   }
   exp=sc.next();
   solve();
  }
 }

 void solve(){
  exp+='\0';
  Result r=e(0);
  debug(r.set.toArray());
  if(r.set.size()==0){
   println("NULL");
  }else{
   for(Iterator<Integer> it=r.set.iterator(); it.hasNext();){
    print(it.next()+(it.hasNext()?" ":"\n"));
   }
  }
 }

 Result e(int p){
  debug("e", p);
  Result r=f(p);
  debug(r.set.toArray(), r.p);
  for(;;){
   if(op(exp.charAt(r.p))){
    Result r2=f(r.p+1);
    switch(exp.charAt(r.p)){
    case 'u': // or
     r.set.addAll(r2.set);
     break;
    case 'i': // and
     for(int e : U){
      if(r.set.contains(e)&&r2.set.contains(e)){}else{
       r.set.remove(e);
      }
     }
     break;
    case 'd': // diff
     r.set.removeAll(r2.set);
     break;
    case 's': // sym
     for(int e : U){
      if(r.set.contains(e)&&r2.set.contains(e)){
       r.set.remove(e);
      }else if(r2.set.contains(e)){
       r.set.add(e);
      }
     }
     break;
    }
    r.p=r2.p;
   }else{
    break;
   }
  }
  return r;
 }

 boolean op(char c){
  return c=='u'||c=='i'||c=='d'||c=='s';
 }

 Result f(int p){
  debug("f", p);
  if(exp.charAt(p)=='c'){
   Result r=f(p+1);
   TreeSet<Integer> c=new TreeSet<Integer>();
   for(int e : U){
    if(!r.set.contains(e)){
     c.add(e);
    }
   }
   r.set.clear();
   r.set.addAll(c);
   return r;
  }else{
   return t(p);
  }
 }

 Result t(int p){
  debug("t", p);
  if(exp.charAt(p)=='('){
   Result r=e(p+1);
   r.p++; // skip ')'
   return r;
  }else{
   Result r=new Result(p+1);
   r.set.addAll(sets[exp.charAt(p)]);
   return r;
  }
 }

 class Result{
  int p;
  TreeSet<Integer> set;

  Result(int p){
   this.p=p;
   set=new TreeSet<Integer>();
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1162 Discrete Speed

2011-06-07T00:17:00.001+09:00

■1162 Discrete Speed

拡張ダイクストラ．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 int s, g;
 LinkedList<E>[] es;

 @SuppressWarnings("unchecked")
 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   es=new LinkedList[n];
   for(int i=0; i<n; i++){
    es[i]=new LinkedList<E>();
   }
   s=sc.nextInt()-1;
   g=sc.nextInt()-1;
   for(int i=0; i<m; i++){
    int x=sc.nextInt()-1;
    int y=sc.nextInt()-1;
    int d=sc.nextInt();
    int c=sc.nextInt();
    es[x].add(new E(y, d, c));
    es[y].add(new E(x, d, c));
   }
   solve();
  }
 }

 void solve(){
  // [前][今][前から今の速度]
  double[][][] d=new double[n][n][40];
  PriorityQueue<P> que=new PriorityQueue<P>();
  for(int j=0; j<n; j++){
   for(int i=0; i<n; i++){
    fill(d[j][i], INF);
   }
  }
  d[s][s][1]=0;
  que.offer(new P(s, s, 0, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.q][p.p][p.v]+EPS<p.d){
    continue;
   }
   for(E e : es[p.p]){
    if(p.q==e.to){
     continue;
    }
    for(int i=-1; i<=1; i++){
     if(p.v+i<=0||p.v+i>e.c){
      continue;
     }
     if(d[p.p][e.to][p.v+i]>p.d+(double)e.d/(p.v+i)+EPS){
      d[p.p][e.to][p.v+i]=p.d+(double)e.d/(p.v+i);
      que.offer(new P(p.p, e.to, p.v+i, d[p.p][e.to][p.v+i]));
     }
    }
   }
  }
  double min=INF;
  for(int i=0; i<n; i++){
   min=min(min, d[i][g][1]);
  }
  println(""+(min<INF/2?min:"unreachable"));
 }

 class E{
  int to, d, c;

  E(int to, int d, int c){
   this.to=to;
   this.d=d;
   this.c=c;
  }
 }

 class P implements Comparable<P>{
  int q, p, v;
  double d;

  P(int q, int p, int v, double d){
   this.q=q;
   this.p=p;
   this.v=v;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   if(d+EPS<p.d){
    return -1;
   }else if(d>p.d+EPS){
    return 1;
   }else{
    return 0;
   }
  }

 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1161 Verbal Arithmetic

2011-06-07T00:17:00.000+09:00

■1161 Verbal Arithmetic

非常に汚い探索による解法．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 String[] ss;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   ss=new String[n];
   for(int i=0; i<n; i++){
    ss[i]=sc.next();
   }
   solve();
  }
 }

 int size;
 int[] cs;
 int[] map;
 boolean[] used;
 int ans;

 void solve(){
  int[] a=new int[256];
  fill(a, -1);
  size=0;
  for(String s : ss){
   for(int i=0; i<s.length(); i++){
    if(a[s.charAt(i)]==-1){
     size++;
     a[s.charAt(i)]=INF;
    }
    a[s.charAt(i)]=min(a[s.charAt(i)], s.length()-1-i);
   }
  }
  cs=new int[size];
  for(int k=0, i=0; i<256; i++){
   if(a[i]>=0){
    cs[k++]=i+1000*a[i];
   }
  }
  sort(cs);

  used=new boolean[10];
  map=new int[256];
  fill(map, -1);
  ans=0;
  dfs(0);
  println(""+ans);
 }

 void dfs(int k){
  if(k==size){
   if(ok(8)){
    ans++;
   }
   return;
  }
  for(int i=0; i<10; i++){
   if(!used[i]){
    used[i]=true;
    map[cs[k]%1000]=i;
    if(ok(cs[k]/1000)){
     dfs(k+1);
    }
    map[cs[k]%1000]=-1;
    used[i]=false;
   }
  }
 }

 boolean ok(int d){
  int sum=0;
  for(int j=0; j<n; j++){
   if(map[ss[j].charAt(0)]==0&&ss[j].length()>1){
    return false;
   }
   int num=0;
   for(int i=max(0, d-ss[j].length()); i<d; i++){
    num=num*10+map[ss[j].charAt(ss[j].length()-d+i)];
   }
   if(j==n-1){
    sum-=num;
   }else{
    sum+=num;
   }
  }
  int mod=1;
  for(int i=0; i<d; i++){
   mod*=10;
  }
  return sum%mod==0;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1133 Water Tank

2011-06-07T00:12:00.000+09:00

■1133 Water Tank

実装ゲー．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import javax.swing.*;
import java.awt.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-6;

 int d;
 int n;
 int[] x, h;
 int m;
 int[] f, dv;
 int l;
 int[] p, t;

 void run(){
  d=sc.nextInt();
  for(int k=0; k<d; k++){
   n=sc.nextInt()+1;
   x=new int[n+1];
   h=new int[n+1];
   x[0]=0;
   x[n]=100;
   h[0]=h[n]=50;
   for(int i=1; i<n; i++){
    x[i]=sc.nextInt();
    h[i]=sc.nextInt();
   }
   m=sc.nextInt();
   f=new int[m];
   dv=new int[m];
   for(int i=0; i<m; i++){
    f[i]=sc.nextInt();
    dv[i]=sc.nextInt();
   }
   l=sc.nextInt();
   p=new int[l];
   t=new int[l];
   for(int i=0; i<l; i++){
    p[i]=sc.nextInt();
    t[i]=sc.nextInt();
   }
   solve();
  }
 }

 double[] y, a;
 double time;

 void solve(){
  y=new double[n];
  a=new double[n];
  for(int j=0; j<m; j++){
   for(int i=0; i<n; i++){
    if(x[i]<f[j]&&f[j]<x[i+1]){
     a[i]+=dv[j]/30.0;
    }
   }
  }
  // Visualizer v=new Visualizer();

  double[] ans=new double[l];
  fill(ans, -1);

  for(time=0;;){
   double min=INF;
   for(int i=0; i<n; i++){
    if(a[i]>EPS){
     if(y[i]+EPS<h[i]){
      min=min(min, (h[i]-y[i])*(x[i+1]-x[i])/a[i]);
     }
     if(y[i]+EPS<h[i+1]){
      min=min(min, (h[i+1]-y[i])*(x[i+1]-x[i])/a[i]);
     }
    }
   }
   if(min==INF){
    for(;;);
   }
   for(int j=0; j<l; j++){
    if(time<t[j]+EPS&&t[j]+EPS<time+min){
     for(int i=0; i<n; i++){
      if(x[i]<p[j]&&p[j]<x[i+1]){
       ans[j]=min(y[i]+(t[j]-time)*a[i]/(x[i+1]-x[i]), 50);
      }
     }
    }
   }
   boolean all50=true;
   time+=min;
   for(int i=0; i<n; i++){
    y[i]+=min*a[i]/(x[i+1]-x[i]);
    all50&=abs(y[i]-50)<EPS;
   }
   // v.repaint();
   // sleep(1000);

   if(all50){
    break;
   }
   double[] a2=new double[n];

   for(int j=0; j<n; j++){
    boolean[] bottom=new boolean[n];
    int left, right;
    for(left=j; left>=0&&y[left]+EPS>h[left]; left--);
    for(right=j; right<n&&y[right]+EPS>h[right+1]; right++);

    if(y[left]+EPS<y[j]){
     for(int i=left; i<n&&abs(y[i]-y[left])<EPS; i++){
      bottom[i]=true;
     }
    }
    if(y[right]+EPS<y[j]){
     for(int i=right; i>=0&&abs(y[i]-y[right])<EPS; i--){
      bottom[i]=true;
     }
    }
    if(abs(y[left]-y[j])<EPS&&abs(y[right]-y[j])<EPS){
     for(int i=left; i<=right; i++){
      bottom[i]=true;
     }
    }
    int sum=0;
    for(int i=0; i<n; i++){
     if(bottom[i]){
      sum+=x[i+1]-x[i];
     }
    }
    for(int i=0; i<n; i++){
     if(bottom[i]){
      a2[i]+=a[j]/sum*(x[i+1]-x[i]);
     }
    }
   }
   a=a2.clone();
  }
  for(int i=0; i<l; i++){
   println(ans[i]+EPS<0?"50.0":ans[i]+"");
  }
 }

 void sleep(long millis){
  try{
   Thread.sleep(millis);
  }catch(InterruptedException e){
   e.printStackTrace();
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }

 public class Visualizer extends JFrame{
  Visualizer(){
   setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
   setVisible(true);
   getContentPane().add(new MainPanel(), BorderLayout.CENTER);
   pack();
  }

  class MainPanel extends JPanel{
   MainPanel(){
    setPreferredSize(new Dimension(512, 512));
   }

   public void paintComponent(Graphics g){
    int width=getWidth();
    int height=getHeight();
    for(int i=0; i<n; i++){
     g.setColor(Color.BLUE);
     g.fillRect(x[i]*4, height-(int)(y[i]*4), (x[i+1]-x[i])*4,
       (int)(y[i]*4));
     g.drawString(String.format("%.4f", a[i]), x[i]*4, height/2);
    }

    for(int i=0; i<=n; i++){
     g.setColor(Color.RED);
     g.drawLine(x[i]*4, height-h[i]*4, x[i]*4, height);
    }

    g.setColor(Color.BLACK);
    g.drawString(""+time, 100, 100);
   }
  }
 }
}

IPSC 2011

2011-06-06T19:37:00.000+09:00

IPSC 2011(19:00~24:00)

ユニークな問題がたくさんありました．

■A - Against a rock play Spock

やるだけ．

■C - Candy for each guess

Easyだけなら全探索．Hannahは別に答えを変える必要な無く．最適なもの一つをひたすら用いればよい．

■D - Divide the rectangle

Easyだけ提出．

■F - Flipping coins

Easyだけ．全探索したら，本当に確率が50%を越えたので吃驚．

■M - My little puppy

わんちゃんが何か言ってくるので，それに対する正しい反応を返答する．
趣旨が分かりませんでしたが，面白かった(?)です．

■Result

6AC (A1 A2 C1 D1 F1 [M+++++])
256th

半端な順位です．

Bの解を，kinabaさんやuwiさんが画像でアップしていましたが，フラクタルな構造をしていました．思い付かなかった．

UAPC 2011

2011-06-06T19:36:00.000+09:00

UAPC 2011(6/5 13:00~18:00)

GCJ疲れが影響して，惨敗しました．

■A. It's our delight!!

やるだけ．

■K. Rearranging Seats

合計席数が偶数なら絶対に存在する．逆に奇数では絶対に存在しない．

■Result

2AC 74th
駄目駄目でした．

Google Code Jam 2011 Round2

2011-06-06T09:57:00.040+09:00

GCJ2011 Round2(6/4 23:00~01:30)

Round2に進めただけでも，進歩を感じましたが，欲を出して，Tシャツを狙いに行きました．

■A. Airport Walkways

K[m]の道がある．あなたは，普段は速度S[m/s]で歩くが，（トータルで）t[s]だけ速度R[m/s]で走ることが出来る．
さらに道のいくつかの部分には，動く歩道が設置されており，その速度があなたの歩くor走る速度に上乗せされる．
最短何秒でK[m]移動することが出来るか．

どこ走るかがポイント．答えは，動く歩道の速度+歩く速度が小さいところをより優先する．
あとは，走った時間が正確にt[s]になるように気をつける．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int caze;
 int TT;
 int x, s, r, t, n;
 int[] b, e, w;

 void run(){
  TT=sc.nextInt();
  for(caze=1; caze<=TT; caze++){
   x=sc.nextInt();
   s=sc.nextInt();
   r=sc.nextInt();
   t=sc.nextInt();
   n=sc.nextInt();
   b=new int[n];
   e=new int[n];
   w=new int[n];
   for(int i=0; i<n; i++){
    b[i]=sc.nextInt();
    e[i]=sc.nextInt();
    w[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int[] v=new int[x];
  fill(v, s);
  for(int j=0; j<n; j++){
   for(int i=b[j]; i<e[j]; i++){
    v[i]+=w[j];
   }
  }
  PriorityQueue<Integer> que=new PriorityQueue<Integer>();
  for(int i=0; i<x; i++){
   que.offer(v[i]);
  }
  double d=r-s;
  double remain=t;
  double ans=0;
  for(int i=0; i<x; i++){
   int u=que.poll();
   if(1.0/(u+d)>remain+EPS){
    double p=remain*(u+d);
    ans+=remain+(1.0-p)/u;
    remain=0;
   }else{
    remain-=1.0/(u+d);
    ans+=1.0/(u+d);
   }
  }
  answer(ans+"");
 }

 void answer(String s){
  println("Case #"+caze+": "+s);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  try{
   System.setIn(new FileInputStream(
     "D:/contest_workspace/gcj_2011_round2/dat/A-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round2/dat/A-large.out")));
  }catch(Exception e){}

  new A().run();
  System.out.flush();
  System.out.close();
 }
}

■B. Spinning Blade

全探索で解ける．
愚直に実装すると，(x₁, y₁)-(x₁, y₁)からなる長方形の重心を求めるための計算量は，O(n⁵)となり(8分間では)絶対に間に合わない．
そこで，部分和を使う．
MX1(i, j)=Σ_0≦k≦ia(k, j)k
MY1(i, j)=Σ_0≦k≦ja(i, k)k
とする．
これで，ある行 or 列に対するある範囲の質量×位置の総和がO(1)で求まるため，総計算量は、O(n⁴)になる．しかし，n=500なので，これでも厳しい．
最終的に，
MX2(i, j)=Σ_0≦k≦iMX1(i, k)
MY2(i, j)=Σ_0≦k≦jMY1(k, j)
とすると，
MX1(i, j) or MY1(i, j)は(1, 1)-(i, j)からなる長方形のxおよびy座標に関する質量×位置の総和になる．(1, 1)-(i, j)の長方形の総質量も同様にして求められるようにすれば，1クエリをO(1)で求めることが出来るため結局，総計算量がO(n³)になり間に合う．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int caze;
 int t;
 int m, n, d;
 long[][] a;

 void run(){
  t=sc.nextInt();
  for(caze=1; caze<=t; caze++){
   n=sc.nextInt();
   m=sc.nextInt();
   d=sc.nextInt();
   a=new long[n][m];
   for(int j=0; j<n; j++){
    String s=sc.next();
    for(int i=0; i<m; i++){
     a[j][i]=s.charAt(i)-'0'+d;
    }
   }
   solve();
  }
 }

 long[][] mx1, mx2, my1, my2, m1, m2;
 double gx, gy, g;

 void solve(){
  mx1=new long[n][m];
  mx2=new long[n][m];
  my1=new long[n][m];
  my2=new long[n][m];
  m1=new long[n][m];
  m2=new long[n][m];

  for(int j=0; j<n; j++){
   mx1[j][0]=a[j][0]*0;
   m1[j][0]=a[j][0];
   for(int i=1; i<m; i++){
    mx1[j][i]=mx1[j][i-1]+a[j][i]*i;
    m1[j][i]=m1[j][i-1]+a[j][i];
   }
  }

  for(int i=0; i<m; i++){
   mx2[0][i]=mx1[0][i];
   m2[0][i]=m1[0][i];
   for(int j=1; j<n; j++){
    mx2[j][i]=mx2[j-1][i]+mx1[j][i];
    m2[j][i]=m2[j-1][i]+m1[j][i];
   }
  }

  for(int i=0; i<m; i++){
   my1[0][i]=a[0][i]*0;
   for(int j=1; j<n; j++){
    my1[j][i]=my1[j-1][i]+a[j][i]*j;
   }
  }

  for(int j=0; j<n; j++){
   my2[j][0]=my1[j][0];
   for(int i=1; i<m; i++){
    my2[j][i]=my2[j][i-1]+my1[j][i];
   }
  }

  // 1クエリO(1)
  int ans=0;
  for(int y=0; y<n; y++){
   for(int x=0; x<m; x++){
    for(int w=3; x+w<=m&&y+w<=n; w++){
     calc(x, y, w);
     double mx=x+(w-1)/2.;
     double my=y+(w-1)/2.;
     if(abs(mx-gx)<EPS&&abs(my-gy)<EPS){
      ans=max(ans, w);
     }
    }
   }
  }
  answer(ans>0?(ans+""):"IMPOSSIBLE");
  debug(ans);
 }

 void calc(int x, int y, int w){
  gx=mx2[y+w-1][x+w-1];
  gy=my2[y+w-1][x+w-1];
  g=m2[y+w-1][x+w-1];
  if(x>0){
   gx-=mx2[y+w-1][x-1];
   gy-=my2[y+w-1][x-1];
   g-=m2[y+w-1][x-1];
  }
  if(y>0){
   gx-=mx2[y-1][x+w-1];
   gy-=my2[y-1][x+w-1];
   g-=m2[y-1][x+w-1];
  }
  if(x>0&&y>0){
   gx+=mx2[y-1][x-1];
   gy+=my2[y-1][x-1];
   g+=m2[y-1][x-1];
  }
  gx-=a[y][x]*x+a[y][x+w-1]*(x+w-1)+a[y+w-1][x]*x+a[y+w-1][x+w-1]*(x+w-1);
  gy-=a[y][x]*y+a[y][x+w-1]*y+a[y+w-1][x]*(y+w-1)+a[y+w-1][x+w-1]*(y+w-1);
  g-=a[y][x]+a[y][x+w-1]+a[y+w-1][x]+a[y+w-1][x+w-1];
  gx/=g;
  gy/=g;
 }

 void answer(String s){
  println("Case #"+caze+": "+s);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  try{
   System.setIn(new FileInputStream(
     "D:/contest_workspace/gcj_2011_round2/dat/B-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round2/dat/B-large.out")));
  }catch(Exception e){}

  new B().run();
  System.out.flush();
  System.out.close();
 }
}

■Result38pts. 756th念願のTシャツゲットです．もう少し頑張れば，Round3に進めたかもしれないですが，ここ最近で最高レベルに集中出来たので良かったと思います．

TopCoder SRM 508

2011-06-06T09:44:00.000+09:00

SRM 508(6/3 0:00~2:00)

■DivideAndShift(Easy)

答えをf(n,m)として，再帰的に解きました．
素因数分解をして，素数のべき乗ごとに再帰するので，制限時間には余裕で間に合います．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class DivideAndShift {
 int INF=1<<28;
 double EPS=1e-9;

 int rec(int n, int m){
  if(m==0){
   return 0;
  }
  HashMap<Integer,Integer> map=primeFactor(n);
  int res=min(m,n-m);
  for(int p:map.keySet()){
   if(p==1){
    continue;
   }
   res=min(res,rec(n/p,m%(n/p))+1);
  }
  return res;
 }

 public int getLeast(int n, int m) {
  return rec(n,m-1);
 }
 
 HashMap<Integer, Integer> primeFactor(int n){
  HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
  for(int i=2; i*i<=n; i++){
   int c=0;
   for(; n%i==0; n/=i)
    c++;
   if(c>0)
    map.put(i, c);
  }
  if(n!=1)
   map.put(n, 1);
  return map;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■Challenge Phase

撃墜無し．

■Result

o-- +0/-0
125.55pts. 406th

■Rating

1365 -> 1414
微増．目標の1500にはいつ到達できるのか…．

CodeChef May Cook-off 2011

2011-05-30T20:14:00.001+09:00

CodeChef May Cook-off 2011（1:00~3:30)

■Popular Rice Recipe

やるだけ．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  int caze=sc.nextInt();
  for(int k=0; k<caze; k++){
   int n=sc.nextInt();
   HashMap<String, Integer> map=new HashMap<String, Integer>();
   int ans=0;
   for(int i=0; i<n; i++){
    String s=sc.next();
    int p=sc.next().equals("+")?1:-1;
    if(map.containsKey(s)){
     ans-=map.get(s);
    }
    ans+=p;
    map.put(s, p);
   }
   println(""+ans);
  }
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new Main().run();
 }
}

■Distribute idlis Equally

シミュレーションなので，やるだけですが，時間内にACを取れませんでした．
原因はPriorityQueueにおいてremove()を使っていたことです．
removeを使うと，計算量は，
O((A number of times)*n*(A number of test cases))
となり，TLEしてしまうのです．
実際，removeを使わずに実装すれば，
O((A number of times)*log(n)*(A number of test cases))
となるので，余裕で間に合います．
以下，Practiceにて通ったコード．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] a;

 void run(){
  int t=sc.nextInt();
  for(int j=0; j<t; j++){
   n=sc.nextInt();
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   println(solve()+"");
  }
 }

 int solve(){
  int sum=0;
  for(int e : a){
   sum+=e;
  }
  if(sum%n!=0){
   return -1;
  }
  PriorityQueue<R> que1=new PriorityQueue<R>();
  PriorityQueue<R> que2=new PriorityQueue<R>();
  for(int e : a){
   que1.add(new R(e));
   que2.add(new R(-e));
  }
  int t;
  for(t=0;; t++){
   R p=que1.poll();
   for(;p.f;){
    p=que1.poll();
   }
   p.f=true;
   R q=que2.poll();
   for(;q.f;){
    q=que2.poll();
   }
   q.f=true;
   int min=p.v;
   int max=-q.v;
   if(min==max){
    break;
   }
   int r=(int)((max-min+1)/2.0);
   min+=r;
   max-=r;
   que1.add(new R(min));
   que2.add(new R(-min));
   que1.add(new R(max));
   que2.add(new R(-max));
  }
  return t;
 }

 class R implements Comparable<R>{
  int v;
  boolean f;
  R(int v){
   this.v=v;
  }
  @Override
  public int compareTo(R r){
   return v-r.v;
  }
 }
 
 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new Main().run();
 }
}

■Result

----o

これは酷い…．

TopCoder SRM 507

2011-05-29T17:25:00.000+09:00

SRM 507(5/29 1:00~3:00)

黄色くなれませんでした…．

■TheNumbersWithLuckyLastDigit(Easy)

6～50枚の色タイルが与えられる．その中から，6枚を選び出し，立方体に貼り付ける．
どの面についても，辺で接している面とは色が異なっていなければならない．
そのようなタイルの貼り付けたは存在するか．

最初にDFSで全探索しようと思ったのが間違いでした．
実際，色ごとのタイルの枚数を調べて場合分けすれば求まるのです（もっと完結に書くことも出来ます）．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class CubeStickers {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public String isPossible(String[] ss) {
  HashMap<String,Integer> map=new HashMap<String,Integer>();
  for(String s:ss){
   if(!map.containsKey(s)){
    map.put(s,0);
   }
   map.put(s,map.get(s)+1);
  }
  if(map.size()>=5){
   return "YES";
  }
  if(map.size()==4){
   int c=0;
   for(int e:map.values()){
    if(e>=2){
     c++;
    }
   }
   return c>=2?"YES":"NO";
  }
  if(map.size()==3){
   for(int e:map.values()){
    if(e<2){
     return "NO";
    }
   }
   return "YES";
  }
  return "NO";
 }
 
 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■CubePacking(Medium)

1辺の長さが1の立方体Ns個と，1辺の長さがLの立方体Nb個とを詰めることが出来る直方体の最小体積を求めよ．
実は結構簡単で，3辺の内の2辺を決めると，もう1辺はすぐ求まります．
ですので，2辺を全探索しつつ，体積を算出し最小値を求めれば良いのです．
本番中は解けませんでした…．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class CubePacking {
 long INF=1L<<32;
 // int INF=1<<28;
 double EPS=1e-9;

 public int getMinimumVolume(int m, int n, int len) {
  long ans=INF;
  for(long a=1;a*a*a<=INF;a++){
   for(long b=a;a*b*b<=INF;b++){
    long base=(a/len)*(b/len);
    if(base==0){
     continue;
    }
    long c=((n-1)/base+1)*len;
    long rest=m-(a*b*c-len*len*len*n);
    if(rest>0){
     c+=(rest-1)/(a*b)+1;
    }
    ans=min(ans,a*b*c);
   }
  }
  return (int)ans;
 }
 
 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■Challenge Phase

撃墜無し．SystemTestで落ちた人もRoom内には居ませんでした．

■Result

o-- +0/-0
144.37pts. 683th

■Rating

1442 -> 1365
前々回のレートに戻ってしまいました…．

Google Code Jam 2011 Round1B

2011-05-23T22:53:00.000+09:00

せめて，Bは解いておこうかと．

■B. Revenge of the Hot Dogs

ご想像のとおり二分探索．
時間tに対して，各ホットドッグ屋がD離れることが出来るかを判定する必要がある．
これは，ホットドッグ屋を左から見ていき，可能な限り左に寄せていくことで判定できる．
二分探索の上限の見積もりが甘くLargeでWAってしまった…．


import java.util.*;
import java.util.Map.Entry;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
 Scanner sc=new Scanner(System.in);

 long INF=1L<<40;
 double EPS=1e-9;

 int caze;
 int n, d;
 R[] rs;

 void run(){
  int tt=sc.nextInt();
  for(caze=1; caze<=tt; caze++){
   n=sc.nextInt();
   d=sc.nextInt();
   rs=new R[n];
   for(int i=0; i<n; i++){
    int p=sc.nextInt();
    int m=sc.nextInt();
    rs[i]=new R(p, m);
   }
   solve();
  }
 }

 void solve(){
  long left=0, right=INF;
  for(int i=0; i<n; i++){
   rs[i].p*=2;
  }
  d*=2;

  sort(rs, new Comparator<R>(){
   @Override
   public int compare(R r1, R r2){
    return r1.p-r2.p;
   }
  });

  for(int i=0; i<1000; i++){
   long mid=(left+right)/2;
   if(check(mid)){
    right=mid;
   }else{
    left=mid;
   }
  }
  debug(right, right/2.0);
  answer(String.format("%.1f", right/2.0));
 }

 boolean check(long t){
  long left=-INF;
  for(int j=0; j<n; j++){
   for(int i=0; i<rs[j].m; i++){
    if(rs[j].p+t<left+d){
     return false;
    }
    left=max(left+d, rs[j].p-t);
    // [left+d, INF) and [p-t , p+t]
   }
  }
  return true;
 }

 class R{
  int p, m;
  R(int p, int m){
   this.p=p;
   this.m=m;
  }
 }

 void answer(String s){
  println("Case #"+caze+": "+s);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  try{
   System.setIn(new FileInputStream(
     "D:/contest_workspace/gcj_2011_round1b/dat/B-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round1b/dat/B-large.out")));
  }catch(Exception e){}
  new B().run();
  System.out.flush();
  System.out.close();
 }
}

Google Code Jam 2011 Round1A

2011-05-23T22:42:00.000+09:00

遅ればせながら，報告．

■A. FreeCell Statistics

まず，下記の2条件を満たすか調べる．
・P_G=0の時は，P_D=0でないといけない．
何故なら，P_G=0ならば，全てのゲームで負けているから．
・P_G=100の時は，P_D=100でないといけない．
理由は上とほぼ同じ．

次に，勝率がP_D[%]となる（今日の）最小のゲーム数を求める．
つまり，
P_D/100*Dが整数となるような，最小のDを求める．
つまり，
D=100/gcd(P_D,100)
である．
D≦Nならば，"Possible"．
P_Gについては，試合の勝敗を調整すれば基本的に実現可能．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int caze;
 int t;
 long n, nd, ng;

 void run(){
  t=sc.nextInt();
  for(caze=1; caze<=t; caze++){
   n=sc.nextLong();
   nd=sc.nextLong();
   ng=sc.nextLong();
   solve();
  }
 }

 void solve(){
  long dd=100;
  long dg=100;
  if(ng==0&&nd>0){
   answer("Broken");
   return;
  }
  if(ng==100&&nd<100){
   answer("Broken");
   return;
  }
  long gcdD=gcd(nd, dd);
  long gcdG=gcd(ng, dg);
  debug(gcdD, gcdG);
  nd/=gcdD;
  dd/=gcdD;
  ng/=gcdG;
  dg/=gcdG;
  debug(nd, dd, ng, dg);
  long d=dd;
  if(d>n){
   answer("Broken");
   return;
  }
  answer("Possible");
 }

 void answer(String s){
  println("Case #"+caze+": "+s);
 }

 long gcd(long m, long n){
  for(; n!=0;){
   long t=m%n;
   m=n;
   n=t;
  }
  return m;
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  try{
   System.setIn(new FileInputStream(
     "D:/contest_workspace/gcj_2011_round1a/dat/A-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round1a/dat/A-large.out")));
  }catch(Exception e){}

  new A().run();
  System.out.flush();
  System.out.close();
 }
}

■B. The Killer Word

大雑把な方針は，DFSです．
まず，辞書単語を文字列の長さで分類します．
そして，リストの文字を順番に辞書全体に適用していきます．
その際，それぞれの辞書単語の開示状態は変わります．
この開示状態が等しいもので分類して，その集合で個々にDFSを行います．
集合の要素数が1になったら終わりです．
詳しい説明は，GCJ公式のContest Analysisを御覧下さい．
ちなみに，本番では解けませんでした．


import java.util.*;
import java.util.Map.Entry;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int caze;
 int m, n;
 String[] dic, lis;
 String l;

 int[] bit;
 int[] opend;
 int[][] open;
 int[] loses;

 void run(){
  int tt=sc.nextInt();
  for(caze=1; caze<=tt; caze++){
   m=sc.nextInt();
   n=sc.nextInt();
   dic=new String[m];
   lis=new String[n];
   for(int i=0; i<m; i++){
    dic[i]=sc.next();
   }
   for(int i=0; i<n; i++){
    lis[i]=sc.next();
   }
   solve();
  }
 }

 void dfs(TreeSet<Integer> set, int k, int exist){
  if(set.size()<=1||k>=26){
   return;
  }
  if(((exist>>(l.charAt(k)-'a'))&1)==0){
   dfs(set, k+1, exist);
   return;
  }
  HashMap<Integer, TreeSet<Integer>> map=new HashMap<Integer, TreeSet<Integer>>();
  HashMap<Integer, Integer> exists=new HashMap<Integer, Integer>();
  for(int i : set){
   opend[i]|=open[i][l.charAt(k)];
   if(open[i][l.charAt(k)]==0){
    loses[i]++;
   }
   if(!map.containsKey(opend[i])){
    map.put(opend[i], new TreeSet<Integer>());
    exists.put(opend[i], 0);
   }
   map.get(opend[i]).add(i);
   exists.put(opend[i], exists.get(opend[i])|bit[i]);
  }
  for(Entry<Integer, TreeSet<Integer>> entry : map.entrySet()){
   dfs(entry.getValue(), k+1, exists.get(entry.getKey()));
  }
 }

 void solve(){
  String ans="";
  for(int k=0; k<n; k++){
   TreeSet<Integer>[] sets=new TreeSet[10];
   for(int i=0; i<10; i++){
    sets[i]=new TreeSet<Integer>();
   }
   bit=new int[m];
   opend=new int[m];
   open=new int[m][256];
   loses=new int[m];
   int[] exists=new int[10];
   for(int j=0; j<m; j++){
    sets[dic[j].length()-1].add(j);
    for(int i=0; i<dic[j].length(); i++){
     bit[j]|=1<<(dic[j].charAt(i)-'a');
     open[j][dic[j].charAt(i)]|=1<<i;
     exists[dic[j].length()-1]|=1<<(dic[j].charAt(i)-'a');
    }
   }
   l=lis[k];
   for(int i=0; i<10; i++){
    dfs(sets[i], 0, exists[i]);
   }
   int max=-1;
   for(int i=0; i<m; i++){
    max=max(max, loses[i]);
   }
   for(int i=0; i<m; i++){
    if(loses[i]==max){
     ans+=dic[i]+(k==n-1?"":" ");
     break;
    }
   }
  }
  answer(ans);
  debug(ans);
 }

 void answer(String s){
  println("Case #"+caze+": "+s);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  try{
   System.setIn(new FileInputStream(
     "D:/contest_workspace/gcj_2011_round1a/dat/B-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round1a/dat/B-large.out")));
  }catch(Exception e){}
  new B().run();
  System.out.flush();
  System.out.close();
 }
}

■Result

oo----
20pts. 870th
どうにかRound2へ進出出来ます．

専門書を読む #20

2011-05-23T00:24:00.003+09:00

■コンピュータの数学5 二項係数pp.51-59

TopCoder SRM 504.5

2011-05-18T02:50:00.000+09:00

SRM 504.5(5/18 0:00~2:00)

多忙でしたが，折角なので参加することにしました．

■TheNumbersWithLuckyLastDigit(Easy)

実際にいくつか試してみると，10で割った余りで"ほぼ"決まることが分かります．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class TheNumbersWithLuckyLastDigit {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int find(int n) {
  int[] a={5,2,3,5,1,3,4,1,2,4};
  boolean[] out=new boolean[20];
  out[1]=out[2]=out[3]=out[5]=out[6]=out[9]=out[10]=out[13]=true;
  if(n<20&&out[n]){
   return -1;
  }else{
   return a[n%10];
  }
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■TheJackpotDivOne(Medium)

本番ではdoubleを使っていたので，アンダーフロー(?)による精度落ちで撃墜されました．下が修正コード．JavaならばBigIntegerが使えます．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class TheJackpotDivOne {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public long[] find(long[] a, long m) {
  int n=a.length;
  for(;;){
   int k=n-1;
   BigInteger ave=BigInteger.ZERO;
   boolean same=true;
   for(int i=n-1;i>=0;i--){
    if(a[i]<=a[k]){
     k=i;
    }
    same&=a[0]==a[i];
    ave=ave.add(BigInteger.valueOf(a[i]));
   }
   if(same){
    break;
   }
   long x=ave.divide(BigInteger.valueOf(n)).longValue()-a[k]+1;
   if(m>=x){
    a[k]+=x;
    m-=x;
   }else{
    a[k]+=m;
    sort(a);
    return a;
   }
  }
  for(int i=0;i<n;i++){
   a[i]+=m/n;
   if(i<m%n){
    a[i]++;
   }
  }
  sort(a);
  return a;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■Challenge Phase

Easyで一人撃墜．

■Result

ox- +1/-0
241.3pts. 299th
前回の教訓を生かし，1撃墜に止めました．

■Rating

1360 -> 1442
黄色くなれるか…?!

TCO11 Algo Qual1

2011-05-15T03:13:00.002+09:00

TCO11 Algo Qual1(5/15 1:00~3:00)

■MinimumLiars(Easy)

考えられる全ケースを試すだけ．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class MinimumLiars {
 int INF=1<<28;
 double EPS=1e-9;

 public int getMinimum(int[] a) {
  int n=a.length;
  for(int j=0;j<=n;j++){
   int s=0;
   for(int i=0;i<n;i++){
    if(a[i]>j){
     s++;
    }
   }
   if(j==s){
    return j;
   }
  }
  return -1;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args) {
  // MinimumLiars temp = new MinimumLiars();
  // System.out.println(temp.getMinimum(int[] claim));
 }
}

■FoxListeningToMusic(Medium)

O(Tn)じゃないとSystem Testで落ちます．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class FoxListeningToMusic {
 int INF=1<<28;
 double EPS=1e-9;

 public double[] getProbabilities(int[] a, int t) {
  int n=a.length;
  double[] dp=new double[t+1];
  dp[0]=1./n;
  for(int k=0;k<t;k++){
   double[] d=new double[n];
   for(int i=0;i<n;i++){
    d[i]+=dp[k]/n;
   }
   for(int i=0;i<n;i++){
    if(k+a[i]<=t){
     dp[k+a[i]]+=d[i];
    }
   }
  }
  // debug(dp);
  double[] res=new double[n];
  for(int i=0;i<n;i++){
   for(int j=t;j>t-a[i]&&j>=0;j--){
    res[i]+=dp[j];
   }
  }
  return res;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args) {
 }
}

■Challenge Phase

Mediumにて，O(Tn²)の人を狙ったのですが，3回もミスしてしまいました．

■Result

○○× +1 -3
478.98pts. 332th

■Rating

1279 -> 1360
600位以内なので，次のラウンドへ．Round1も残りたいですね．

UTPC 2011(東京大学プログラミングコンテスト)

2011-05-14T19:01:00.001+09:00

UTPC 2011(05/14 12:00~17:00)

久し振りの投稿．

■A プログラミングコンテスト


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;

 void run(){
  n=sc.nextInt();
  m=sc.nextInt();
  int max=0;
  for(int j=0; j<n; j++){
   int a=0;
   for(int i=0; i<m; i++){
    a+=sc.nextInt();
   }
   max=max(max, a);
  }
  println(""+max);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

■B (iwi)


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  String s=sc.next();
  int ans=0;
  if(s.length()%2==1){
   if(!Character.isLetter(s.charAt(s.length()/2))){
    ans++;
   }
  }
  boolean[][] check=new boolean[256][256];
  check['i']['i']=true;
  check['w']['w']=true;
  check['('][')']=true;
  check[')']['(']=true;
  for(int i=0; i<s.length()/2; i++){
   if(!check[s.charAt(i)][s.charAt(s.length()-1-i)]){
    ans++;
   }
  }
  println(""+ans);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

■C [[iwi]]

全探索による解法．LCSのような解法もあるようです．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  String ss=sc.next();
  boolean[][] check=new boolean[256][256];
  check['('][')']=true;
  check[')']['(']=true;
  check['{']['}']=true;
  check['}']['{']=true;
  check['['][']']=true;
  check[']']['[']=true;
  int k=ss.indexOf("iwi");
  int m=k;
  int n=ss.length()-(k+3);
  String s=ss.substring(0, k);
  String t=ss.substring(k+3, ss.length());
  // debug(m, n);
  // debug(s, t);
  int max=0;
  for(int sup1=0; sup1<1<<m; sup1++){
   String s1="";
   for(int i=0; i<m; i++){
    if(((sup1>>i)&1)==1){
     s1+=s.charAt(i);
    }
   }
   for(int sup2=0; sup2<1<<n; sup2++){
    if(Integer.bitCount(sup1)==Integer.bitCount(sup2)){
     String s2="";
     for(int j=0; j<n; j++){
      if(((sup2>>j)&1)==1){
       s2+=t.charAt(j);
      }
     }
     boolean f=true;
     for(int i=0; i<s1.length(); i++){
      f&=check[s1.charAt(i)][s2.charAt(s2.length()-1-i)];
     }
     if(f){
      // debug(s1, s2);
      max=max(max, s1.length()+3+s2.length());
     }
    }
   }
  }
  println(max+"");
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

■D 停止問題

BFSによる解法．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 char[][] cs;

 void run(){
  n=sc.nextInt();
  m=sc.nextInt();
  cs=new char[n][m];
  for(int j=0; j<n; j++){
   String s=sc.next();
   for(int i=0; i<m; i++){
    cs[j][i]=s.charAt(i);
   }
  }

  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};
  LinkedList<P> que=new LinkedList<P>();
  boolean[][][][] visited=new boolean[m][n][16][4];

  que.offer(new P(0, 0, 0, 3));
  visited[0][0][0][3]=true;

  for(; !que.isEmpty();){
   P p=que.poll();
   // debug(p.x, p.y, p.mem, p.dir);
   if(cs[p.y][p.x]=='?'){
    for(int i=0; i<4; i++){
     P q=new P(p.x, p.y, p.mem, p.dir);
     q.dir=i;
     q.x=(q.x+dx[q.dir]+m)%m;
     q.y=(q.y+dy[q.dir]+n)%n;
     if(!visited[q.x][q.y][q.mem][q.dir]){
      que.offer(q);
      visited[q.x][q.y][q.mem][q.dir]=true;
     }
    }
    continue;
   }
   P q=new P(p.x, p.y, p.mem, p.dir);
   switch(cs[p.y][p.x]){
   case '<':
    q.dir=2;
    break;
   case '>':
    q.dir=3;
    break;
   case '^':
    q.dir=0;
    break;
   case 'v':
    q.dir=1;
    break;
   case '_':
    if(q.mem==0){
     q.dir=3;
    }else{
     q.dir=2;
    }
    break;
   case '|':
    if(q.mem==0){
     q.dir=1;
    }else{
     q.dir=0;
    }
    break;
   case '.':
    break;
   case '@':
    println("YES");
    return;
   case '+':
    q.mem=(q.mem+1)%16;
    break;
   case '-':
    q.mem=(q.mem+15)%16;
    break;
   }
   if(Character.isDigit(cs[p.y][p.x])){
    q.mem=cs[p.y][p.x]-'0';
   }
   q.x=(q.x+dx[q.dir]+m)%m;
   q.y=(q.y+dy[q.dir]+n)%n;
   if(!visited[q.x][q.y][q.mem][q.dir]){
    que.offer(q);
    visited[q.x][q.y][q.mem][q.dir]=true;
   }
  }
  println("NO");
 }

 class P{
  int x, y;
  int mem;
  int dir;

  P(int x, int y, int mem, int dir){
   this.x=x;
   this.y=y;
   this.mem=mem;
   this.dir=dir;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

■E ファーストアクセプタンス

System.arraycopyを何故か忘れていたため，競技中はWAでした．下は競技終了後のコード．ちなみに，bでソートすればいいので，aは関係ないです．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 long INF=1L<<48;
 double EPS=1e-9;

 int n;
 R[] rs;

 void run(){
  n=sc.nextInt();
  rs=new R[n];
  for(int i=0; i<n; i++){
   int a=sc.nextInt();
   int b=sc.nextInt();
   rs[i]=new R(a, b);
  }

  sort(rs, new Comparator<R>(){
   @Override
   public int compare(R r1, R r2){
    if(r1.b!=r2.b){
     return r1.b-r2.b;
    }else{
     return r2.a-r1.a;
    }
   }
  });

  long[][] dp=new long[n+1][n+1];
  fill(dp[0], INF);
  dp[0][0]=0;
  for(int j=1; j<=n; j++){
   System.arraycopy(dp[j-1], 0, dp[j], 0, n+1);
   for(int i=0; i<j; i++){
    long t=dp[j-1][i]+rs[j-1].a;
    if(t<=rs[j-1].b){
     dp[j][i+1]=min(dp[j][i+1], t);
    }
   }
   // debug(dp[j]);
  }
  for(int i=n; i>=0; i--){
   if(dp[n][i]<INF){
    println(i+"");
    break;
   }
  }
 }

 class R{
  int a, b;
  R(int a, int b){
   this.a=a;
   this.b=b;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

■Result

400pt. 77th

途中で離脱してしまったので，簡単な問題しか解けず残念．
Eは解法が合っていましたし，A~Dも1時間程度で解けていたので，わずかながらに成長しているようです．
それにしても，沢山の強豪がいますね．今年のICPCが心配です．

今月の〇〇(2011年4月)

2011-04-30T18:23:00.000+09:00

■Aizu Online Judge

Solved:254/46th
Rating:203.75/50th
Ratingは目標通り200に到達しましたが，そのせいでSolvedの順位が下がってしまいました．5月は，Solvedの順位を30位以上，願わくば20位以上にしたいです．

■TopCoder/Codeforces

Codeforcesは，一旦Div.2に落ちたものの，再びDiv.1に復帰しました．
TopCoderは，Rating微増．

Aizu Online Judge 1202 Mobile Phone Coverage

2011-04-30T18:15:00.002+09:00

■1202 Mobile Phone Coverage

面倒な問題．下の画像のような感じに分割した．区間をマージする処理が面倒だった．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 R[] rs;
 int caze;

 void run(){
  for(caze=1;; caze++){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   rs=new R[n];
   for(int i=0; i<n; i++){
    double x=sc.nextDouble();
    double y=sc.nextDouble();
    double r=sc.nextDouble();
    rs[i]=new R(x-r, y-r, x+r, y+r);
   }
   solve();
  }
 }

 void solve(){
  TreeSet<Double> setX=new TreeSet<Double>();
  for(int i=0; i<n; i++){
   setX.add(rs[i].x1);
   setX.add(rs[i].x2);
  }
  Double[] xs=setX.toArray(new Double[0]);
  sort(xs);
  int m=xs.length;
  @SuppressWarnings("unchecked")
  TreeSet<R>[] setR=new TreeSet[m];
  for(int i=0; i<m; i++){
   setR[i]=new TreeSet<R>();
  }

  for(int j=0; j<m-1; j++){
   for(int i=0; i<n; i++){
    if(rs[i].x1<xs[j]+EPS&&xs[j]+EPS<rs[i].x2){
     setR[j].add(rs[i]);
    }
   }
  }

  double sum=0;
  for(int k=0; k<m-1; k++){
   LinkedList<Double> seg=new LinkedList<Double>();
   for(R r : setR[k]){
    if(abs(r.y1-r.y2)<EPS){
     continue;
    }
    int i=seg.size(), j=seg.size();
    for(int p=seg.size()-1; p>=0; p--){
     double y=seg.get(p);
     if(y+EPS>r.y2){
      j=p;
     }
     if(y+EPS>r.y1){
      i=p;
     }
    }
    for(int p=i; p<j; p++){
     seg.remove(i);
    }
    if(j%2==0){
     seg.add(i, r.y2);
    }
    if(i%2==0){
     seg.add(i, r.y1);
    }
   }
   double len=0;
   for(int i=0; i<seg.size(); i+=2){
    len+=seg.get(i+1)-seg.get(i);
   }
   sum+=len*(xs[k+1]-xs[k]);
  }
  println(String.format("%d %.2f", caze, sum+EPS));
 }

 class R implements Comparable<R>{
  double x1, y1, x2, y2;

  R(double x1, double y1, double x2, double y2){
   this.x1=x1;
   this.y1=y1;
   this.x2=x2;
   this.y2=y2;
  }

  @Override
  public int compareTo(R arg0){
   if(y1-y2+EPS<0){
    return -1;
   }else if(y1-y2>0+EPS){
    return 1;
   }else if(x1-x2+EPS<0){
    return -1;
   }else if(x1-x2>0+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1221 Numoeba

2011-04-30T18:03:00.002+09:00

■1221 Numoeba

制限時間・メモリ共に余裕があるので，あとは気合で書くだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int k;
 int m;
 int mod=12345678;
 boolean[] visited=new boolean[10000];

 void run(){
  for(;;){
   k=sc.nextInt();
   if(k==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  Cell leader=new Cell(k);
  m=0;
  int maxNum=1;
  for(int k=1;; k++){
   LinkedList<Cell> que=new LinkedList<Cell>();
   que.offer(leader);
   fill(visited, false);
   visited[leader.v]=true;

   for(; !que.isEmpty();){
    Cell c=que.poll();
    int n=c.n*3+1;
    for(; n%2==0;){
     n/=2;
    }
    n%=mod;
    c.candidate=n>c.n&&(c.size()==0||(c.size()==1&&c!=leader));
    c.n=n;
    if(c.n==1){
     if(c==leader){
      println(k+" "+maxNum);
      return;
     }
     Cell par=null;
     for(Cell d : c){
      if(visited[d.v]){
       par=d;
      }
      d.remove(c);
     }
     c.remove(par);
     if(c.size()==1){
      Cell child=c.getFirst();
      par.add(child);
      child.add(par);
      que.offer(child);
      visited[child.v]=true;
     }
    }else{
     for(Cell d : c){
      if(!visited[d.v]){
       que.offer(d);
       visited[d.v]=true;
      }
     }
    }
   }
   fill(visited, false);
   Cell newLeader=new Cell(0);
   boolean overlap=false;
   int num=0;

   que.offer(leader);
   visited[leader.v]=true;
   for(; !que.isEmpty();){
    Cell c=que.poll();
    num++;
    for(Cell d : c){
     if(!visited[d.v]){
      que.offer(d);
      visited[d.v]=true;
     }
    }
    if(c.n>newLeader.n){
     newLeader=c;
     overlap=false;
    }else if(c.n==newLeader.n){
     overlap=true;
    }
    if(c.candidate&&((c.size()==1&&c!=leader)||c.size()==0)){
     Cell d=new Cell(((c.n+1)/2)|1);
     if(d.n!=1){
      c.add(d);
      d.add(c);
      num++;
     }
    }
   }

   if(!overlap){
    leader=newLeader;
    Cell c=new Cell(((leader.n+1)/2-1)|1);
    if(c.n!=1){
     leader.add(c);
     c.add(leader);
     num++;
    }
   }
   maxNum=max(maxNum, num);
  }
 }

 void dfs(Cell leader){
  fill(visited, false);
  dfs(leader, "");
 }

 void dfs(Cell c, String tab){
  debug(tab, c.n, c.size(), c.v);
  visited[c.v]=true;
  for(Cell d : c){
   if(!visited[d.v]){
    dfs(d, tab+"  ");
   }
  }
 }

 class Cell extends LinkedList<Cell>{
  int n, v;
  boolean candidate;

  Cell(int n){
   this.n=n;
   this.v=m++;
  }

  @Override
  public int hashCode(){
   return v;
  }

  @Override
  public boolean equals(Object o){
   return hashCode()==((Cell)o).hashCode();
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1215 Co-occurrence Search

2011-04-30T18:03:00.001+09:00

■1215 Co-occurrence Search

しゃくとり法で解くことが出来る．入力がややこしく，無限ループによるTLEを連発してしまった．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 char[] s, key;

 void run(){
  for(;;){
   StringBuffer lines=new StringBuffer();
   for(;;){
    String line=sc.nextLine();
    if(line.equals("")){
     break;
    }
    lines.append(line);
   }
   s=lines.toString().toCharArray();
   key=sc.nextLine().toCharArray();
   solve();
   if(sc.hasNext()){
    sc.nextLine();
   }else{
    break;
   }
  }
  System.out.flush();
 }

 void solve(){
  int i=0, j=0;
  int num=0;
  int n=s.length;

  int min=INF;
  int cMin=0, iMin=0, jMin=0;

  int nKey=0;
  boolean[] isKey=new boolean[256];
  for(char c : key){
   isKey[c]=true;
  }
  for(boolean b : isKey){
   nKey+=b?1:0;
  }
  int[] count=new int[256];

  for(;;){
   for(; j<n&&num<nKey; j++){
    if(isKey[s[j]]&&count[s[j]]++==0){
     num++;
    }
   }

   if(num<nKey){
    break;
   }

   if(j-i<min){
    iMin=i;
    jMin=j;
    min=j-i;
    cMin=1;
   }else if(j-i==min){
    cMin++;
   }

   if(isKey[s[i]]&&--count[s[i]]==0){
    num--;
   }
   i++;
  }

  println(cMin+"\n");
  if(cMin>0){
   String ans=new String(s, iMin, jMin-iMin);
   for(int k=0; k<(ans.length()-1)/72+1; k++){
    println(ans.substring(k*72, min((k+1)*72, ans.length())));
   }
   println("");
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1226 Fishnet

2011-04-30T18:03:00.000+09:00

■1226 Fishnet

全通り試す．面積はヘロンの公式を使えば簡単．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 P[] a, b, c, d;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   n+=2;
   a=new P[n];
   b=new P[n];
   c=new P[n];
   d=new P[n];
   a[0]=new P(0, 0);
   b[0]=new P(0, 1);
   c[0]=new P(0, 0);
   d[0]=new P(1, 0);
   for(int i=1; i<n-1; i++)
    a[i]=new P(sc.nextDouble(), 0);
   for(int i=1; i<n-1; i++)
    b[i]=new P(sc.nextDouble(), 1);
   for(int i=1; i<n-1; i++)
    c[i]=new P(0, sc.nextDouble());
   for(int i=1; i<n-1; i++)
    d[i]=new P(1, sc.nextDouble());
   a[n-1]=new P(1, 0);
   b[n-1]=new P(1, 1);
   c[n-1]=new P(0, 1);
   d[n-1]=new P(1, 1);
   solve();
  }
 }

 void solve(){
  double ans=0;
  for(int j=0; j<n-1; j++){
   for(int i=0; i<n-1; i++){
    P p1=isLL(a[i], b[i], c[j], d[j]);
    P p2=isLL(a[i+1], b[i+1], c[j], d[j]);
    P p3=isLL(a[i+1], b[i+1], c[j+1], d[j+1]);
    P p4=isLL(a[i], b[i], c[j+1], d[j+1]);
    ans=max(ans, area(p1, p2, p3)+area(p3, p4, p1));
   }
  }
  println(String.format("%.6f", ans+EPS));
 }

 double area(P p1, P p2, P p3){
  double a=p1.sub(p2).abs();
  double b=p2.sub(p3).abs();
  double c=p3.sub(p1).abs();
  double s=(a+b+c)/2;
  return Math.sqrt(s*(s-a)*(s-b)*(s-c));
 }

 // 直線と直線の交点
 P isLL(P p1, P p2, P q1, P q2){
  double d=q2.sub(q1).det(p2.sub(p1));
  if(abs(d)<EPS)
   return null;
  return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));
 }

 class P{
  double x, y;

  P(){
   this(0, 0);
  }

  P(double x, double y){
   this.x=x;
   this.y=y;
  }

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }

  @Override
  public String toString(){
   return "("+x+", "+y+")";
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1217 Family Tree

2011-04-21T22:53:00.000+09:00

■ 1217 Family Tree

入力の解析が少し面倒．クエリに対する判定は，ある人の親さえ分かれば非常に簡単に出来る．
下記のコードではchildrenも記録していたけど全く必要なかった．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 HashMap<String, String> parent;
 HashMap<String, LinkedList<String>> children;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   parent=new HashMap<String, String>();
   children=new HashMap<String, LinkedList<String>>();
   sc.nextLine();
   String p="", r=""; // 親, 1つ前
   children.put(p, new LinkedList<String>());
   int x=-1;
   for(int j=0; j<n; j++){
    String s=sc.nextLine();
    int y=s.length()-s.replaceAll(" ", "").length();
    s=s.replaceAll(" ", "");
    // debug(s, r, p);
    if(y>x){
     p=r;
    }else if(y<x){
     for(int i=y; i<x; i++){
      p=parent.get(p);
     }
    }
    parent.put(s, p);
    children.get(p).add(s);
    children.put(s, new LinkedList<String>());
    x=y;
    r=s;
   }
   // dfs("", "");
   for(int i=0; i<m; i++){
    String s=sc.next();
    sc.next();
    sc.next();
    char c=sc.next().charAt(0);
    sc.next();
    String t=sc.next();
    t=t.substring(0, t.length()-1);
    boolean f=false;
    switch(c){
    case 'c':
     f=parent.containsKey(s)&&parent.get(s).equals(t);
     break;
    case 'p':
     f=parent.containsKey(t)&&parent.get(t).equals(s);
     break;
    case 's':
     f=parent.containsKey(s)&&parent.containsKey(t)
       &&parent.get(s).equals(parent.get(t));
     break;
    case 'd':
     for(s=parent.get(s); s!=null; s=parent.get(s)){
      f|=s.equals(t);
     }
     break;
    case 'a':
     for(t=parent.get(t); t!=null; t=parent.get(t)){
      f|=t.equals(s);
     }
     break;
    }
    println(f?"True":"False");
   }
   println("");
  }
 }

 void dfs(String s, String tab){
  for(String t : children.get(s)){
   debug(tab, t, parent.get(t));
   dfs(t, tab+"\t");
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Codeforces Beta Round #69 (Div. 2 Only)

2011-04-20T23:15:00.000+09:00

Codeforces Beta Round #69 (Div. 2 Only)

Div. 1復帰が目標でした．

A. Panoramixs Prediction

値が小さいので愚直に一つずつ試行．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;

 void run(){
  m=sc.nextInt();
  n=sc.nextInt();
  boolean f=true;
  for(int i=m+1; i<n; i++){
   f&=!isP(i);
  }
  f&=isP(n);
  println(f?"YES":"NO");
 }

 boolean isP(int n){
  for(int i=2; i*i<=n; i++){
   if(n%i==0){
    return false;
   }
  }
  return n!=1;
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new A().run();
 }
}

B. Depression

%12を忘れないように気をつけるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  String[] ss=sc.next().split(":");
  double h=Integer.parseInt(ss[0]);
  double m=Integer.parseInt(ss[1]);
  h=(h%12)/12.0*360;
  m=m/60.0*360;
  h=(h+m/12)%360;
  println(h+" "+m);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new B().run();
 }
}

C. Heroes

全探索で解くことが出来るが，ちょっとしたミスをしたためSystem Test落ち．下は修正版．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class C{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, a, b, c;
 int[] p, q;
 HashMap<String, Integer> map;

 void run(){
  int m=7;

  map=new HashMap<String, Integer>();
  map.put("Anka", 0);
  map.put("Chapay", 1);
  map.put("Cleo", 2);
  map.put("Troll", 3);
  map.put("Dracul", 4);
  map.put("Snowy", 5);
  map.put("Hexadecimal", 6);

  n=sc.nextInt();
  p=new int[n];
  q=new int[n];
  for(int i=0; i<n; i++){
   p[i]=map.get(sc.next());
   sc.next();
   q[i]=map.get(sc.next());
  }
  a=sc.nextInt();
  b=sc.nextInt();
  c=sc.nextInt();

  long dmin=1L<<32;
  int lmax=0;
  for(int k=1; k<1<<m; k++){
   for(int j=1; j<1<<m; j++){
    int i=((1<<m)-1)&~(k^j);
    if((k^j)==(k|j)&&i>0){
     int x=a/Integer.bitCount(i);
     int y=b/Integer.bitCount(j);
     int z=c/Integer.bitCount(k);
     int d=max(abs(x-y), max(abs(y-z), abs(z-x)));

     int l=0;
     for(int e=0; e<n; e++){
      if(((k>>p[e])&1)!=0&&((k>>q[e])&1)!=0)
       l++;
      else if(((j>>p[e])&1)!=0&&((j>>q[e])&1)!=0)
       l++;
      else if(((i>>p[e])&1)!=0&&((i>>q[e])&1)!=0)
       l++;
     }
     if(d<dmin){
      dmin=d;
      lmax=l;
     }else if(d==dmin){
      lmax=max(lmax, l);
     }
    }
   }
  }
  println(dmin+" "+lmax);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new C().run();
 }
}

D. Falling Anvils

x²+√px+q=0は，p≧4qならば実解が存在する．
つまり，(p,q)∈[0,a]×[-b,b]の長方形内においてp≧4qを満たす領域の面積を計算し，それを長方形の面積で割った値が，実解が存在する確率．a=0やb=0の時は，0除算を避けるために例外処理を追加する必要がある．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class D{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int t;
 double a, b;

 void run(){
  t=sc.nextInt();
  for(int i=0; i<t; i++){
   a=sc.nextInt();
   b=sc.nextInt();
   double area;
   if(4*b<a+EPS){
    area=2*b*(a-b);
   }else{
    area=a*(b+a/8);
   }
   if(abs(b)<EPS){
    println("1");
   }else if(abs(a)<EPS){
    println("0.5");
   }else{
    println(area/(2*a*b)+"");
   }
  }
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new D().run();
 }
}

ooxo- 2726p 46位
1624 -> 1654
復帰完了…というところです．

Aizu Online Judge 1218 Push!!

2011-04-20T21:40:00.000+09:00

■1218 Push!!

人の座標と荷物の座標を状態とし，距離を荷物を押した回数としたダイクストラで解ける．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int[][] a;
 int mx0, my0, cx0, cy0, gx, gy;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
     if(a[j][i]==2){
      cx0=i;
      cy0=j;
      a[j][i]=0;
     }else if(a[j][i]==3){
      gx=i;
      gy=j;
      a[j][i]=0;
     }else if(a[j][i]==4){
      mx0=i;
      my0=j;
      a[j][i]=0;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  PriorityQueue<P> que=new PriorityQueue<P>();
  boolean[][][][] visited=new boolean[m][n][m][n];
  int[][][][] d=new int[m][n][m][n];

  for(int k=0; k<m; k++){
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     fill(d[k][j][i], INF);
    }
   }
  }

  que.add(new P(mx0, my0, cx0, cy0));
  visited[mx0][my0][cx0][cy0]=true;
  d[mx0][my0][cx0][cy0]=0;

  int[] dx={0, 0, -1, 1};
  int[] dy={1, -1, 0, 0};

  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.mx][p.my][p.cx][p.cy]<p.d){
    continue;
   }
   for(int i=0; i<4; i++){
    P q=new P(p.mx+dx[i], p.my+dy[i], p.cx, p.cy);
    int push=0;
    // 人が画面外or移動不可
    if(q.mx<0||q.mx>=m||q.my<0||q.my>=n||a[q.my][q.mx]==1){
     continue;
    }
    // 人の移動先がブロック
    if(q.mx==q.cx&&q.my==q.cy){
     q.cx+=dx[i];
     q.cy+=dy[i];
     push=1;
    }
    // ブロックが画面外or配置不可
    if(q.cx<0||q.cx>=m||q.cy<0||q.cy>=n||a[q.cy][q.cx]==1){
     continue;
    }
    // 訪問していない
    if(!visited[q.mx][q.my][q.cx][q.cy]){
     q.d=d[q.mx][q.my][q.cx][q.cy]=d[p.mx][p.my][p.cx][p.cy]
       +push;
     visited[q.mx][q.my][q.cx][q.cy]=true;
     que.offer(q);
    }
   }
  }

  int min=INF;
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    min=min(min, d[i][j][gx][gy]);
   }
  }

  println(""+(min==INF?-1:min));

 }

 class P implements Comparable<P>{
  int mx, my, cx, cy;
  int d;

  P(int mx, int my, int cx, int cy){
   this.mx=mx;
   this.my=my;
   this.cx=cx;
   this.cy=cy;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1209 Square Coins

2011-04-20T21:39:00.000+09:00

■1209 Square Coins

dp[i]を支払う金額がiの時のコインの組み合わせの数とする．
コインa[0],…,a[j-1]までのdp[i]が求められていれば，a[j]についてのdp[i]を以下の式で求めていけばよい．
dp[i]+=dp[i-a[j]]
初期値は，
dp[0]=1
dp[i]=0 (i≠0)

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  int n=17;
  int[] a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=(i+1)*(i+1);
  }
  int max=300;
  int[] dp=new int[max];
  dp[0]=1;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<max; i++){
    dp[i]+=dp[i-a[j]];
   }
  }
  for(;;){
   int k=sc.nextInt();
   if(k==0){
    break;
   }
   println(""+dp[k]);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1209 Square Coins

2011-04-19T22:03:00.000+09:00

■1209 Square Coins

dp[i]を支払う金額がiの時のコインの組み合わせの数とする．
コインa[0],…,a[j-1]までのdp[i]が求められていれば，a[j]についてのdp[i]を以下の式で更新すれば良い．
dp[i]+=dp[i-a[j]]

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  int n=17;
  int[] a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=(i+1)*(i+1);
  }
  int max=300;
  int[] dp=new int[max];
  dp[0]=1;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<max; i++){
    dp[i]+=dp[i-a[j]];
   }
  }
  for(;;){
   int k=sc.nextInt();
   if(k==0){
    break;
   }
   println(""+dp[k]);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

TopCoder Member SRM 503 Div1 Medium KingdomXCitiesandVillages

2011-04-19T00:47:00.000+09:00

■KingdomXCitiesandVillages

問題・解説は，Match Editorial Archiveを参考に．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class KingdomXCitiesandVillages {
 int INF=1<<28;
 double EPS=1e-9;

 int m, n;

 public double determineLength(int[] cx, int[] cy, int[] vx, int[] vy) {
  m=cx.length;
  n=vx.length;
  double sum=0;
  for(int j=0;j<n;j++){
   LinkedList<R> list=new LinkedList<R>();
   for(int i=0;i<n;i++){
    if(i!=j){
     list.add(new R(Math.hypot(vx[j]-vx[i], vy[j]-vy[i]), false));
    }
   }
   for(int i=0;i<m;i++){
    list.add(new R(Math.hypot(vx[j]-cx[i], vy[j]-cy[i]), true));
   }
   R[] rs=list.toArray(new R[0]);
   Arrays.sort(rs);
   for(int i=0;i<rs.length;i++){
    if(rs[i].isCity){
     sum+=rs[i].d/(i+1);
     break;
    }else{
     sum+=rs[i].d/(i+1)/(i+2);
    }
   }
  }
  return sum;
 }

 class R implements Comparable<R>{
  double d;
  boolean isCity;
  R(double d, boolean isCity){
   this.d=d;
   this.isCity=isCity;
  }
  public int compareTo(R r){
   if(d-r.d+EPS<0){
    return -1;
   }else if(d-r.d>0+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

Aizu Online Judge 1216 Lost in Space

2011-04-18T21:06:00.000+09:00

■1216 Lost in Space

全探索で間に合う．
元の三角形の辺の長さをd[i]とする．
与えられた座標軍からある3点を選び，それぞれの辺の長さをe[i]とする．
この時，それぞれの辺の比r[i]は，
r[i]=e[i]/d[i]
となる．
それぞれの比の誤差が，0.1%以上になることは無い，というのだから，任意のi，jに対して，
|r[i]-r[j]|/r[i] < 0.1
となる．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 double[] d;
 P[] ps;
 int n;

 void run(){
  d=new double[3];
  for(int t=sc.nextInt(); t>0; t--){
   for(int i=0; i<3; i++){
    d[i]=sc.nextDouble();
   }
   n=sc.nextInt();
   ps=new P[n];
   for(int i=0; i<n; i++){
    double x=sc.nextDouble();
    double y=sc.nextDouble();
    double z=sc.nextDouble();
    ps[i]=new P(x, y, z);
   }
   solve();
  }
 }

 void solve(){
  double[] len={0, 0, 0};
  for(int c=0; c<n; c++){
   for(int b=0; b<n; b++){
    if(b==c){
     continue;
    }
    for(int a=0; a<n; a++){
     if(a==b||a==c){
      continue;
     }
     len[0]=ps[b].sub(ps[c]).abs()/d[0];
     len[1]=ps[c].sub(ps[a]).abs()/d[1];
     len[2]=ps[a].sub(ps[b]).abs()/d[2];
     boolean error=false;
     for(int i=0; i<3; i++){
      int p=i;
      int q=(i+1)%3;
      error|=abs(len[p]-len[q])/len[p]+EPS>=0.001;
     }
     if(!error){
      println((a+1)+" "+(b+1)+" "+(c+1));
     }
    }
   }
  }
 }

 class P{
  double x, y, z;

  P(){
   this(0, 0, 0);
  }

  P(double x, double y, double z){
   this.x=x;
   this.y=y;
   this.z=z;
  }

  P add(P p){
   return new P(x+p.x, y+p.y, z+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y, z-p.z);
  }

  P mul(double m){
   return new P(x*m, y*m, z*m);
  }

  P div(double d){
   return new P(x/d, y/d, z/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y+z*z;
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y+z*p.y;
  }

  // outer product
  P det(P p){
   return new P(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);
  }

  @Override
  public String toString(){
   return x+", "+y+", "+z;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1214 Walking Ant

2011-04-18T21:05:00.001+09:00

■1214 Walking Ant

BFSで解ける．但し状態を，(x, y, hp)とする．hpは現在の体力を表す．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int sx, sy, gx, gy;
 int[][] a;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
     if(a[j][i]==2){
      sx=i;
      sy=j;
      a[j][i]=1;
     }else if(a[j][i]==3){
      gx=i;
      gy=j;
      a[j][i]=1;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  int max=7;
  int[][][] d=new int[n][m][max];
  boolean[][][] visited=new boolean[n][m][max];
  LinkedList<P> que=new LinkedList<P>();

  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    fill(d[j][i], INF);
   }
  }

  que.offer(new P(sx, sy, 6));
  d[sy][sx][6]=0;
  visited[sy][sx][6]=true;

  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  for(; !que.isEmpty();){
   P p=que.poll();
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i], p.hp-1);
    if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&a[q.y][q.x]!=0&&q.hp>0){
     if(a[q.y][q.x]==4){
      q.hp=6;
     }
     if(!visited[q.y][q.x][q.hp]){
      que.offer(q);
      d[q.y][q.x][q.hp]=d[p.y][p.x][p.hp]+1;
      visited[q.y][q.x][q.hp]=true;
     }
    }
   }
  }
  int ans=INF;
  for(int k=0; k<max; k++){
   ans=min(ans, d[gy][gx][k]);
  }
  println((ans!=INF?ans:-1)+"");
 }

 class P{
  int x, y, hp;

  P(int x, int y, int hp){
   this.x=x;
   this.y=y;
   this.hp=hp;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

TopCoder Member SRM 503

2011-04-17T16:27:00.001+09:00

SRM 503(12/19 1:00~3:00)

■FoxMakingDice(Div1 Easy)

Toastmanは，パンを何枚か焼きたい．パンには幾つかの種類があり，ある種類のパンは，X分未満焼くとunder toasted，X分超過焼くとover toastedとなる．
Toastmanは，パンを焼いたが，m_i分焼いてunder toastedだったもの，また，n_i分焼いてover toastedだったものが出来た．Toastmanは何種類のパンを用いたかを覚えていないが，ある種類のパンを焼いたときにunder toasted・over toastedだったものがそれぞれ少なくとも1枚以上はあったという．
パンの種類の最小数を答えよ．

under toastedだったものをU，over toastedだったものをOとし，それらを焼かれた時間の数直線にプロットする．例えば下図．
UOUOOUOUOUOUO

・パンの種類が1つで良い場合．

UUUUU | OOOOOO
上のような場合．Xは，"|"で表される．

・パンが何種類あっても不可能な場合．

O…………
または，
…………U
の場合．

・パンの種類が2つで良い場合．

上記のどれにも当てはまらない場合．
何故なら，必ずパンの順列は，
U[…………]O
となり，
U | […………]O
で分けると，
[…………]内のOは全て排除され．
[U……U]O
となる．その後，
[U……U] | O
で分ければ終了する．


import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class ToastXToast {
 int INF=1<<28;
 double EPS=1e-9;

 public int bake(int[] a, int[] b) {
  Arrays.sort(a); // o
  Arrays.sort(b); // x
  boolean f=true;
  for(int j=0;j<b.length;j++){
   for(int i=0;i<a.length;i++){
    f&=a[i]<b[j];
   }
  }
  if(f){
   return 1;
  }
  else if(a[0]>b[0]||a[a.length-1]>b[b.length-1]){
   return -1;
  }
  else if(a.length>=2&&b.length>=2){
   return 2;
  }
  else{
   return -1;
  }
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args) {
  ToastXToast temp = new ToastXToast();
 }
}

■Result

○×× 0 0
144.26pt.

■Rating

1243 -> 1279
若干上昇．少しずつRatingを上げていきたいものです…．

Aizu Online Judge 1212 Mirror Illusion

2011-04-16T21:23:00.001+09:00

■1212 Mirror Illusion

ある座標pから方向vを見ていたとする．ちなみに，初期条件は，p₀=(0.75, 0.25)，v₀=(1, 1)
vのノルムを16以上にとれば，(p+v)が必ず室外に出るので，以下vをそういうベクトルとする．
まず，(p, p+v)が人に当たるかを調べる．当たっていたらそこで終了．
次に，(p, p+v)が鏡に当たるかを調べる．一つでも当たる鏡があれば，その内で交差点が最もpに近い鏡mを選ぶ．pを，(p, p+v)とmとの交差点とする．また，新しい方向ベクトルを，mが横置きだったらv'=(v_x, -v_y)，縦置きだったらv'=(-v_x, v_y)とする．
一つも当たらなかった場合は，外壁のいずれかに当たっていることになるので，4つの壁それぞれについて当たっているかおよび交差点を計算．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int m;
 Seg[] segs;

 void run(){
  m=8;
  for(;;){
   n=sc.nextInt();
   if(n<0){
    break;
   }
   segs=new Seg[n];
   for(int i=0; i<n; i++){
    char c=sc.next().charAt(0);
    int x=sc.nextInt();
    int y=sc.nextInt();
    if(c=='x'){
     segs[i]=new Seg(0, x, y, x+1, y);
    }else{
     segs[i]=new Seg(1, x, y, x, y+1);
    }
   }
   solve();
  }
 }

 void solve(){
  P p0=new P(0.75, 0.25);
  P p=new P(0.75, 0.25);
  P v=new P(1, 1);
  Seg[] walls=new Seg[4];
  walls[0]=new Seg(0, 0, 0, m, 0);
  walls[1]=new Seg(0, 0, m, m, m);
  walls[2]=new Seg(0, 0, 0, 0, m);
  walls[3]=new Seg(0, m, 0, m, m);

  for(int i=0; i<10; i++){
   v=v.div(v.abs()).mul(2*m);

   if(p.sub(p0).abs()>EPS&&disSP(p, p.add(v), p0)<EPS){
    int x=(int)(p0.x*100+EPS);
    int y=(int)(p0.y*100+EPS);
    println(x+" "+y);
    break;
   }

   Seg seg=null;
   P p2=null;
   double min=INF;
   for(Seg s : segs){
    if(crsSS(p, p.add(v), s.p1, s.p2)){
     P q=isLL(p, p.add(v), s.p1, s.p2);
     double d=p.sub(q).abs();
     if(d<min+EPS&&d>EPS){
      seg=s;
      p2=q;
      min=p.sub(q).abs();
     }
    }
   }

   if(p2!=null){
    p=p2;
    if(seg.d==0){
     v.y=-v.y;
    }else{
     v.x=-v.x;
    }
   }else{
    for(Seg s : walls){
     if(crsSS(p, p.add(v), s.p1, s.p2)){
      P q=isLL(p, p.add(v), s.p1, s.p2);
      if(p.sub(q).abs()>EPS){
       int x=(int)(q.x*100+EPS);
       int y=(int)(q.y*100+EPS);
       println(x+" "+y);
      }
     }
    }
    break;
   }
  }
 }

 // 線分と点の距離
 double disSP(P p1, P p2, P q){
  if(p2.sub(p1).dot(q.sub(p1))<EPS)
   return q.sub(p1).abs();
  if(p1.sub(p2).dot(q.sub(p2))<EPS)
   return q.sub(p2).abs();
  return disLP(p1, p2, q);
 }

 // 直線と点の距離
 double disLP(P p1, P p2, P q){
  return abs(p2.sub(p1).det(q.sub(p1)))/p2.sub(p1).abs();
 }

 // 線分と線分の交差判定
 boolean crsSS(P p1, P p2, P q1, P q2){
  if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))
   return false;
  if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))
   return false;
  if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))
   return false;
  if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))
   return false;
  return signum(p2.sub(p1).det(q1.sub(p1)))
    *signum(p2.sub(p1).det(q2.sub(p1)))<EPS
    &&signum(q2.sub(q1).det(p1.sub(q1)))
      *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;
 }

 // 直線と直線の交点
 P isLL(P p1, P p2, P q1, P q2){
  double d=q2.sub(q1).det(p2.sub(p1));
  if(abs(d)<EPS)
   return null;
  return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));
 }

 class Seg{
  int d;
  P p1, p2;

  Seg(int d, int x1, int y1, int x2, int y2){
   this.d=d;
   p1=new P(x1, y1);
   p2=new P(x2, y2);
  }
 }

 // 2 dimensions
 class P{
  double x, y;

  P(){
   this(0, 0);
  }

  P(double x, double y){
   this.x=x;
   this.y=y;
  }

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1211 Trapezoids

2011-04-16T21:13:00.000+09:00

■1211 Trapezoids

下のような入力が与えられたとする．

*** * * ********** * * * * * * * *** * * * * * * * * * * ***** * * * * * * * ********** * * ************

まず，四角形の内部となりえない所をある値（ここでは'-'）で埋める．

-----------***--------- -----------* *-------- **********-* *------- * *-* *------ * *** *-* *----- * * * *-* *---- * ***** *-* *--- * *-* *-- **********-* *- -----------************

(i, j)が'*'となる(i, j)をラスタスキャン．輪郭をたどり，たどった点を' 'に変更する．

-----------***--------- -----------* *-------- -----------* *------- - --* *------ - *** --* *----- - * * --* *---- - ***** --* *--- - --* *-- -----------* *- -----------************

'-'のみを壁として(i, j)からBFS．この時の探索回数が領域の面積．
(i, j)からBFSで0を'-'に塗りつぶしていく

-----------***--------- -----------* *-------- -----------* *------- -----------* *------ --***------* *----- --* *-----* *---- --*****----* *--- -----------* *-- -----------* *- -----------************

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 int[][] a;
 int c;
 boolean[] wall;

 void run(){
  for(int k=0;; k++){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   if(k>0){
    println("----------");
   }
   sc.nextLine();
   m=0;
   String[] ss=new String[n];
   for(int i=0; i<n; i++){
    ss[i]=sc.nextLine();
    m=max(m, ss[i].length());
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<ss[j].length(); i++){
     a[j][i]=ss[j].charAt(i)=='*'?1:0;
    }
   }
   solve();
  }
 }

 void solve(){
  c=2;
  wall=new boolean[]{false, true, true};
  for(int j=0; j<n; j++){
   if(a[j][0]==0){
    bfs(0, j);
   }
   if(a[j][m-1]==0){
    bfs(m-1, j);
   }
  }
  for(int i=0; i<m; i++){
   if(a[0][i]==0){
    bfs(i, 0);
   }
   if(a[n-1][i]==0){
    bfs(i, n-1);
   }
  }

  HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
  int[] dx={1, 1, 0, -1, -1, -1, 0, 1};
  int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    if(a[j][i]==1){
     int outline=0;
     int d=0;
     int x=i, y=j;
     for(;;){
      outline++;
      a[y][x]=0;
      boolean f=false;
      d=(d+5)%8;
      for(int k=0; k<8; k++, d=(d+1)%8){
       int x2=x+dx[d];
       int y2=y+dy[d];
       if(x2>=0&&x2<m&&y2>=0&&y2<n&&a[y2][x2]==1){
        x=x2;
        y=y2;
        f=true;
        break;
       }
      }
      if(!f){
       break;
      }
     }
     c=-1;
     wall=new boolean[]{false, false, true};
     int area=bfs(x, y);
     if(!map.containsKey(area)){
      map.put(area, 0);
     }
     map.put(area, map.get(area)+1);

     c=2;
     wall=new boolean[]{false, true, true};
     bfs(x, y);
    }
   }
  }
  Integer[] is=map.keySet().toArray(new Integer[0]);
  sort(is);
  for(int key : is){
   println(key+" "+map.get(key));
  }
 }

 int bfs(int x, int y){
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};
  LinkedList<P> que=new LinkedList<P>();
  boolean[][] visited=new boolean[n][m];
  que.add(new P(x, y));
  visited[y][x]=true;
  int res=0;
  for(; !que.isEmpty();){
   P p=que.poll();
   if(c>=0){
    a[p.y][p.x]=c;
   }
   res++;
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i]);
    if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&!visited[q.y][q.x]
      &&!wall[a[q.y][q.x]]){
     que.add(q);
     visited[q.y][q.x]=true;
    }
   }
  }
  return res;
 }

 class P{
  int x, y;

  P(int x, int y){
   this.x=x;
   this.y=y;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1208 Rational Irrationals

2011-04-05T23:38:00.000+09:00

■1208 Rational Irrationals

全探索を行うと，O(n²)でかなりキツイ．そこで二部探索を使う．
具体的には，分数をm/dとした時，dを1~nまで回し，√pに近くなるようなmを求める．
探索の幅として[1,n]を設定し，m/d<√pを条件とすれば，
m/d<√p<(m+1)/d
もしくは，
m/d<(m+1)/d<√p (ただし，m+1>n)
となる．
事実上計算量はO(n)．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int p, m;

 void run(){
  for(;;){
   p=sc.nextInt();
   m=sc.nextInt();
   if((p|m)==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  long n1=0, d1=1;
  long n2=m, d2=1;
  for(long d=1; d<=m; d++){
   double left=1, right=m;
   for(int i=0; i<100; i++){
    double mid=(left+right)/2;
    if(mid*mid<p*d*d+EPS){
     left=mid;
    }else{
     right=mid;
    }
   }
   int n=(int)(left+EPS);
   if(n1*d<n*d1&&n*n<p*d*d){
    n1=n;
    d1=d;
   }
   if(++n<=m){
    if(p*d*d<n*n&&n*d2<n2*d){
     n2=n;
     d2=d;
    }
   }
  }
  long gcd=gcd(n1, d1);
  n1/=gcd;
  d1/=gcd;
  gcd=gcd(n2, d2);
  n2/=gcd;
  d2/=gcd;
  println(n2+"/"+d2+" "+n1+"/"+d1);
 }

 long gcd(long m, long n){
  for(; n!=0;){
   m=m%n;
   long t=m;
   m=n;
   n=t;
  }
  return m;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge

2011-04-04T20:25:00.000+09:00

■1204 Pipeline Scheduling

再帰を用いて実際にシミュレートする．左端から詰めていくようにして，簡単な枝刈り（現時点でのサイクル数が，暫定の最短より長い場合は中断）を付け加えれば通る．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, t, u;
 int[][] a, b;
 int ans;

 void run(){
  t=10;
  u=5;
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   a=new int[u][n];
   for(int j=0; j<u; j++){
    String s=sc.next();
    for(int i=0; i<n; i++){
     a[j][i]=s.charAt(i)=='.'?0:1;
    }
   }
   solve();
  }
 }

 void rec(int k, int p){
  if(p>=ans){
   return;
  }
  if(k==t+1){
   ans=min(ans, p+n-1);
   return;
  }
  for(int q=p; q<p+n; q++){
   boolean f=true;
   for(int j=0; j<u; j++){
    for(int i=0; i<n; i++){
     f&=a[j][i]==0||b[j][q+i]==0;
    }
   }
   if(f){
    for(int j=0; j<u; j++){
     for(int i=0; i<n; i++){
      if(a[j][i]==1){
       b[j][q+i]=k;
      }
     }
    }
    rec(k+1, q+1);
    for(int j=0; j<u; j++){
     for(int i=0; i<n; i++){
      if(a[j][i]==1){
       b[j][q+i]=0;
      }
     }
    }
   }
  }
 }

 void solve(){
  ans=INF;
  b=new int[u][(n+1)*(t+1)];
  rec(1, 0);
  println(""+ans);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1203 Napoleon's Grumble

2011-04-03T14:35:00.001+09:00

■1203 Napoleon's Grumble

回文の中心点jを0~n-1まで動かしながら，
c_j-i,…,c_j+i
c_j-i,…,c_j+i+1
が回文となる最大のiを探す．
片っ端から回文候補をリストに入れた後，冗長のものを省く．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 String s;

 void run(){
  for(; sc.hasNextLine();){
   s=sc.nextLine();
   solve();
  }
 }

 void solve(){
  s=s.toUpperCase().replaceAll("[^A-Z]", "");
  int n=s.length();
  TreeSet<String> set=new TreeSet<String>();
  for(int j=0; j<n; j++){
   int i;
   for(i=0; j-i>=0&&j+i<n&&s.charAt(j-i)==s.charAt(j+i); i++);
   i--;
   if(i>=1){
    set.add(s.substring(j-i, j+i+1));
   }
   for(i=0; j-i>=0&&j+i+1<n&&s.charAt(j-i)==s.charAt(j+i+1); i++);
   i--;
   if(i>=1){
    set.add(s.substring(j-i, j+i+2));
   }
  }
  for(Iterator<String> i=set.iterator(); i.hasNext();){
   String s=i.next();
   for(Iterator<String> j=set.iterator(); j.hasNext();){
    String t=j.next();
    if((s.length()+t.length())%2==0&&t.length()>s.length()){
     int k=(t.length()-s.length())/2;
     if(t.substring(k, t.length()-k).equals(s)){
      i.remove();
      break;
     }
    }
   }
  }
  for(; !set.isEmpty();){
   print(set.pollFirst());
   if(!set.isEmpty()){
    print(" ");
   }
  }
  println("");
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1201 Lattice Practices

2011-04-02T23:13:00.001+09:00

■1201 Lattice Practices

まず，10枚の板から5枚を選び，その5枚で構成出来るパターンを全て列挙．列挙の際，反転させても変わらない板がある場合があるので，重複を考慮する必要がある．それぞれのパターンに対応するパターンを残りの5枚で構成できうるかを判定する．10個から5個選ぶ…₁₀P₅=30240反転の種類…2⁵=32

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int[] a, rev;
 int n, m;

 void run(){
  n=10;
  m=n/2;
  a=new int[n];
  rev=new int[1<<m];
  for(int i=0; i<1<<m; i++){
   int x=i;
   x=(x&0x55555555)<<1|(x>>1)&0x55555555;
   x=(x&0x33333333)<<2|(x>>2)&0x33333333;
   x=(x&0x0f0f0f0f)<<4|(x>>4)&0x0f0f0f0f;
   x=(x<<24)|((x&0xff00)<<8)|((x>>8)&0xff00)|(x>>24);
   rev[i]=(int)(x>>(32-m))&((1<<m)-1);
  }

  for(;;){
   for(int i=0; i<n; i++){
    String s=sc.next();
    if(s.equals("END")){
     return;
    }
    a[i]=Integer.parseInt(s, 2);
   }
   solve();
  }
 }

 void solve(){
  int ans=0;
  int[] b=new int[m];
  int[] c=new int[m];
  int comb=(1<<m)-1;
  boolean[] used=new boolean[m];

  for(; comb<1<<n;){
   // 2^(反転させても同じものの個数)で割る
   int div=1;
   for(int i=0, j=0, k=0; k<10; k++){
    if((comb>>k&1)==1){
     b[i++]=a[k];
     if(rev[a[k]]==a[k]){
      div*=2;
     }
    }else{
     c[j++]=a[k];
    }
   }

   Arrays.sort(b);
   int sum=0;
   for(;;){
    // 2^n通り反転させる
    for(int sup=0; sup<1<<m; sup++){
     for(int i=0; i<m; i++){
      if((sup>>i&1)==1){
       b[i]=rev[b[i]];
      }
     }
     // bの並びをcで構築できるか
     Arrays.fill(used, false);
     sum++;
     for(int i=0; i<m; i++){
      int bits=0;
      for(int j=0; j<m; j++){
       bits=(bits<<1)|(b[j]>>i&1);
      }
      int k=-1;
      for(int j=0; j<m; j++){
       if(!used[j]
         &&((c[j]^bits)==(1<<m)-1||(rev[c[j]]^bits)==(1<<m)-1)){
        k=j;
       }
      }
      if(k>=0){
       used[k]=true;
      }else{
       sum--;
       break;
      }
     }
     for(int i=0; i<m; i++){
      if((sup>>i&1)==1){
       b[i]=rev[b[i]];
      }
     }
    }
    if(!nextPermutation(b)){
     break;
    }
   }
   ans+=sum/div;

   int x=comb&-comb, y=comb+x;
   comb=((comb&~y)/x>>1)|y;
  }
  ans/=8; // 鏡像反転*回転
  println(""+ans);
 }

 boolean nextPermutation(int[] is){
  int n=is.length;
  for(int i=n-1; i>0; i--){
   if(is[i-1]<is[i]){
    int j=n;
    while(is[i-1]>=is[--j]);
    swap(is, i-1, j);
    rev(is, i, n);
    return true;
   }
  }
  rev(is, 0, n);
  return false;
 }

 void swap(int[] is, int i, int j){
  int t=is[i];
  is[i]=is[j];
  is[j]=t;
 }

 void rev(int[] is, int i, int j){
  for(j--; i<j; i++, j--){
   int t=is[i];
   is[i]=is[j];
   is[j]=t;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

今月の〇〇(2011年3月)

2011-03-31T23:18:00.002+09:00

■Aizu Online Judge

Solved:235/43th
Rating:151.76/67th
簡単な問題ばかり解いていたので，Ratingの順位がやや低めです．ということで来月の目標はRating200にしました．

■TopCoder/Codeforces

ほとんど参加できていません．そのためレーティングも代わり映えしていません．そのため来月は，レーティングの昇降は兎も角として，出来るだけ参加することを重視しようと思います．

■専門書

「計算理論の基礎」を読み進めています．5章辺りを読んでいますが，練習問題に全く手を付けていないため，そちらにも着手する必要がありそうです．また，「コンピュータの数学」は今の自分なら十分読めると判断したため，そろそろ真面目に読もうかと考えている次第です．

Aizu Online Judge 0125 Day Count

2011-03-25T00:13:00.000+09:00

■0125 Day Count

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class Main{

 Scanner sc=new Scanner(System.in);;

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int y1=sc.nextInt();
   int m1=sc.nextInt();
   int d1=sc.nextInt();
   int y2=sc.nextInt();
   int m2=sc.nextInt();
   int d2=sc.nextInt();
   if(y1<0||m1<0||d1<0||y2<0||m2<0||d2<0){
    break;
   }
   int a=day(y1, m1, d1);
   int b=day(y2, m2, d2);
   println((b-a)+"");
  }
 }

 int day(int y, int m, int d){
  int res=0;
  int[] days={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  for(int i=0; i<m-1; i++){
   res+=days[i];
  }
  res+=y*365+d-1;
  if((m==2&&d<=28)||m==1){
   y--;
  }
  if(y>=0){
   res+=y/4+1;
   res-=y/100+1;
   res+=y/400+1;
  }
  return res;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  new Main().run();
 }
}

Aizu Online Judge 0121 Seven Puzzle

2011-03-25T00:12:00.001+09:00

■0121 Seven Puzzle

先に，全てのパターンについて最小ステップ数を計算しておく．BFSで可能．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 HashMap<Integer, Integer> map;
 int[] a;
 int w=4, h=2;

 void run(){
  a=new int[w*h];
  init();
  for(; sc.hasNext();){
   for(int i=0; i<w*h; i++){
    a[i]=sc.nextInt();
   }
   println(""+map.get(id(a)));
  }
 }

 void init(){

  LinkedList<S> que=new LinkedList<S>();
  map=new HashMap<Integer, Integer>();

  que.offer(new S(0, 0, new int[]{0, 1, 2, 3, 4, 5, 6, 7}));
  map.put(id(que.peek().a), 0);
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  for(; !que.isEmpty();){
   S s=que.poll();
   int p=s.y*w+s.x;
   for(int i=0; i<4; i++){
    int x2=s.x+dx[i];
    int y2=s.y+dy[i];
    int p2=y2*w+x2;
    if(x2>=0&&x2<w&&y2>=0&&y2<h){
     int[] a2=s.a.clone();
     int t=a2[p];
     a2[p]=a2[p2];
     a2[p2]=t;
     S s2=new S(x2, y2, a2);
     if(!map.containsKey(id(s2.a))){
      que.offer(s2);
      map.put(id(s2.a), map.get(id(s.a))+1);
     }
    }
   }
  }
 }

 int id(int[] a){
  int res=0;
  for(int e : a){
   res=res*10+e;
  }
  return res;
 }

 class S{
  int x, y;
  int[] a;

  S(int x, int y, int[] a){
   this.x=x;
   this.y=y;
   this.a=a;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0120 Patisserie

2011-03-25T00:11:00.000+09:00

■0120 Patisserie

r₁のロールケーキにr₂のロールケーキを並べると，
長さが2√(r₁r₂)-r₁+r₂だけ増える．
dp[k][S]=右端がロールケーキk，集合Sのロールケーキを既に並べたとしたときの最小の長さ
としてDP．計算量はO(2ⁿn²)．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int len, n;
 int[] a;

 void run(){
  for(;sc.hasNext();){
   String[] ss=sc.nextLine().split(" ");
   len=Integer.parseInt(ss[0]);
   n=ss.length-1;
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=Integer.parseInt(ss[i+1]);
   }
   solve();
  }
 }

 void solve(){
  double[][] dp=new double[1<<n][n];
  for(int j=0; j<1<<n; j++){
   fill(dp[j], INF);
  }
  for(int i=0; i<n; i++){
   dp[1<<i][i]=2*a[i];
  }
  for(int s=1; s<1<<n; s++){
   for(int j=0; j<n; j++){
    if((s>>j&1)==0){
     continue;
    }
    for(int i=0; i<n; i++){
     if((s>>i&1)==0){
      dp[s|1<<i][i]=min(dp[s|1<<i][i],
        dp[s][j]+2*sqrt(a[j]*a[i])-a[j]+a[i]);
     }
    }
   }
  }
  double min=INF;
  for(int i=0; i<n; i++){
   min=min(min, dp[(1<<n)-1][i]);
  }
  println(min<len+EPS?"OK":"NA");
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0514 Quality Checking

2011-03-25T00:10:00.000+09:00

■0514 Quality Checking

合格

→3つ共正常

失敗

→2つが正常なら残り1つが失敗

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int na, nb, nc;
   na=sc.nextInt();
   nb=sc.nextInt();
   nc=sc.nextInt();
   if((na|nb|nc)==0){
    break;
   }

   int n=sc.nextInt();
   int[] as=new int[na];
   int[] bs=new int[nb];
   int[] cs=new int[nc];
   Arrays.fill(as, 2);
   Arrays.fill(bs, 2);
   Arrays.fill(cs, 2);

   R[] rs=new R[n];
   for(int i=0; i<n; i++){
    int a=sc.nextInt()-1;
    int b=sc.nextInt()-na-1;
    int c=sc.nextInt()-na-nb-1;
    int r=sc.nextInt();
    rs[i]=new R(a, b, c, r);
    if(r==1){
     as[a]=1;
     bs[b]=1;
     cs[c]=1;
    }
   }

   for(int i=0; i<n; i++){
    if(rs[i].r==0){
     int a=as[rs[i].a];
     int b=bs[rs[i].b];
     int c=cs[rs[i].c];
     if(a==1&&b==1){
      c=0;
     }else if(b==1&&c==1){
      a=0;
     }else if(c==1&&a==1){
      b=0;
     }
     as[rs[i].a]=a;
     bs[rs[i].b]=b;
     cs[rs[i].c]=c;
    }
   }
   for(int i=0; i<na; i++){
    println(as[i]+"");
   }
   for(int i=0; i<nb; i++){
    println(bs[i]+"");
   }
   for(int i=0; i<nc; i++){
    println(cs[i]+"");
   }
  }
 }

 class R{
  int a, b, c, r;

  R(int a, int b, int c, int r){
   this.a=a;
   this.b=b;
   this.c=c;
   this.r=r;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0231 Dangerous Bridge

2011-03-25T00:07:00.001+09:00

■0231 Dangerous Bridge

時刻aと時刻b-1について調べるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] m, a, b;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   m=new int[n];
   a=new int[n];
   b=new int[n];
   for(int i=0; i<n; i++){
    m[i]=sc.nextInt();
    a[i]=sc.nextInt();
    b[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  for(int j=0; j<n; j++){
   int sum1=0, sum2=0;
   for(int i=0; i<n; i++){
    if(a[i]<=a[j]&&a[j]<b[i]){
     sum1+=m[i];
    }
    if(a[i]<=b[j]-1&&b[j]-1<b[i]){
     sum2+=m[i];
    }
   }
   if(sum1>150||sum2>150){
    println("NG");
    return;
   }
  }
  println("OK");
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Codeforces Round #61 (Div. 2)

2011-03-08T16:12:00.001+09:00

コンテストが随分ご無沙汰だったので参加してきました．

Codeforces Round #61 (Div. 2)

A. Petya and Java

面倒だったので，BigIntegerを使って読み込み．実は，入力は必ず正の数なので，負の方向へのチェックは必要ありませんでした…．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  BigInteger b=sc.nextBigInteger();
  long[] s={-128, -32768, -2147483648, -9223372036854775808L};
  long[] e={127, 32767, 2147483647, 9223372036854775807L};
  String[] ss={"byte", "short", "int", "long"};
  for(int i=0; i<4; i++){
   if(b.compareTo(new BigInteger(s[i]+""))>=0
     &&b.compareTo(new BigInteger(e[i]+""))<=0){
    println(ss[i]);
    return;
   }
  }
  println("BigInteger");
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new A().run();
 }
}

B. Petya and Countryside

全探索すればOK．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] a;

 void run(){
  n=sc.nextInt();
  a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=sc.nextInt();
  }
  int max=0;
  for(int j=0; j<n; j++){
   int s=1;
   for(int i=j-1; i>=0; i--){
    if(a[i]<=a[i+1]){
     s++;
    }else{
     break;
    }
   }
   for(int i=j+1; i<n; i++){
    if(a[i-1]>=a[i]){
     s++;
    }else{
     break;
    }
   }
   max=max(max, s);
  }
  println(max+"");
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new B().run();
 }
}

C. Petya and File System

書けば通ると思いましたが，落ちてしまいました．

D. Petya and His Friends

私が考えたのは以下のやり方．

a₁	a₂	a₃	a₄	…	a_n
2	2	2	2	…
	3	3	3	…	3
5		5	5	…	5
7	7		7	…	7

これを縦に掛けたものがそれぞれ答え．

実際には，6, 10, 15, 15*2, 15*3, …で十分だったようです．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class D{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  int n=sc.nextInt();
  if(n==2){
   println("-1");
   return;
  }
  BigInteger[] bis=new BigInteger[n];
  for(int i=0; i<n; i++){
   bis[i]=BigInteger.ONE;
  }

  int max=1000;
  int p=0;
  int[] prime=new int[max];
  boolean[] isPrime=new boolean[max+1];
  Arrays.fill(isPrime, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=2; i<=max; i++){
   if(isPrime[i]){
    prime[p++]=i;
    for(int j=2*i; j<=max; j+=i){
     isPrime[j]=false;
    }
   }
  }

  for(int j=0; j<n; j++){
   BigInteger bi=new BigInteger(prime[j]+"");
   for(int i=0; i<n-1; i++){
    bis[(j+i)%n]=bis[(j+i)%n].multiply(bi);
   }
  }
  for(int i=0; i<n; i++){
   if(bis[i].toString().length()>100){
    println("-1");
    return;
   }
  }
  for(int i=0; i<n; i++){
   println(bis[i]+"");
  }
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new D().run();
 }
}

ooxo- 3226p 68位
1506 -> 1694
紫コーダーになりました．

Aizu Online Judge 0212 Highway Express Bus

2011-03-07T01:06:00.000+09:00

■0212 Highway Express Bus

拡張Dijkstra．ノードを(今いる町, 残りチケット枚数)とする．後は次状態に遷移する際に，チケットを使った場合と使わなかった場合で更新．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int c, n, m, s, g;
 LinkedList<E>[] es;

 @SuppressWarnings("unchecked")
 void run(){
  for(;;){
   c=sc.nextInt();
   n=sc.nextInt();
   m=sc.nextInt();
   s=sc.nextInt()-1;
   g=sc.nextInt()-1;
   if((c|n|m|(s+1)|(g+1))==0){
    break;
   }
   es=new LinkedList[n];
   for(int i=0; i<n; i++){
    es[i]=new LinkedList<E>();
   }
   for(int i=0; i<m; i++){
    int u=sc.nextInt()-1;
    int v=sc.nextInt()-1;
    int w=sc.nextInt()/10;
    es[u].add(new E(v, w));
    es[v].add(new E(u, w));
   }
   solve();
  }
 }

 void solve(){
  int[][] d=new int[n][c+1];
  PriorityQueue<P> que=new PriorityQueue<P>();

  for(int i=0; i<n; i++){
   Arrays.fill(d[i], INF);
  }
  d[s][c]=0;
  que.offer(new P(s, c, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v][p.c]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to][p.c]>d[p.v][p.c]+e.cost){
     d[e.to][p.c]=d[p.v][p.c]+e.cost;
     que.offer(new P(e.to, p.c, d[e.to][p.c]));
    }
    if(p.c>0&&d[e.to][p.c-1]>d[p.v][p.c]+e.cost/2){
     d[e.to][p.c-1]=d[p.v][p.c]+e.cost/2;
     que.offer(new P(e.to, p.c-1, d[e.to][p.c-1]));
    }
   }
  }
  int min=INF;
  for(int i=0; i<=c; i++){
   min=min(min, d[g][i]);
  }
  min*=10;
  println(""+min);
 }

 class E{
  int to, cost;

  E(int to, int cost){
   this.to=to;
   this.cost=cost;
  }
 }

 class P implements Comparable<P>{
  int v, c, d;

  P(int v, int c, int d){
   this.v=v;
   this.c=c;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0209 Scene in a Picture

2011-03-07T01:04:00.000+09:00

■0209 Scene in a Picture

全探索．

計算量はO(m²n²)だが，100²50²=2.5*10⁷なので余裕．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int[][] a, b;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[m][m];
   b=new int[n][n];
   for(int j=0; j<m; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
    }
   }
   for(int j=0; j<n; j++){
    for(int i=0; i<n; i++){
     b[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  int[][][] c=new int[4][n][n];
  for(int j=0; j<n; j++){
   for(int i=0; i<n; i++){
    c[0][j][i]=b[j][i];
    c[1][i][n-1-j]=b[j][i];
    c[2][n-1-j][n-1-i]=b[j][i];
    c[3][n-1-i][j]=b[j][i];
   }
  }

  int p=m*m;
  for(int i=0; i<4; i++){
   p=min(p, match(c[i]));
  }
  if(p==m*m){
   println("NA");
  }else{
   println((p%m+1)+" "+(p/m+1));
  }
 }

 int match(int[][] c){
  for(int y=0; y+n<=m; y++){
   for(int x=0; x+n<=m; x++){
    boolean f=true;
    for(int j=0; j<n; j++){
     for(int i=0; i<n; i++){
      f&=c[j][i]==-1||c[j][i]==a[y+j][x+i];
     }
    }
    if(f){
     for(int j=0; j<n; j++){
      for(int i=0; i<n; i++){
       if(c[j][i]!=-1){
        return (y+j)*m+(x+i);
       }
      }
     }
    }
   }
  }
  return m*m;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0207 Block

2011-03-07T01:03:00.001+09:00

■0207 Block

(xs,ys)から同じ色を持つブロックについてBFS．(xg,yg)が訪問済みであればOK．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int w, h;
 int sx, sy;
 int gx, gy;
 int[][] a;

 void run(){
  for(;;){
   w=sc.nextInt();
   h=sc.nextInt();
   if((w|h)==0){
    break;
   }
   sx=sc.nextInt()-1;
   sy=sc.nextInt()-1;
   gx=sc.nextInt()-1;
   gy=sc.nextInt()-1;
   int n=sc.nextInt();
   a=new int[h][w];
   for(int k=0; k<n; k++){
    int c=sc.nextInt();
    int d=sc.nextInt();
    int x=sc.nextInt()-1;
    int y=sc.nextInt()-1;
    for(int j=0; j<2; j++){
     for(int i=0; i<4; i++){
      if(d==0){
       a[y+j][x+i]=c;
      }else{
       a[y+i][x+j]=c;
      }
     }
    }
   }
   solve();
  }
 }

 void solve(){
  LinkedList<P> que=new LinkedList<P>();
  boolean[][] visited=new boolean[h][w];

  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  que.offer(new P(sx, sy));
  visited[sy][sx]=true;

  for(; !que.isEmpty();){
   P p=que.poll();
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i]);
    if(q.x>=0&&q.x<w&&q.y>=0&&q.y<h&&a[q.y][q.x]==a[sy][sx]
      &&!visited[q.y][q.x]){
     que.offer(q);
     visited[q.y][q.x]=true;
    }
   }
  }
  println(visited[gy][gx]?"OK":"NG");
 }

 class P{
  int x, y;

  P(int x, int y){
   this.x=x;
   this.y=y;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0203 A New Plan of Aizu Ski Resort

2011-03-07T01:03:00.000+09:00

■0203 A New Plan of Aizu Ski Resort

dp[j][i]=(i,j)に到達するまでの滑り方のパターン数
としてDP．
dp[0][i]=
0 - (i,0)に障害物がある
1 - (i,0)に障害物がない
あとは，説明通りに更新していく．dp[n]まで用意しておいて，dp[n-1]とdp[n]の総和が答え．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int[][] a;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  long[][] dp=new long[n+1][m];
  for(int i=0; i<m; i++){
   if(a[0][i]==0){
    dp[0][i]=1;
   }
  }
  for(int j=0; j<n-1; j++){
   for(int i=0; i<m; i++){
    switch(a[j][i]){
    case 0:
     if(i-1>=0&&a[j+1][i-1]==0)
      dp[j+1][i-1]+=dp[j][i];
     if(a[j+1][i]!=1)
      dp[j+1][i]+=dp[j][i];
     if(i+1<m&&a[j+1][i+1]==0)
      dp[j+1][i+1]+=dp[j][i];
     break;
    case 2:
     if(j>=n-2||a[j+2][i]!=1)
      dp[j+2][i]+=dp[j][i];
     break;
    }
   }
  }
  long ans=0;
  for(int j=n-1; j<n+1; j++){
   for(int i=0; i<m; i++){
    ans+=dp[j][i];
   }
  }
  println(ans+"");
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0202 At Boss's Expense

2011-03-05T00:14:00.002+09:00

■0202 At Boss's Expense

可能な合計金額と，素数全列挙．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, x;
 int[] a;

 void run(){
  for(;;){
   n=sc.nextInt();
   x=sc.nextInt();
   if((n|x)==0){
    break;
   }
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int max=1000000;
  int p=0;
  int[] prime=new int[max];
  boolean[] isPrime=new boolean[max+1];
  Arrays.fill(isPrime, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=2; i<=max; i++){
   if(isPrime[i]){
    prime[p++]=i;
    for(int j=2*i; j<=max; j+=i){
     isPrime[j]=false;
    }
   }
  }
  boolean[] dp=new boolean[max+1];
  dp[0]=true;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<=max; i++){
    dp[i]|=dp[i-a[j]];
   }
  }
  int ans=0;
  for(int i=2; i<=x; i++){
   if(dp[i]&&isPrime[i]){
    ans=i;
   }
  }
  if(ans>0){
   println(ans+"");
  }else{
   println("NA");
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0201 Wrought Gold Master

2011-03-05T00:14:00.001+09:00

■0201 Wrought Gold Master

DFS．あるアイテムについてそれ自身を買う，あるいはレシピを用いて錬金するという両手法を試し，最小を返す．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 HashMap<String, Integer> val;
 HashMap<String, LinkedList<String>> recipe;
 String item;

 void run(){
  for(;;){
   val=new HashMap<String, Integer>();
   recipe=new HashMap<String, LinkedList<String>>();
   n=sc.nextInt();
   if(n==0){
    break;
   }
   for(int i=0; i<n; i++){
    String s=sc.next();
    int d=sc.nextInt();
    val.put(s, d);
   }
   m=sc.nextInt();
   for(int j=0; j<m; j++){
    String s=sc.next();
    int k=sc.nextInt();
    LinkedList<String> list=new LinkedList<String>();
    for(int i=0; i<k; i++){
     String t=sc.next();
     list.add(t);
    }
    recipe.put(s, list);
   }
   item=sc.next();
   solve();
  }
 }

 void solve(){
  println(dfs(item)+"");
 }

 int dfs(String s){
  int res=INF;
  if(val.containsKey(s)){
   res=min(res, val.get(s));
  }
  if(recipe.containsKey(s)){
   int sum=0;
   for(String t : recipe.get(s)){
    sum+=dfs(t);
   }
   res=min(res, sum);
  }
  return res;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0200 Traveling Alone: One-way Ticket of Youth

2011-03-05T00:14:00.000+09:00

■0200 Traveling Alone: One-way Ticket of Youth

Warshall-Floyd．O(n³)でn=300なので，多分間に合うだろうという魂胆．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int[][] cost, time;
 int n, m, k;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   cost=new int[m][m];
   time=new int[m][m];
   for(int j=0; j<m; j++){
    fill(cost[j], INF);
    fill(time[j], INF);
   }
   for(int i=0; i<n; i++){
    int a=sc.nextInt()-1;
    int b=sc.nextInt()-1;
    int c=sc.nextInt();
    int t=sc.nextInt();
    cost[a][b]=cost[b][a]=c;
    time[a][b]=time[b][a]=t;
   }
   for(int k=0; k<m; k++){
    for(int i=0; i<m; i++){
     for(int j=0; j<m; j++){
      cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);
      time[i][j]=min(time[i][j], time[i][k]+time[k][j]);
     }
    }
   }
   k=sc.nextInt();
   for(int i=0; i<k; i++){
    int p=sc.nextInt()-1;
    int q=sc.nextInt()-1;
    int r=sc.nextInt();
    if(r==0){
     println(cost[p][q]+"");
    }else{
     println(time[p][q]+"");
    }
   }
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0197 Greatest Common Divisor: Euclidean Algorithm

2011-03-04T00:02:00.003+09:00

■0197 Greatest Common Divisor: Euclidean Algorithm

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int x=sc.nextInt();
   int y=sc.nextInt();
   if((x|y)==0){
    break;
   }
   if(x<y){
    int t=x;
    x=y;
    y=t;
   }
   for(int i=0;; i++){
    if(y==0){
     println(x+" "+i);
     break;
    }
    x=x%y;
    int t=x;
    x=y;
    y=t;
   }
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0196 Baseball Championship

2011-03-04T00:02:00.002+09:00

■0196 Baseball Championship

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int n=sc.nextInt();
   if(n==0){
    break;
   }
   R[] rs=new R[n];
   for(int j=0; j<n; j++){
    rs[j]=new R();
    rs[j].name=sc.next();
    for(int i=0; i<n-1; i++){
     switch(sc.nextInt()){
     case 0:
      rs[j].win--;
      break;
     case 1:
      rs[j].lose++;
      break;
     }
    }
   }
   Arrays.sort(rs);
   for(R r : rs){
    println(r.name);
   }
  }
 }

 class R implements Comparable<R>{
  int win, lose;
  String name;

  @Override
  public int compareTo(R r){
   if(win!=r.win){
    return win-r.win;
   }else{
    return lose-r.lose;
   }
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0195 What is the Most Popular Shop in Tokaichi?

2011-03-04T00:02:00.001+09:00

■0195 What is the Most Popular Shop in Tokaichi?

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int n=5;
   int max=0;
   char c='A';
   for(int i=0; i<n; i++){
    int a=sc.nextInt()+sc.nextInt();
    if(a==0){
     return;
    }
    if(a>max){
     c=(char)('A'+i);
     max=a;
    }
   }
   println(c+" "+max);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0189 Convenient Location

2011-03-04T00:02:00.000+09:00

■0189 Convenient Location

各々のノードのついて，Dijkstraをやるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 LinkedList<E>[] es;

 @SuppressWarnings("unchecked")
 void run(){
  for(;;){
   es=new LinkedList[10];
   for(int i=0; i<es.length; i++){
    es[i]=new LinkedList<E>();
   }
   n=0;
   m=sc.nextInt();
   if(m==0){
    break;
   }
   for(int i=0; i<m; i++){
    int u=sc.nextInt();
    int v=sc.nextInt();
    int w=sc.nextInt();
    es[u].add(new E(v, w));
    es[v].add(new E(u, w));
    n=max(n, u+1);
    n=max(n, v+1);
   }
   solve();
  }
 }

 void solve(){
  int min=INF;
  int v=0;
  for(int i=0; i<n; i++){
   int d=dijkstra(i);
   if(d<min){
    v=i;
    min=d;
   }
  }
  println(v+" "+min);
 }

 int dijkstra(int s){
  int[] d=new int[n];
  PriorityQueue<P> que=new PriorityQueue<P>();

  Arrays.fill(d, INF);
  d[s]=0;
  que.offer(new P(s, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to]>d[p.v]+e.cost){
     d[e.to]=d[p.v]+e.cost;
     que.offer(new P(e.to, d[e.to]));
    }
   }
  }

  int res=0;
  for(int i=0; i<n; i++){
   res+=d[i];
  }
  return res;
 }

 class E{
  int to, cost;

  E(int to, int cost){
   this.to=to;
   this.cost=cost;
  }
 }

 class P implements Comparable<P>{
  int v, d;

  P(int v, int d){
   this.v=v;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0185 Goldbach's Conjecture II

2011-02-24T22:33:00.000+09:00

■0185 Goldbach's Conjecture II

入力が最大で10⁶なので，最初にエラトステネスの篩で素数を生成しておくのが無難．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int max=1000000;
 int[] prime;
 boolean[] isPrime;

 void run(){
  int p=0;
  prime=new int[max];
  isPrime=new boolean[max+1];
  Arrays.fill(isPrime, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=2; i<=max; i++){
   if(isPrime[i]){
    prime[p++]=i;
    for(int j=2*i; j<=max; j+=i){
     isPrime[j]=false;
    }
   }
  }

  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   int ans=0;
   for(int i=0; i<p; i++){
    if(prime[i]>n/2){
     break;
    }
    if(isPrime[n-prime[i]]){
     ans++;
    }
   }
   println(""+ans);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0184 Tsuruga Castle

2011-02-24T22:30:00.013+09:00

■0184 Tsuruga Castle

やるだけ．出力量がかなり多いので，バッファに貯めて最後に出力した．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int n=sc.nextInt();
   if(n==0){
    break;
   }
   int[] h=new int[7];
   for(int i=0; i<n; i++){
    int a=sc.nextInt();
    for(int k=0; k<7; k++){
     if(a<(k+1)*10||k==6){
      h[k]++;
      break;
     }
    }
   }
   for(int i=0; i<7; i++){
    println(""+h[i]);
   }
  }
  System.out.flush();
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0183 Black-and-White

2011-02-24T22:30:00.012+09:00

■0183 Black-and-White

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int[][] a;
 int n;

 void run(){
  n=3;
  for(;;){
   a=new int[n][n];
   for(int j=0; j<n; j++){
    String s=sc.next();
    if(s.equals("0")){
     return;
    }
    for(int i=0; i<n; i++){
     switch(s.charAt(i)){
     case 'b':
      a[j][i]=0;
      break;
     case 'w':
      a[j][i]=1;
      break;
     case '+':
      a[j][i]=-1;
      break;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  if(check(0)){
   println("b");
  }else if(check(1)){
   println("w");
  }else{
   println("NA");
  }
 }

 boolean check(int e){
  boolean f=false;
  for(int j=0; j<n; j++){
   boolean f1=true, f2=true;
   for(int i=0; i<n; i++){
    f1&=a[j][i]==e;
    f2&=a[i][j]==e;
   }
   f|=f1|f2;
  }
  boolean f1=true, f2=true;
  for(int i=0; i<n; i++){
   f1&=a[i][i]==e;
   f2&=a[i][n-1-i]==e;
  }
  return f|f1|f2;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0181 Persistence

2011-02-24T00:10:00.002+09:00

■0181 Persistence

二分探索．

本棚の幅をbとし，幅bの本棚に全て本を収納出来ることをC(b)で表す．
この問題における答えは，C(b)となる最小のb(=b_min)であり，C(b)であるかどうかは容易に求まる，かつb<b_minなるbについては，C(b)は成立しないので二分探索を適用することが出来る．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int[] a;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int left=0, right=1500000;
  for(int i=0; i<100; i++){
   int mid=(left+right)/2;
   if(check(mid)){
    right=mid;
   }else{
    left=mid;
   }
  }
  println(""+right);
 }

 boolean check(int b){
  int d=1;
  int sum=0;
  for(int i=0; i<n; i++){
   if(a[i]>b){
    return false;
   }
   sum+=a[i];
   if(sum>b){
    sum=a[i];
    d++;
   }
  }
  return d<=m;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0180 Stellar Performance of the Debunkey Family

2011-02-24T00:10:00.000+09:00

■0180 Stellar Performance of the Debunkey Family

最小全域木．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 LinkedList<E> list;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   list=new LinkedList<E>();
   for(int i=0; i<m; i++){
    int a=sc.nextInt();
    int b=sc.nextInt();
    int cost=sc.nextInt();
    list.add(new E(a, b, cost));
   }
   solve();
  }
 }

 void solve(){
  E[] es=list.toArray(new E[0]);
  Arrays.sort(es);
  init();
  int wt=0;
  for(E e : es){
   if(find(e.v1)!=find(e.v2)){
    union(e.v1, e.v2);
    wt+=e.w;
   }
  }
  println(""+wt);
 }

 class E implements Comparable<E>{
  int v1, v2, w;

  E(int v1, int v2, int w){
   this.v1=v1;
   this.v2=v2;
   this.w=w;
  }

  @Override
  public int compareTo(E e){
   return w-e.w;
  }
 }

 int[] p, rank;

 void init(){
  p=new int[n];
  rank=new int[n];
  for(int i=0; i<n; i++){
   p[i]=i;
   rank[i]=0;
  }
 }

 int find(int x){
  if(p[x]==x)
   return x;
  else
   return p[x]=find(p[x]);
 }

 void union(int x, int y){
  x=find(x);
  y=find(y);
  if(rank[x]>rank[y]){
   p[y]=x;
  }else{
   p[x]=y;
   if(rank[x]==rank[y])
    rank[y]++;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0179 Mysterious Worm

2011-02-24T00:09:00.000+09:00

■0179 Mysterious Worm

深さ優先探索．同じ状態が何度も発生しないように，既に出た状態を集合に突っ込んでおくと良い(ただし，計算量がO(logn)であるものを用いないとTLEの可能性有)．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 String worm;

 void run(){
  for(;;){
   worm=sc.next();
   if(worm.equals("0")){
    break;
   }
   solve();
  }
 }

 void solve(){
  LinkedList<String> que=new LinkedList<String>();
  TreeSet<String> set=new TreeSet<String>();
  HashMap<String, Integer> map=new HashMap<String, Integer>();
  que.add(worm);
  set.add(worm);
  map.put(worm, 0);
  for(; !que.isEmpty();){
   String s=que.poll();
   boolean f=true;
   for(int i=0; i<s.length(); i++){
    f&=s.charAt(0)==s.charAt(i);
   }
   if(f){
    println(""+map.get(s));
    return;
   }
   for(String t : next(s)){
    if(!set.contains(t)){
     que.offer(t);
     set.add(t);
     map.put(t, map.get(s)+1);
    }
   }
  }
  println("NA");
 }

 LinkedList<String> next(String s){
  LinkedList<String> list=new LinkedList<String>();
  for(int i=0; i<s.length()-1; i++){
   if(s.charAt(i)!=s.charAt(i+1)){
    char c='*';
    switch(s.charAt(i)+s.charAt(i+1)){
    case 'r'+'g':
     c='b';
     break;
    case 'g'+'b':
     c='r';
     break;
    case 'b'+'r':
     c='g';
     break;
    }
    list.add(s.substring(0, i)+c+c
      +(i<s.length()-2?s.substring(i+2, s.length()):""));
   }
  }
  return list;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0176 What Color?

2011-02-22T23:10:00.001+09:00

■0176 What Color?

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   String s=sc.next();
   if(s.equals("0")){
    break;
   }
   int r=Integer.parseInt(s.substring(1, 3), 16);
   int g=Integer.parseInt(s.substring(3, 5), 16);
   int b=Integer.parseInt(s.substring(5, 7), 16);
   int k=-1;
   double min=INF;
   for(int i=0; i<8; i++){
    int dr=r-(i/4)*0xff;
    int dg=g-((i/2)%2)*0xff;
    int db=b-(i%2)*0xff;
    double d=Math.sqrt(dr*dr+dg*dg+db*db);
    if(d+EPS<min){
     k=i;
     min=d;
    }
   }
   println(new String[]{"black", "blue", "lime", "aqua", "red",
     "fuchsia", "yellow", "white",}[k]);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0175 A King in Hawaii

2011-02-22T23:10:00.000+09:00

■0175 A King in Hawaii

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int n=sc.nextInt();
   if(n==-1){
    break;
   }
   println(Integer.toString(n, 4));
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0174 Badminton

2011-02-22T23:09:00.002+09:00

■0174 Badminton

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 String[] ss;

 void run(){
  ss=new String[3];
  for(;;){
   ss[0]=sc.next();
   if(ss[0].equals("0")){
    break;
   }
   ss[1]=sc.next();
   ss[2]=sc.next();
   solve();
  }
 }

 void solve(){
  for(int j=0; j<3; j++){
   int a=0, b=0;
   for(int i=0; i<ss[j].length()-1; i++){
    if(ss[j].charAt(i+1)=='A'){
     a++;
    }else{
     b++;
    }
   }
   if((a+1==11&&b<=9)||(a+1>=12&&a+1==b+2)){
    a++;
   }else{
    b++;
   }
   println(a+" "+b);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0173 Haunted House

2011-02-22T23:09:00.001+09:00

■0173 Haunted House

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(int i=0; i<9; i++){
   String s=sc.next();
   int a=sc.nextInt();
   int b=sc.nextInt();
   println(s+" "+(a+b)+" "+(a*200+b*300));
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0170 Lunch

2011-02-22T23:09:00.000+09:00

■0170 Lunch

全探索．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 String[] f;
 int[] w, s;
 int[] a, best;
 double bestG;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   f=new String[n];
   w=new int[n];
   s=new int[n];
   for(int i=0; i<n; i++){
    f[i]=sc.next();
    w[i]=sc.nextInt();
    s[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  a=new int[n];
  best=new int[n];
  for(int i=0; i<n; i++){
   a[i]=i;
  }
  bestG=INF;
  rec(0);
  for(int e : best){
   println(f[e]);
  }
 }

 void rec(int j){
  if(j==n){
   int sumW=0;
   int nW=0;
   for(int i=n-1; i>=0; i--){
    if(s[a[i]]<sumW){
     return;
    }
    sumW+=w[a[i]];
    nW+=(i+1)*w[a[i]];
   }
   double g=(double)nW/sumW;
   if(g+EPS<bestG){
    System.arraycopy(a, 0, best, 0, n);
    bestG=g;
   }
   return;
  }

  for(int i=j; i<n; i++){
   int t=a[i];
   a[i]=a[j];
   a[j]=t;
   rec(j+1);
   t=a[i];
   a[i]=a[j];
   a[j]=t;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0169 Blackjack

2011-02-22T23:08:00.001+09:00

■0169 Blackjack

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   Scanner s=new Scanner(sc.nextLine());
   int count1=0;
   int sum=0;
   for(; s.hasNext();){
    int a=s.nextInt();
    if(a==0){
     return;
    }
    if(a>10){
     sum+=10;
    }else{
     sum+=a;
    }
    if(a==1){
     count1++;
    }
   }
   int ans=0;
   for(int i=0; i<=count1; i++){
    if(sum<=21){
     ans=sum;
    }
    sum+=10;
   }
   println(""+ans);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0168 Kannondou

2011-02-22T23:08:00.000+09:00

■0168 Kannondou

動的計画法．

dp[段数]=組み合わせ
dp[0]=1
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int n=sc.nextInt();
   if(n==0){
    break;
   }
   int[] dp=new int[n+4];
   dp[0]=1;
   for(int i=0; i<=n; i++){
    dp[i+1]+=dp[i];
    dp[i+2]+=dp[i];
    dp[i+3]+=dp[i];
   }
   int ans=((dp[n]+9)/10+364)/365;
   println(ans+"");
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0167 Bubble Sort

2011-02-22T23:07:00.000+09:00

■0167 Bubble Sort

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] a;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int swap=0;
  for(int j=n-1; j>=0; j--){
   for(int i=0; i<j; i++){
    if(a[i]>a[i+1]){
     int t=a[i];
     a[i]=a[i+1];
     a[i+1]=t;
     swap++;
    }
   }
  }
  println(""+swap);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0166 Area of Polygon

2011-02-22T23:06:00.001+09:00

■0166 Area of Polygon

中心角θの三角形の面積は，2sin(θ/2)

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   double[] area=new double[2];
   for(int j=0; j<2; j++){
    int m=sc.nextInt();
    if(m==0){
     return;
    }
    int sum=0;
    for(int i=0; i<m-1; i++){
     int deg=sc.nextInt();
     area[j]+=Math.sin(Math.toRadians(deg/2))*2;
     sum+=deg;
    }
    area[j]+=Math.sin(Math.toRadians(360-sum))/2;
   }
   if(area[0]>area[1]+EPS){
    println("1");
   }else if(area[0]+EPS<area[1]){
    println("2");
   }else{
    println("0");
   }
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0164 Ohajiki Game

2011-02-22T23:06:00.000+09:00

■0164 Ohajiki Game

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int n=sc.nextInt();
   if(n==0){
    break;
   }
   int[] a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   for(int r=31, i=0;; i=(i+1)%n){
    println(""+r);
    r-=a[i];
    if(r<=0){
     println("0");
     break;
    }
    println(""+r);
    r-=(r-1)%5;
   }
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0163 Highway Toll

2011-02-22T23:05:00.000+09:00

■0163 Highway Toll

やるだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  int[][] d={
    //
    {0, 6, 13, 18, 23, 43, 58}, //
    {6, 0, 7, 12, 17, 37, 52}, //
    {13, 7, 0, 5, 10, 30, 45}, //
    {18, 12, 5, 0, 5, 25, 40}, //
    {23, 17, 10, 5, 0, 20, 35}, //
    {43, 37, 30, 25, 20, 0, 15}, //
    {58, 52, 45, 40, 35, 15, 0}, //
  };
  int[][] c={
    //
    {0, 300, 500, 600, 700, 1350, 1650}, //
    {300, 0, 350, 450, 600, 1150, 1500}, //
    {500, 350, 0, 250, 400, 1000, 1350}, //
    {600, 450, 250, 0, 250, 850, 1300}, //
    {700, 600, 400, 250, 0, 600, 1150}, //
    {1350, 1150, 1000, 850, 600, 0, 500}, //
    {1650, 1500, 1350, 1300, 1150, 500, 0},}; //

  for(;;){
   int ic1=sc.nextInt()-1;
   if(ic1==-1){
    break;
   }
   int h1=sc.nextInt();
   int m1=sc.nextInt()+h1*60;
   int ic2=sc.nextInt()-1;
   int h2=sc.nextInt();
   int m2=sc.nextInt()+h2*60;
   int s=17*60+30;
   int g=19*60+30;
   int ans=c[ic1][ic2];
   if((s<=m1&&m1<=g)||(s<=m2&&m2<=g)){
    if(d[ic1][ic2]<=40){
     // 半額
     ans=(int)(Math.ceil(ans/2./50.)*50+EPS);
    }
   }
   println(""+ans);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0144 Packet Transportation

2011-02-22T23:04:00.000+09:00

■0144 Packet Transportation

BFSするだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int start, goal, ttl;
 LinkedList<Integer>[] graph;

 @SuppressWarnings("unchecked")
 void run(){
  n=sc.nextInt();
  graph=new LinkedList[n];
  for(int j=0; j<n; j++){
   int u=sc.nextInt()-1;// ルータ番号
   int m=sc.nextInt();
   graph[u]=new LinkedList<Integer>();
   for(int i=0; i<m; i++){
    int v=sc.nextInt()-1;
    graph[u].add(v);
   }
  }
  int p=sc.nextInt();
  for(int i=0; i<p; i++){
   start=sc.nextInt()-1;
   goal=sc.nextInt()-1;
   ttl=sc.nextInt();
   solve();
  }
 }

 void solve(){
  LinkedList<Integer> que=new LinkedList<Integer>();
  boolean[] visited=new boolean[n];
  int[] d=new int[n];
  Arrays.fill(d, INF);
  que.offer(start);
  d[start]=1;
  visited[start]=true;
  for(; !que.isEmpty();){
   int u=que.poll();
   for(int v : graph[u]){
    if(!visited[v]){
     que.offer(v);
     d[v]=d[u]+1;
     visited[v]=true;
    }
   }
  }
  if(d[goal]<=ttl){
   println(""+d[goal]);
  }else{
   println("NA");
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0143 Altair and Vega

2011-02-22T23:03:00.000+09:00

■0143 Altair and Vega

牽牛と織女を結ぶ線分が，三角形を構成する線分と何回交差するかで答えは決まる．

0，2回：遮断されていない
1回：遮断されている

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 P ps1, ps2, ps3;
 P k, s;

 void run(){
  n=sc.nextInt();
  for(int i=0; i<n; i++){
   int xp1=sc.nextInt();
   int yp1=sc.nextInt();
   int xp2=sc.nextInt();
   int yp2=sc.nextInt();
   int xp3=sc.nextInt();
   int yp3=sc.nextInt();
   int xk=sc.nextInt();
   int yk=sc.nextInt();
   int xs=sc.nextInt();
   int ys=sc.nextInt();
   ps1=new P(xp1, yp1);
   ps2=new P(xp2, yp2);
   ps3=new P(xp3, yp3);
   k=new P(xk, yk);
   s=new P(xs, ys);
   solve();
  }
 }

 void solve(){
  if(crsSS(k, s, ps1, ps2)^crsSS(k, s, ps2, ps3)^crsSS(k, s, ps3, ps1)){
   println("OK");
  }else{
   println("NG");
  }
 }

 boolean crsSS(P p1, P p2, P q1, P q2){
  if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))
   return false;
  if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))
   return false;
  if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))
   return false;
  if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))
   return false;
  return signum(p2.sub(p1).det(q1.sub(p1)))
    *signum(p2.sub(p1).det(q2.sub(p1)))<EPS
    &&signum(q2.sub(q1).det(p1.sub(q1)))
      *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;
 }

 class P{
  double x, y;

  P(){
   this(0, 0);
  }

  P(double x, double y){
   this.x=x;
   this.y=y;
  }

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0155 Spider Jin

2011-02-20T22:36:00.000+09:00

■0155 Spider Jin

最初にどのビルからどのビルへ移動することが出来るかの辺を張る．あとはDijkstraをしながら，あるビルの前に訪れるビルを逐一記録しておけば良い．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] b, x, y;
 int m;
 int[] s, g;
 HashMap<Integer, Integer> map;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   b=new int[n];
   x=new int[n];
   y=new int[n];
   for(int i=0; i<n; i++){
    b[i]=sc.nextInt();
    x[i]=sc.nextInt();
    y[i]=sc.nextInt();
   }
   m=sc.nextInt();
   s=new int[m];
   g=new int[m];
   for(int i=0; i<m; i++){
    s[i]=sc.nextInt();
    g[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  map=new HashMap<Integer, Integer>();
  for(int i=0; i<n; i++){
   map.put(b[i], i);
  }

  @SuppressWarnings("unchecked")
  LinkedList<E>[] es=new LinkedList[n];
  for(int j=0; j<n; j++){
   es[j]=new LinkedList<E>();
   for(int i=0; i<n; i++){
    if(i==j){
     continue;
    }
    double cost=Math.hypot(x[i]-x[j], y[i]-y[j]);
    if(cost<50+EPS){
     es[j].add(new E(i, cost));
    }
   }
  }
  for(int i=0; i<m; i++){
   LinkedList<Integer> path=dijkstra(es, map.get(s[i]), map.get(g[i]));
   if(path==null){
    println("NA");
   }else{
    for(int k=0; k<path.size(); k++){
     print(b[path.get(k)]+(k==path.size()-1?"\n":" "));
    }
   }
  }
 }

 LinkedList<Integer> dijkstra(LinkedList<E>[] es, int s, int g){
  int n=es.length;
  double[] d=new double[n];
  int[] pre=new int[n];
  PriorityQueue<P> que=new PriorityQueue<P>();

  Arrays.fill(d, INF);
  Arrays.fill(pre, -1);
  d[s]=0;
  pre[s]=s;
  que.offer(new P(s, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v]<p.d)
    continue;
   for(E e : es[p.v]){
    if(d[e.to]>d[p.v]+e.cost){
     pre[e.to]=p.v;
     d[e.to]=d[p.v]+e.cost;
     que.offer(new P(e.to, d[e.to]));
    }
   }
  }
  LinkedList<Integer> path=new LinkedList<Integer>();
  for(int i=g;; i=pre[i]){
   path.addFirst(i);
   if(i==-1){
    return null;
   }
   if(i==s){
    return path;
   }
  }
 }

 class E{
  int to;
  double cost;

  E(int to, double cost){
   this.to=to;
   this.cost=cost;
  }
 }

 class P implements Comparable<P>{
  int v;
  double d;

  P(int v, double d){
   this.v=v;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   if(d+EPS<p.d){
    return -1;
   }else if(d>p.d+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 0154 Sum of Cards

2011-02-20T22:35:00.000+09:00

■0154 Sum of Cards

動的計画法による解法．

dp[i]=総和がiとなるカードの組み合わせ
とすればよい．更新方法は↓参照．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, g;
 int[] a, b, n;

 void run(){
  for(;;){
   m=sc.nextInt();
   if(m==0){
    break;
   }
   a=new int[m];
   b=new int[m];
   for(int i=0; i<m; i++){
    a[i]=sc.nextInt();
    b[i]=sc.nextInt();
   }
   g=sc.nextInt();
   n=new int[g];
   for(int i=0; i<g; i++){
    n[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int max=1001;
  int[] dp=new int[max];
  int[] dp2=new int[max];
  dp[0]=1;
  for(int j=0; j<m; j++){
   System.arraycopy(dp, 0, dp2, 0, max);
   for(int i=0; i<b[j]; i++){
    for(int k=max-a[j]*(i+1)-1; k>=0; k--){
     dp[k+a[j]*(i+1)]+=dp2[k];
    }
   }
  }
  for(int i=0; i<g; i++){
   println(""+dp[n[i]]);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}