2011年9月11日日曜日

Codeforces Beta Round #86 Div. 1 Only

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

■A. A Grammar Lessons

問題

Petyaの作った言語は以下のBNFにより定義される.与えられた文字列がSentenceか判定せよ.

Sentence := Statement | AdjectiveM | AdjectiveF | NounM | NounF | VerbM | VerbF
Statement := (AdjectiveM* NounM VerbM*) | (AdjectiveF* NounF VerbF*)

AdjectiveM := "lios" | Alphabet AdjectiveM
AdjectiveF := "liala" | Alphabet AdjectiveF
NounM := "etr" | Alphabet NounM
NounF := "etra" | Alphabet NounF
VerbM := "initis" | Alphabet VerbM
VerbF := "inites" | Alphabet VerbF

Alphabet := "a"|"b"|"c"|…|"z"

解法

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

■B. Petr#

問題

文字列s,sbegin,sendが与えられる.
以下を満たす文字列tの個数を求めよ.
  • tはsの部分文字列
  • sbeginはtのprefix
  • sendはtのsuffix

解法

sにおいて,sbeginおよびsendを検索して,インデックスの候補を列挙する.
sbegin,sendに関するインデックスks,keについて,
s[ks]からsbeginがあり,
s[ke]からsendがあり,
ks≦ke かつ ks+|sbegin|≦ke+|send|
ならば,
s[ks],…,s[ke],…,s[ke+|send|-1]
が条件を満たす文字列.
条件を満たす文字列を逐一生成すると,TLEするので,
ハッシュを計算し,重複要素を取り除くことで高速化.
#86 Div. 1 B. Petr#

■Result

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

TopCoder SRM 517

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

2011年9月4日日曜日

Codeforces Beta Round #85 Div. 1 Only

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

■A. Petya and Inequiations

問題

n,x,yが与えられる.
a12+a22+…+an2≥x
a1+a2+…+an≤y
を満たす正整数の列
a1,a2,…,an
を求めよ.なければ,-1を返せ.

解法

a1+a2+…+an
の最小値はn.次に,
a1+a2+…+an=y
としたとき,
a12+a22+…+an2
の最大値は,
ak=1 (1≤k≤n-1)
an=y-(n-1)
のとき,この値(=(n-1)+(y-(n-1))2)がx以上なら数列(ak)が答え.
#85 Div. 1 A. Petya and Inequiations

■B. Petya and Divisors

問題

2つの数列
x1,…,xn
y1,…,yn
が与えられる.
各(xi, yi)について,
xi mod k=0 かつ (∀j:i-yi≤j<i) xj mod k ≠ 0
なる正整数kの数を求めよ.

解法

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

■Result

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

ドカーン.

2011年9月3日土曜日

TopCoder SRM 513

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

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つ組み (v1,v2,v3)は,決して上の条件を満たさない.
また,グループ1から2ノード(v1,v2とする)を選び, グループ1以外の任意の1ノード(uとする)を選んだとき,
(v1,v2,u),(v1,u,v2)
も上の条件を満たさない.
つまり,あるグループ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

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に戻れるかも知れないがしかし….

2011年8月25日木曜日

CodeChef August Cook-off 2011

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--
実に不本意な結果….

2011年8月10日水曜日

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

京都大学プログラミングコンテスト 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=p1p22は条件を満たさないことを使う (p1,p2は素数).
kn∈[A-B, A+B]となる最小のkを以下で求める.
k=max([(A-B)/n], 1)
そして,kn∈[A-B, A+B]である間,kをインクリメント.
ここで,kn=p11+rkp22+skm と表わすことが出来る.
1+rk < 2+sk
ならば,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
まぁまぁの成績.