2011年9月18日日曜日
Codeforces Beta Round #87 Div. 1 Only
Codeforces Beta Round #86 Div. 1 Only (9/16 0:00~2:00）
■A. Party
解法
グラフに注目したとき下のような列があったとする．A1->A2->…->AN
この列の中の任意の2ノードは， 同じグループに属することができないため， 最低でもNグループ必要だと分かる．
このようなNの中で最大のものNmaxを見つければ， 任意の列は，長さが高々Nmaxなので， Nmax個のグループに高々1人で振り分けることが出来る．
結局，Nmaxが答え．
#86 Div. 1 A. Party
■B. Lawnmower
解法
ジグザグに進んでいくため，貪欲に求めることが出来る．#86 Div. 1 B. Lawnmower
■Result
oo--- 1146pts. 256th1700→1717
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. 215th1684->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/-0191.33pts. 301th
■Rating
1645->16732011年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. 278th1689 -> 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/-150.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. 27th1631 -> 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. 78th1562 -> 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まぁまぁの成績．
2011年7月27日水曜日
TopCoder SRM 513
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枚引く．
1.明るい赤を引いた時(m枚)
2.青を引いた時(n-2m枚)
2.1.明るい赤を引いたとき(m枚)
2.2.青を引いたとき(n-2m-2枚)
2.3.明るい紫を引いたとき(1枚)
これらから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/-0429.5pts. 104th
おそらくDiv.1では過去最高の成績です．加えてMediumを解けたのが初めてです．
■Rating
1620 -> 1727大幅上昇．
2011年7月4日月曜日
TopCoder SRM 511
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
こんな感じ（22通り）．
逆に，うさぎが4匹，猫が2匹としても，上と同じよう構成ができるので，
結局2*22=8通り．
これは，5匹と2匹，6匹と2匹，…でも変わらない．
そのため，N=m+nと分かれる場合，
m≠nならば，2*2min(m,n)通り，
m=nならば，2m通り．
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/-0144.29pts. 491th
■Rating
1532 -> 1527微減．次は，TCO Round3ですが，個人的には気楽に挑戦したいと思っています．
2011年6月29日水曜日
TCO Algorithm Round2
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=Y YYN--XならX=N YNY--XならX=N YNN--XならX=N となる． 次に，ある素数の冪乗を考える． 例えば，M=9とすると，2の冪乗は2,4,8まで．この3つに着目した有効な文字列は， NNN YNN YYN YYY の4種類． つまり，p1, p2,…, prについて有効な文字列は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/-0196.11pts. 341th
辛くも逃げきることが出来ました．
■Rating
1431 -> 1530Round3進出+初YellowCoderです． 今年のICPCは国内予選で落ちてしまったので，中々にショックでしたが， 代わりにGoogleとTopCoder両方のTシャツをゲットできそうです．
2011年6月23日木曜日
Aizu Online Judge 1149 Cut the Cakes
■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
■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();
}
}
2011年6月20日月曜日
Aizu Online Judge 1156 Twirling Robot
■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
■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
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++に乗り換えるのも手だと思われます．
2011年6月19日日曜日
TCO Algorithm Round1
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/-0232.61pts. 837th
■Rating
1414 -> 1431残念…．
2011年6月7日火曜日
Aizu Online Judge 1155 How can I satisfy thee? Let me count the ways...
■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
■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
■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
■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
■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
■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);
}
}
}
}
2011年6月6日月曜日
IPSC 2011
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さんが画像でアップしていましたが，フラクタルな構造をしていました．思い付かなかった．
Google Code Jam 2011 Round2
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
全探索で解ける．愚直に実装すると，(x1, y1)-(x1, y1) からなる長方形の重心を求めるための計算量は， O(n5)となり(8分間では)絶対に間に合わない．
そこで，部分和を使う．
MX1(i, j)=Σ0≦k≦ia(k, j)k
MY1(i, j)=Σ0≦k≦ja(i, k)k
とする．
これで，ある行 or 列に対するある範囲の質量×位置の総和がO(1)で求まるため， 総計算量は、O(n4)になる．しかし，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(n3)になり間に合う．
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();
}
}
■Result
38pts. 756th
念願のTシャツゲットです．もう少し頑張れば，Round3に進めたかもしれないですが，ここ最近で最高レベルに集中出来たので良かったと思います．
TopCoder SRM 508
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/-0125.55pts. 406th
■Rating
1365 -> 1414微増．目標の1500にはいつ到達できるのか…．
2011年5月30日月曜日
CodeChef May Cook-off 2011
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これは酷い…．
2011年5月29日日曜日
TopCoder SRM 507
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/-0144.37pts. 683th
■Rating
1442 -> 1365前々回のレートに戻ってしまいました…．
2011年5月23日月曜日
Google Code Jam 2011 Round1B
せめて，Bは解いておこうかと．
時間tに対して，各ホットドッグ屋がD離れることが出来るかを判定する必要がある．
これは，ホットドッグ屋を左から見ていき，可能な限り左に寄せていくことで判定できる．
二分探索の上限の見積もりが甘くLargeでWAってしまった…．
■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
遅ればせながら，報告．
・PG=0の時は，PD=0でないといけない．
何故なら，PG=0ならば，全てのゲームで負けているから．
・PG=100の時は，PD=100でないといけない．
理由は上とほぼ同じ．
次に，勝率がPD[%]となる（今日の）最小のゲーム数を求める．
つまり，
PD/100*Dが整数となるような，最小のDを求める．
つまり，
D=100/gcd(PD,100)
である．
D≦Nならば，"Possible"．
PGについては，試合の勝敗を調整すれば基本的に実現可能．
まず，辞書単語を文字列の長さで分類します．
そして，リストの文字を順番に辞書全体に適用していきます．
その際，それぞれの辞書単語の開示状態は変わります．
この開示状態が等しいもので分類して，その集合で個々にDFSを行います．
集合の要素数が1になったら終わりです．
詳しい説明は，GCJ公式のContest Analysisを御覧下さい．
ちなみに，本番では解けませんでした．
20pts. 870th
どうにかRound2へ進出出来ます．
■A. FreeCell Statistics
まず，下記の2条件を満たすか調べる．・PG=0の時は，PD=0でないといけない．
何故なら，PG=0ならば，全てのゲームで負けているから．
・PG=100の時は，PD=100でないといけない．
理由は上とほぼ同じ．
次に，勝率がPD[%]となる（今日の）最小のゲーム数を求める．
つまり，
PD/100*Dが整数となるような，最小のDを求める．
つまり，
D=100/gcd(PD,100)
である．
D≦Nならば，"Possible"．
PGについては，試合の勝敗を調整すれば基本的に実現可能．
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へ進出出来ます．
2011年5月18日水曜日
TopCoder SRM 504.5
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/-0241.3pts. 299th
前回の教訓を生かし，1撃墜に止めました．
■Rating
1360 -> 1442黄色くなれるか…?!
2011年5月15日日曜日
TCO11 Algo Qual1
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(Tn2)の人を狙ったのですが，3回もミスしてしまいました．■Result
○○× +1 -3478.98pts. 332th
■Rating
1279 -> 1360600位以内なので，次のラウンドへ．Round1も残りたいですね．
2011年5月14日土曜日
UTPC 2011(東京大学プログラミングコンテスト)
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が心配です．
登録:
コメント (Atom)
