2011年9月25日日曜日

移転しました

http://d.hatena.ne.jp/todo314/
投稿者 時刻: 0 件のコメント:
ラベル:

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. 256th
1700→1717
投稿者 時刻: 0 件のコメント:
ラベル:

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

投稿者 時刻: 0 件のコメント:
ラベル:

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
投稿者 時刻: 0 件のコメント:
ラベル:

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

ドカーン．
投稿者 時刻: 0 件のコメント:
ラベル:

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
捻挫+打撲．
投稿者 時刻: 0 件のコメント:
ラベル:

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かどうかを判定せよ．

解法

やるだけ．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class A{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     void run(){  
  16.         long n=sc.nextLong();  
  17.         int c=0;  
  18.         for(; n>0; n/=10){  
  19.             if(n%10==4||n%10==7){  
  20.                 c++;  
  21.             }  
  22.         }  
  23.         boolean f=c>0;  
  24.         for(; c>0; c/=10){  
  25.             f&=c%10==4||c%10==7;  
  26.         }  
  27.         println(f?"YES":"NO");  
  28.     }  
  29.   
  30.     void println(String s){  
  31.         System.out.println(s);  
  32.     }  
  33.   
  34.     void print(String s){  
  35.         System.out.print(s);  
  36.     }  
  37.   
  38.     void debug(Object... os){  
  39.         System.err.println(Arrays.deepToString(os));  
  40.     }  
  41.   
  42.     public static void main(String[] args){  
  43.         new A().run();  
  44.     }  
  45. }  

■B. Lucky String

問題

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

解法

abcdabcd…
↑これをn文字出力するだけ．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class B{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     void run(){  
  16.         int n=sc.nextInt();  
  17.         StringBuffer sb=new StringBuffer("");  
  18.         for(int i=0; i<n;){  
  19.             for(char c='a'; c<='d'&&i<n; c++, i++){  
  20.                 sb.append(c);  
  21.             }  
  22.         }  
  23.         println(sb.toString());  
  24.     }  
  25.   
  26.     void println(String s){  
  27.         System.out.println(s);  
  28.     }  
  29.   
  30.     void print(String s){  
  31.         System.out.print(s);  
  32.     }  
  33.   
  34.     void debug(Object... os){  
  35.         System.err.println(Arrays.deepToString(os));  
  36.     }  
  37.   
  38.     public static void main(String[] args){  
  39.         new B().run();  
  40.     }  
  41. }  

■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は存在しない．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class C{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     int n;  
  16.   
  17.     void run(){  
  18.         n=sc.nextInt();  
  19.         for(int a=0; n-4*a>=0; a++){  
  20.             if((n-4*a)%7==0){  
  21.                 int b=(n-4*a)/7;  
  22.                 StringBuffer sb=new StringBuffer();  
  23.                 for(int i=0; i<a; i++){  
  24.                     sb.append('4');  
  25.                 }  
  26.                 for(int i=0; i<b; i++){  
  27.                     sb.append('7');  
  28.                 }  
  29.                 println(sb.toString());  
  30.                 return;  
  31.             }  
  32.         }  
  33.         println("-1");  
  34.     }  
  35.   
  36.     void println(String s){  
  37.         System.out.println(s);  
  38.     }  
  39.   
  40.     void print(String s){  
  41.         System.out.print(s);  
  42.     }  
  43.   
  44.     void debug(Object... os){  
  45.         System.err.println(Arrays.deepToString(os));  
  46.     }  
  47.   
  48.     public static void main(String[] args){  
  49.         new C().run();  
  50.     }  
  51. }  

■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を用いるのがスマートだと思われる．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class E{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     int n;  
  16.   
  17.     void run(){  
  18.         n=sc.nextInt();  
  19.         make(n);  
  20.   
  21.         for(int i=0; i<n-1; i++){  
  22.             int u=sc.nextInt()-1;  
  23.             int v=sc.nextInt()-1;  
  24.             int w=sc.nextInt();  
  25.             if(!isLucky(w)){  
  26.                 union(u, v);  
  27.             }  
  28.         }  
  29.   
  30.         debug(p);  
  31.   
  32.         long ans=0;  
  33.         for(int i=0; i<n; i++){  
  34.             long s=size(i);  
  35.             if(p[i]>=0){  
  36.                 continue;  
  37.             }  
  38.             if(s>=3){  
  39.                 ans+=s*(s-1)*(s-2);  
  40.             }  
  41.             if(s>=2){  
  42.                 ans+=s*(s-1)*(n-s)*2;  
  43.             }  
  44.         }  
  45.   
  46.         // debug(n*(n-1)*(n-2));  
  47.         // debug(ans);  
  48.         ans=(long)n*(n-1)*(n-2)-ans;  
  49.         println(ans+"");  
  50.     }  
  51.   
  52.     boolean isLucky(int n){  
  53.         for(; n>0; n/=10){  
  54.             if(n%10!=4&&n%10!=7){  
  55.                 return false;  
  56.             }  
  57.         }  
  58.         return true;  
  59.     }  
  60.   
  61.     int[] p;  
  62.   
  63.     void make(int n){  
  64.         p=new int[n];  
  65.         fill(p, -1);  
  66.     }  
  67.   
  68.     int find(int x){  
  69.         return p[x]<0?x:(p[x]=find(p[x]));  
  70.     }  
  71.   
  72.     boolean union(int x, int y){  
  73.         x=find(x);  
  74.         y=find(y);  
  75.         if(x!=y){  
  76.             if(p[y]<p[x]){  
  77.                 int t=x;  
  78.                 x=y;  
  79.                 y=t;  
  80.             }  
  81.             p[x]+=p[y];  
  82.             p[y]=x;  
  83.         }  
  84.         return x!=y;  
  85.     }  
  86.   
  87.     int size(int x){  
  88.         return -p[find(x)];  
  89.     }  
  90.   
  91.     void println(String s){  
  92.         System.out.println(s);  
  93.     }  
  94.   
  95.     void print(String s){  
  96.         System.out.print(s);  
  97.     }  
  98.   
  99.     void debug(Object... os){  
  100.         System.err.println(Arrays.deepToString(os));  
  101.     }  
  102.   
  103.     public static void main(String[] args){  
  104.         new E().run();  
  105.     }  
  106. }  

■Result

ooo-o 4068pts. 27th
1631 -> 1689
投稿者 時刻: 0 件のコメント:
ラベル:

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回の計算で終わるので，逐一試す．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class A{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     void run(){  
  16.         String[] ss=sc.next().split(":");  
  17.         int h=Integer.parseInt(ss[0]);  
  18.         int m=Integer.parseInt(ss[1]);  
  19.         for(;;){  
  20.             if(++m==60){  
  21.                 m=0;  
  22.                 if(++h==24){  
  23.                     h=0;  
  24.                 }  
  25.             }  
  26.             String s=String.format("%02d:%02d", h, m);  
  27.             if(new StringBuffer(s).reverse().toString().equals(s)){  
  28.                 println(s);  
  29.                 return;  
  30.             }  
  31.         }  
  32.     }  
  33.   
  34.     void println(String s){  
  35.         System.out.println(s);  
  36.     }  
  37.   
  38.     void print(String s){  
  39.         System.out.print(s);  
  40.     }  
  41.   
  42.     void debug(Object... os){  
  43.         System.err.println(Arrays.deepToString(os));  
  44.     }  
  45.   
  46.     public static void main(String[] args){  
  47.         new A().run();  
  48.     }  
  49. }  

■C. Dorm Water Supply

問題・解法

ある有向グラフが与えられる．
頂点には，多くとも1つの入る/出る辺があり，辺には情報として容量が与えられる．
以下を満たす（頂点V，頂点U，容量C）を求めよ．
  • Vには入る辺がない．
  • Uには出る辺がない．
  • Vから辺を辿ることで，Uに到着する．
  • Cは，VからUに至る辺の容量で最小のもの．
問題を意訳すると以上のようになるため，あとは書くだけです．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class C{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     int n, p;  
  16.     E[] es;  
  17.     int[] parent;  
  18.     LinkedList<E> answers;  
  19.     boolean[] visited;  
  20.   
  21.     class E{  
  22.         int from, to, cap;  
  23.   
  24.         E(int from, int to, int cap){  
  25.             this.from=from;  
  26.             this.to=to;  
  27.             this.cap=cap;  
  28.         }  
  29.     }  
  30.   
  31.     void run(){  
  32.         n=sc.nextInt();  
  33.         p=sc.nextInt();  
  34.         es=new E[n];  
  35.         answers=new LinkedList<E>();  
  36.         parent=new int[n];  
  37.         fill(parent, -1);  
  38.         for(int i=0; i<n; i++){}  
  39.         for(int i=0; i<p; i++){  
  40.             int a=sc.nextInt()-1;  
  41.             int b=sc.nextInt()-1;  
  42.             int d=sc.nextInt();  
  43.             es[a]=new E(a, b, d);  
  44.             parent[b]=a;  
  45.         }  
  46.         solve();  
  47.     }  
  48.   
  49.     void solve(){  
  50.         visited=new boolean[n];  
  51.         for(int i=0; i<n; i++){  
  52.             if(visited[i]){  
  53.                 continue;  
  54.             }  
  55.             int k=i;  
  56.             boolean loop=false;  
  57.             for(; parent[k]>=0;){  
  58.                 k=parent[k];  
  59.                 if(k==i){  
  60.                     loop=true;  
  61.                     break;  
  62.                 }  
  63.             }  
  64.             if(loop){  
  65.                 continue;  
  66.             }  
  67.             if(es[k]!=null){  
  68.                 visited[k]=true;  
  69.                 dfs(es[k].to, k, es[k].cap);  
  70.             }  
  71.         }  
  72.         E[] anss=answers.toArray(new E[0]);  
  73.         sort(anss, new Comparator<E>(){  
  74.             @Override  
  75.             public int compare(E e1, E e2){  
  76.                 return e1.from-e2.from;  
  77.             }  
  78.         });  
  79.         println(anss.length+"");  
  80.         for(E e : anss){  
  81.             println(e.from+" "+e.to+" "+e.cap);  
  82.         }  
  83.     }  
  84.   
  85.     void dfs(int v, int tank, int diameter){  
  86.         visited[v]=true;  
  87.         if(es[v]==null){  
  88.             answers.add(new E(tank+1, v+1, diameter));  
  89.             return;  
  90.         }  
  91.         dfs(es[v].to, tank, min(diameter, es[v].cap));  
  92.     }  
  93.   
  94.     void println(String s){  
  95.         System.out.println(s);  
  96.     }  
  97.   
  98.     void print(String s){  
  99.         System.out.print(s);  
  100.     }  
  101.   
  102.     void debug(Object... os){  
  103.         // System.err.println(Arrays.deepToString(os));  
  104.     }  
  105.   
  106.     public static void main(String[] args){  
  107.         new C().run();  
  108.     }  
  109. }  

■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)
と表せるので，ループ一つで求められる．
但し，精度が落ちないように工夫して計算する必要がある（下記コード参照）．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class D{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     int n, m, h;  
  16.     int[] s;  
  17.   
  18.     void run(){  
  19.         n=sc.nextInt();  
  20.         m=sc.nextInt();  
  21.         h=sc.nextInt()-1;  
  22.         s=new int[m];  
  23.         for(int i=0; i<m; i++){  
  24.             s[i]=sc.nextInt();  
  25.         }  
  26.         solve();  
  27.     }  
  28.   
  29.     void solve(){  
  30.         int sum=0;  
  31.         for(int i=0; i<m; i++){  
  32.             sum+=s[i];  
  33.         }  
  34.         if(sum<n){  
  35.             println("-1.0");  
  36.             return;  
  37.         }  
  38.         int k=s[h]-1;  
  39.         double ans=1;  
  40.         for(int i=0; i<k; i++){  
  41.             ans*=(double)(sum-n-i)/(sum-1-i);  
  42.         }  
  43.         println((1-ans)+"");  
  44.     }  
  45.   
  46.     void println(String s){  
  47.         System.out.println(s);  
  48.     }  
  49.   
  50.     void print(String s){  
  51.         System.out.print(s);  
  52.     }  
  53.   
  54.     void debug(Object... os){  
  55.         System.err.println(Arrays.deepToString(os));  
  56.     }  
  57.   
  58.     public static void main(String[] args){  
  59.         new D().run();  
  60.     }  
  61. }  

■Result

oxoo- 2816pts. 78th
1562 -> 1631
次回でDiv.1に戻れるかも知れないがしかし…．
投稿者 時刻: 0 件のコメント:
ラベル:

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個）
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     int t, n, a, b;  
  16.   
  17.     void run(){  
  18.         t=sc.nextInt();  
  19.         for(int i=0; i<t; i++){  
  20.             n=sc.nextInt();  
  21.             a=sc.nextInt();  
  22.             b=sc.nextInt();  
  23.             solve();  
  24.         }  
  25.     }  
  26.   
  27.     void solve(){  
  28.         int ans=0;  
  29.         int bitA=Integer.bitCount(a);  
  30.         int bitB=Integer.bitCount(b);  
  31.         if(bitA+bitB<=n){  
  32.             for(int i=0; i<n; i++){  
  33.                 ans<<=1;  
  34.                 if(i<bitA+bitB){  
  35.                     ans++;  
  36.                 }  
  37.             }  
  38.         }else{  
  39.             for(int i=0; i<n; i++){  
  40.                 ans<<=1;  
  41.                 if(i<2*n-(bitA+bitB)){  
  42.                     ans++;  
  43.                 }  
  44.             }  
  45.         }  
  46.         println(ans+"");  
  47.     }  
  48.   
  49.     void println(String s){  
  50.         System.out.println(s);  
  51.     }  
  52.   
  53.     void print(String s){  
  54.         System.out.print(s);  
  55.     }  
  56.   
  57.     void debug(Object... os){  
  58.         System.err.println(Arrays.deepToString(os));  
  59.     }  
  60.   
  61.     public static void main(String[] args){  
  62.         new Main().run();  
  63.     }  
  64. }  

■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する．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.     Scanner sc=new Scanner(System.in);  
  11.   
  12.     int INF=1<<28;  
  13.     double EPS=1e-9;  
  14.   
  15.     int n;  
  16.     int[] vote, ps;  
  17.   
  18.     void run(){  
  19.         for(;;){  
  20.             n=sc.nextInt();  
  21.             if(n==0){  
  22.                 break;  
  23.             }  
  24.             vote=new int[n];  
  25.             ps=new int[n];  
  26.             for(int i=0; i<n; i++){  
  27.                 vote[i]=sc.next().equals("P")?+1:-1;  
  28.                 ps[i]=sc.nextInt()-vote[i];  
  29.             }  
  30.             solve();  
  31.         }  
  32.     }  
  33.   
  34.     void solve(){  
  35.         int min=0;  
  36.         for(int i=0; i<n; i++){  
  37.             if(abs(ps[i]+min)%2==1){  
  38.                 min++;  
  39.             }  
  40.             min=max(min, abs(ps[i]));  
  41.         }  
  42.         println(min+"");  
  43.     }  
  44.   
  45.     void println(String s){  
  46.         System.out.println(s);  
  47.     }  
  48.   
  49.     void print(String s){  
  50.         System.out.print(s);  
  51.     }  
  52.   
  53.     void debug(Object... os){  
  54.         System.err.println(Arrays.deepToString(os));  
  55.     }  
  56.   
  57.     public static void main(String[] args){  
  58.         new Main().run();  
  59.     }  
  60. }  

■Result

o-o--
実に不本意な結果…．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年8月10日水曜日

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

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

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

■A KUPC

文字ごとの出現回数をカウントして，
min(count['K'], count['U'], count['P'], count['C'])
が答え．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5. import static java.lang.Math.*;  
  6. import static java.util.Arrays.*;  
  7.   
  8. public class Main{  
  9.     Scanner sc=new Scanner(System.in);  
  10.     int INF=1<<28;  
  11.     double EPS=1e-12;  
  12.   
  13.     void run(){  
  14.         String s=sc.next();  
  15.         int[] count=new int[256];  
  16.         for(char c : s.toCharArray()){  
  17.             count[c]++;  
  18.         }  
  19.         int ans=min(count['K'], min(count['U'], min(count['P'], count['C'])));  
  20.         println(ans+"");  
  21.     }  
  22.   
  23.     void debug(Object... os){  
  24.         System.err.println(Arrays.deepToString(os));  
  25.     }  
  26.   
  27.     void print(String s){  
  28.         System.out.print(s);  
  29.     }  
  30.   
  31.     void println(String s){  
  32.         System.out.println(s);  
  33.     }  
  34.   
  35.     public static void main(String[] args){  
  36.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  37.         new Main().run();  
  38.     }  
  39. }  

■B 蝉

典型的なDP．
dp[y][x] := (x,y)に到達までに出会う蝉の数の最小値
右か下にしかいけないので，(x,y)の左と上を見ればdp[y][x]を決定できる．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5. import static java.lang.Math.*;  
  6. import static java.util.Arrays.*;  
  7.   
  8. public class Main{  
  9.     Scanner sc=new Scanner(System.in);  
  10.     int INF=1<<28;  
  11.     double EPS=1e-12;  
  12.   
  13.     int n, m;  
  14.     int[][] a;  
  15.   
  16.     void run(){  
  17.         n=sc.nextInt();  
  18.         m=sc.nextInt();  
  19.         a=new int[n][m];  
  20.         for(int j=0; j<n; j++){  
  21.             String s=sc.next();  
  22.             for(int i=0; i<m; i++){  
  23.                 a[j][i]=s.charAt(i)-'0';  
  24.             }  
  25.         }  
  26.   
  27.         int[][] dp=new int[n][m];  
  28.         for(int j=0; j<n; j++){  
  29.             fill(dp[j], INF);  
  30.         }  
  31.         dp[0][0]=0;  
  32.         for(int j=0; j<n; j++){  
  33.             for(int i=0; i<m; i++){  
  34.                 if(j>0){  
  35.                     dp[j][i]=min(dp[j][i], dp[j-1][i]+a[j][i]);  
  36.                 }  
  37.                 if(i>0){  
  38.                     dp[j][i]=min(dp[j][i], dp[j][i-1]+a[j][i]);  
  39.                 }  
  40.             }  
  41.         }  
  42.         println(dp[n-1][m-1]+"");  
  43.     }  
  44.   
  45.     void debug(Object... os){  
  46.         System.err.println(Arrays.deepToString(os));  
  47.     }  
  48.   
  49.     void print(String s){  
  50.         System.out.print(s);  
  51.     }  
  52.   
  53.     void println(String s){  
  54.         System.out.println(s);  
  55.     }  
  56.   
  57.     public static void main(String[] args){  
  58.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  59.         new Main().run();  
  60.     }  
  61. }  

■C しりとり

'xa'と尋ね続ければ，その内，'a'で始まる文字列が無くなることを利用する．
途中で，不正な返答が来た時の処理等を忘れてWAを食らいまくる．
view plainprint?
  1. package c;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7. import static java.lang.Math.*;  
  8. import static java.util.Arrays.*;  
  9.   
  10. public class Main{  
  11.     Scanner sc=new Scanner(System.in);  
  12.     int INF=1<<28;  
  13.     double EPS=1e-12;  
  14.   
  15.     void run(){  
  16.         TreeSet<string> set=new TreeSet<string>();  
  17.         println("?a");  
  18.         System.out.flush();  
  19.         set.add("a");  
  20.         String next="";  
  21.         char ch='a';  
  22.         for(; sc.hasNext();){  
  23.             String s=sc.next();  
  24.             boolean out=false;  
  25.             out|=s.charAt(0)!='a';  
  26.             out|=set.contains(s);  
  27.             if(out){  
  28.                 println("!OUT");  
  29.                 break;  
  30.             }  
  31.             set.add(s);  
  32.             println("?"+s.charAt(s.length()-1)+next+ch+"a");  
  33.             if(ch++=='z'){  
  34.                 next+='z';  
  35.                 ch='a';  
  36.             }  
  37.             System.out.flush();  
  38.         }  
  39.     }  
  40.   
  41.     void debug(Object... os){  
  42.         System.err.println(Arrays.deepToString(os));  
  43.     }  
  44.   
  45.     void print(String s){  
  46.         System.out.print(s);  
  47.     }  
  48.   
  49.     void println(String s){  
  50.         System.out.println(s);  
  51.     }  
  52.   
  53.     public static void main(String[] args){  
  54.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  55.         new Main().run();  
  56.     }  
  57. }</string></string>  

■D 列の構成

ずっとやり方を考えていたが，DFS+適当な枝刈りで通ってしまった． 想定解法は乱択アルゴリズムという珍しい問題．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5. import static java.lang.Math.*;  
  6. import static java.util.Arrays.*;  
  7.   
  8. public class Main{  
  9.     Scanner sc=new Scanner(System.in);  
  10.     int INF=1<<28;  
  11.     double EPS=1e-12;  
  12.   
  13.     int n, k;  
  14.     int[][] a, sum;  
  15.     int[] count, seq;  
  16.     boolean[] brank;  
  17.     boolean end=false;  
  18.   
  19.     void run(){  
  20.         n=sc.nextInt();  
  21.         k=sc.nextInt();  
  22.         a=new int[k][n];  
  23.         brank=new boolean[n];  
  24.         sum=new int[k][n+1];  
  25.         fill(brank, true);  
  26.         for(int j=0; j<k; j++){  
  27.             for(int i=0; i<n/2; i++){  
  28.                 int k=sc.nextInt();  
  29.                 a[j][k-1]=1;  
  30.                 brank[k-1]=false;  
  31.             }  
  32.             for(int i=0; i<n; i++){  
  33.                 sum[j][i+1]=sum[j][i]+a[j][i];  
  34.             }  
  35.         }  
  36.         count=new int[k];  
  37.         seq=new int[n];  
  38.         rec(0);  
  39.     }  
  40.   
  41.     void rec(int x){  
  42.         if(end){  
  43.             return;  
  44.         }  
  45.   
  46.         // 枝刈り  
  47.         for(int j=0; j<k; j++){  
  48.             int rem=sum[j][n]-sum[j][x];  
  49.             if(count[j]+rem<n/8){  
  50.                 return;  
  51.             }  
  52.             if(count[j]>3*n/8){  
  53.                 return;  
  54.             }  
  55.         }  
  56.   
  57.         if(x==n){  
  58.             end=true;  
  59.             for(int i=0; i<n; i++){  
  60.                 print(seq[i]+"");  
  61.             }  
  62.             println("");  
  63.             return;  
  64.         }  
  65.   
  66.         if(brank[x]){  
  67.             rec(x+1);  
  68.             return;  
  69.         }  
  70.   
  71.         seq[x]=0;  
  72.         rec(x+1);  
  73.   
  74.         seq[x]=1;  
  75.         for(int j=0; j<k; j++){  
  76.             count[j]+=a[j][x];  
  77.         }  
  78.         rec(x+1);  
  79.         for(int j=0; j<k; j++){  
  80.             count[j]-=a[j][x];  
  81.         }  
  82.   
  83.     }  
  84.   
  85.     void debug(Object... os){  
  86.         System.err.println(Arrays.deepToString(os));  
  87.     }  
  88.   
  89.     void print(String s){  
  90.         System.out.print(s);  
  91.     }  
  92.   
  93.     void println(String s){  
  94.         System.out.println(s);  
  95.     }  
  96.   
  97.     public static void main(String[] args){  
  98.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  99.         new Main().run();  
  100.     }  
  101. }  

■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
これを妥当な範囲内の素数全てについて行う．
view plainprint?
  1. import java.util.*;  
  2. import java.util.Map.Entry;  
  3. import java.lang.*;  
  4. import java.math.*;  
  5. import java.io.*;  
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.     Scanner sc=new Scanner(System.in);  
  11.     int INF=1<<28;  
  12.     double EPS=1e-12;  
  13.   
  14.     long a;  
  15.     int b;  
  16.     int p, m;  
  17.     int[] prime;  
  18.     boolean[] isPrime;  
  19.     boolean[] fox;  
  20.   
  21.     void run(){  
  22.         a=sc.nextLong();  
  23.         b=sc.nextInt();  
  24.   
  25.         fox=new boolean[2*b+1];  
  26.         fill(fox, true);  
  27.           
  28.         for(int i=0;i<2*b+1;i++){  
  29.             if(i-b+a<2){  
  30.                 fox[i]=false;  
  31.             }  
  32.         }  
  33.   
  34.         m=(int)sqrt(a+b)+10;  
  35.         p=0;  
  36.         prime=new int[m];  
  37.         isPrime=new boolean[m+1];  
  38.         Arrays.fill(isPrime, true);  
  39.         isPrime[0]=isPrime[1]=false;  
  40.         for(int i=2; i<=m; i++){  
  41.             if(isPrime[i]){  
  42.                 prime[p++]=i;  
  43.                 for(int j=2*i; j<=m; j+=i)  
  44.                     isPrime[j]=false;  
  45.             }  
  46.         }  
  47.   
  48.         int e1=1, e2=2;  
  49.         for(int p2=0; p2<p; p2++){  
  50.             long n2=(long)prime[p2]*prime[p2];  
  51.             if(n2>a+b){  
  52.                 break;  
  53.             }  
  54.             for(int p1=0; p1<p2; p1++){  
  55.                 long n1=prime[p1];  
  56.                 long n=n1*n2;  
  57.                 if(n<0){  
  58.                     debug(n);  
  59.                 }  
  60.                 if(n>a+b){  
  61.                     break;  
  62.                 }  
  63.   
  64.                 int c=0;  
  65.                 for(long k=max((a-b)/n, 1); k*n<=a+b; k++){  
  66.                     c++;  
  67.                     int pc1=0;  
  68.                     for(long i=k; i%prime[p1]==0; i/=prime[p1]){  
  69.                         pc1++;  
  70.                     }  
  71.                     int pc2=0;  
  72.                     for(long i=k; i%prime[p2]==0; i/=prime[p2]){  
  73.                         pc2++;  
  74.                     }  
  75.   
  76.                     if(e1+pc1<e2+pc2){  
  77.                         if(k*n>=a-b){  
  78.                             fox[(int)(k*n-a+b)]=false;  
  79.                         }  
  80.                     }  
  81.                 }  
  82.             }  
  83.         }  
  84.   
  85.         int c=0;  
  86.         for(int i=0; i<2*b+1; i++){  
  87.             if(fox[i]){  
  88.                 c++;  
  89.             }  
  90.         }  
  91.   
  92.         println(c+"");  
  93.     }  
  94.   
  95.     void debug(Object... os){  
  96.         System.err.println(Arrays.deepToString(os));  
  97.     }  
  98.   
  99.     void print(String s){  
  100.         System.out.print(s);  
  101.     }  
  102.   
  103.     void println(String s){  
  104.         System.out.println(s);  
  105.     }  
  106.   
  107.     public static void main(String[] args){  
  108.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  109.         new Main().run();  
  110.     }  
  111. }  

■結果

ooooo----- 500pts. 17th
まぁまぁの成績．
投稿者 時刻: 1 件のコメント:
ラベル:

2011年7月27日水曜日

TopCoder SRM 513

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

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

■YetAnotherIncredibleMachine(Easy)

・解法

全探索．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class YetAnotherIncredibleMachine {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public int countWays(int[] mount, int[] length, int[] balls) {  
  15.   int n=length.length;  
  16.   int m=balls.length;  
  17.   long res=1;  
  18.   long mod=1000000009;  
  19.   for(int j=0;j<n;j++){   
  20.    int c=0;  
  21.    for(int x=-length[j];x<=0;x++){  
  22.     boolean f=true;  
  23.     for(int i=0;i<m;i++){  
  24.      if(mount[j]+x<=balls[i]&&balls[i]<=mount[j]+x+length[j]){  
  25.       f=false;  
  26.      }  
  27.     }  
  28.     if(f){  
  29.      c++;  
  30.     }  
  31.    }  
  32.    res=(res*c)%mod;  
  33.   }  
  34.   return (int)res;  
  35.  }  
  36.   
  37.  void debug(Object...os){  
  38.   System.err.println(Arrays.deepToString(os));  
  39.  }  
  40.   
  41.  void print(String s){  
  42.   System.out.print(s);  
  43.  }  
  44.   
  45.  void println(String s){  
  46.   System.out.println(s);  
  47.  }  
  48. }  
  49.   
  50.   
  51. // Powered by FileEdit  
  52. // Powered by TZTester 1.01 [25-Feb-2003]  
  53. // Powered by CodeProcessor  

■PerfectMemory(Medium)

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

解法

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

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

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

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

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

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

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

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

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

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

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

これらからDPテーブルを更新していきます．初期値の与え方が面倒なので，メモ化再帰でもいいかも知れません．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class PerfectMemory {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public double getExpectation(int N, int M) {  
  15.   int n=N*M;  
  16.   double[][] dp=new double[n+1][n+1];  
  17.   for(int j=2;j<=n;j+=2){  
  18.    for(int i=j;i>=j/2;i--){  
  19.     dp[j][i]=j/2;  
  20.    }  
  21.    for(int i=j/2-1;i>=0;i--){  
  22.     double p1=(double)(j-2*i)/(j-i);  
  23.     double p2=(double)i/(j-i);  
  24.     double q1=(double)i/(j-i-1);  
  25.     double q2=(double)(j-2*i-2)/(j-i-1);  
  26.     double q3=(double)1/(j-i-1);  
  27.     dp[j][i]+=(2+dp[j-2][i])*p1*q1;  
  28.     dp[j][i]+=(1+dp[j][i+2])*p1*q2;  
  29.     dp[j][i]+=(1+dp[j-2][i])*p1*q3;  
  30.     if(i>0){  
  31.      dp[j][i]+=(1+dp[j-2][i-1])*p2;  
  32.     }  
  33.    }  
  34.   }  
  35.   for(int i=0;i<=n;i+=2){  
  36.    // debug(i, dp[i]);  
  37.   }  
  38.   return dp[n][0];  
  39.  }  
  40.   
  41.  void debug(Object...os){  
  42.   System.err.println(Arrays.deepToString(os));  
  43.  }  
  44.   
  45.  void print(String s){  
  46.   System.out.print(s);  
  47.  }  
  48.   
  49.  void println(String s){  
  50.   System.out.println(s);  
  51.  }  
  52. }  
  53.   
  54.   
  55. // Powered by FileEdit  
  56. // Powered by TZTester 1.01 [25-Feb-2003]  
  57. // Powered by CodeProcessor  

■Challenge Phase

撃墜無し．

■Result

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

■Rating

1620 -> 1727
大幅上昇．
投稿者 時刻: 0 件のコメント:
ラベル:

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通り．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Zoo {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public long theCount(int[] a) {  
  15.   int n=a.length;  
  16.   int[] count=new int[n];  
  17.   for(int i:a){  
  18.    if(i>=n){  
  19.     return 0;  
  20.    }  
  21.    if(++count[i]>2){  
  22.     return 0;  
  23.    }  
  24.   }  
  25.   int p=0, q=0;  
  26.   int k=0;  
  27.   // debug(count);  
  28.   for(int i=n-1;i>=0;i--){  
  29.    if(count[i]==k+2){  
  30.     p=q=i+1;  
  31.    }  
  32.    else if(count[i]==k+1){  
  33.     if(k==0){  
  34.      p=i+1;  
  35.     }else if(k==1){  
  36.      q=i+1;  
  37.     }  
  38.    }  
  39.    else if(count[i]==k){  
  40.    }  
  41.    else{  
  42.     return 0;  
  43.    }  
  44.    k=count[i];  
  45.   }  
  46.   // debug(p,q);  
  47.   long ret=1;  
  48.   for(int i=0;i<min(p,q);i++){  
  49.    ret*=2;  
  50.   }  
  51.   return ret*(p!=q?2:1);  
  52.  }  
  53.   
  54.  void debug(Object...os){  
  55.   System.err.println(Arrays.deepToString(os));  
  56.  }  
  57.   
  58.  void print(String s){  
  59.   System.out.print(s);  
  60.  }  
  61.   
  62.  void println(String s){  
  63.   System.out.println(s);  
  64.  }  
  65. }  

■FiveHundredElevenAdd(Medium)

本番は解けませんでしたので，simezi_tanさんの記事を参照下さい．
SRM 511 Div1 Medium FiveHundredEleven - simezi_tanの日記
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class FiveHundredEleven {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  int[][] memo; // 0:win, 1:lose  
  15.  int[] cards;  
  16.  int n;  
  17.   
  18.  int rec(int step,int mem){  
  19.   if(memo[step][mem]>=0){  
  20.    return memo[step][mem];  
  21.   }  
  22.   if(mem==511){  
  23.    // former player loses.  
  24.    return memo[step][mem]=0;  
  25.   }  
  26.   if(step==n){  
  27.    // the player can't choose a card.  
  28.    return memo[step][mem]=1;  
  29.   }  
  30.   int not=0;  
  31.   for(int i=0;i<n;i++){  
  32.    if((mem|cards[i])==mem){  
  33.     not++;  
  34.    }  
  35.   }  
  36.   boolean win=false;  
  37.   // search : not-step cards that don't affect mem are not used  
  38.   if(not>step){  
  39.    win|=rec(step+1,mem)==1;  
  40.   }  
  41.   // search : cards that affect mem.  
  42.   for(int i=0;i<n;i++){  
  43.    if((mem|cards[i])!=mem){  
  44.     win|=rec(step+1,mem|cards[i])==1;  
  45.    }  
  46.   }  
  47.   return memo[step][mem]=win?0:1;  
  48.  }  
  49.   
  50.  public String theWinner(int[] cards) {  
  51.   this.cards=cards;  
  52.   n=cards.length;  
  53.   memo=new int[n+1][512];  
  54.   for(int i=0;i<n+1;i++){  
  55.    fill(memo[i],-1);  
  56.   }  
  57.   return rec(0,0)==0?"Fox Ciel":"Toastman";  
  58.  }  
  59.   
  60.  void debug(Object...os){  
  61.   System.err.println(Arrays.deepToString(os));  
  62.  }  
  63.   
  64.  void print(String s){  
  65.   System.out.print(s);  
  66.  }  
  67.   
  68.  void println(String s){  
  69.   System.out.println(s);  
  70.  }  
  71. }  

■Challenge Phase

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

■Result

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

■Rating

1532 -> 1527
微減．次は，TCO Round3ですが，個人的には気楽に挑戦したいと思っています．
投稿者 時刻: 0 件のコメント:
ラベル:

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種類． あとは，それらを掛け合わせるだけ．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class GuessTheNumberGame {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public int possibleClues(int n) {  
  15.   long res=1;  
  16.   long mod=1000000007;  
  17.   boolean[] isP=new boolean[n+1];  
  18.   int[] p=new int[n+1];  
  19.   fill(isP,true);  
  20.   isP[0]=isP[1]=false;  
  21.   int k=0;  
  22.   for(int j=0;j<=n;j++){  
  23.    if(!isP[j]){  
  24.     continue;  
  25.    }  
  26.    p[k++]=j;  
  27.    for(int i=j*2;i<=n;i+=j){  
  28.     isP[i]=false;  
  29.    }  
  30.   }  
  31.   // debug(p);  
  32.   for(int i=0;i<k;i++){  
  33.    int c=0;  
  34.    for(long m=1;m<=n;m*=p[i]){  
  35.     c++;  
  36.    }  
  37.    // debug(i,p[i],c);  
  38.    res=(res*c)%mod;  
  39.   }  
  40.   return (int)res;  
  41.  }  
  42.   
  43.  void debug(Object...os){  
  44.   System.err.println(Arrays.deepToString(os));  
  45.  }  
  46.   
  47.  void print(String s){  
  48.   System.out.print(s);  
  49.  }  
  50.   
  51.  void println(String s){  
  52.   System.out.println(s);  
  53.  }  
  54. }  

■Challenge Phase

撃墜無し．

■Result

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

■Rating

1431 -> 1530
Round3進出+初YellowCoderです． 今年のICPCは国内予選で落ちてしまったので，中々にショックでしたが， 代わりにGoogleとTopCoder両方のTシャツをゲットできそうです．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年6月23日木曜日

Aizu Online Judge 1149 Cut the Cakes

■1149 Cut the Cakes

やればできる．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int n, w, h;  
  17.  int[] ps, ss;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    n=sc.nextInt();  
  22.    w=sc.nextInt();  
  23.    h=sc.nextInt();  
  24.    if((n|w|h)==0){  
  25.     break;  
  26.    }  
  27.    ps=new int[n];  
  28.    ss=new int[n];  
  29.    for(int i=0; i<n; i++){  
  30.     ps[i]=sc.nextInt()-1;  
  31.     ss[i]=sc.nextInt();  
  32.    }  
  33.    solve();  
  34.   }  
  35.  }  
  36.   
  37.  void solve(){  
  38.   LinkedList<R> list=new LinkedList<R>();  
  39.   list.add(new R(0, 0, w, h));  
  40.   for(int i=0; i<n; i++){  
  41.    R r=list.remove(ps[i]);  
  42.    debug(i, r.x, r.y, r.w, r.h);  
  43.    int x=r.x, y=r.y;  
  44.    for(int k=0; k<ss[i]; k++){  
  45.     if(y==r.y&&x<r.x+r.w){  
  46.      x++;  
  47.     }else if(x==r.x+r.w&&y<r.y+r.h){  
  48.      y++;  
  49.     }else if(y==r.y+r.h&&x>r.x){  
  50.      x--;  
  51.     }else if(x==r.x&&y>r.y){  
  52.      y--;  
  53.     }else{  
  54.      debug("Error!");  
  55.     }  
  56.     // debug(x,y);  
  57.    }  
  58.    debug(x, y);  
  59.    R r1=null, r2=null;  
  60.    if(x==r.x||x==r.x+r.w){  
  61.     r1=new R(r.x, r.y, r.w, y-r.y);  
  62.     r2=new R(r.x, r.y+r1.h, r.w, r.h-r1.h);  
  63.    }else{  
  64.     r1=new R(r.x, r.y, x-r.x, r.h);  
  65.     r2=new R(r.x+r1.w, r.y, r.w-r1.w, r.h);  
  66.    }  
  67.    debug("r1", r1.x, r1.y, r1.w, r1.h);  
  68.    debug("r2", r2.x, r2.y, r2.w, r2.h);  
  69.    if(r1.w*r1.h<r2.w*r2.h){  
  70.     list.add(r1);  
  71.     list.add(r2);  
  72.    }else{  
  73.     list.add(r2);  
  74.     list.add(r1);  
  75.    }  
  76.   }  
  77.   R[] rs=list.toArray(new R[0]);  
  78.   sort(rs);  
  79.   String ans="";  
  80.   for(R r : rs){  
  81.    ans+=(r.w*r.h)+" ";  
  82.    debug(r.x, r.y, r.w, r.h, r.w*r.h);  
  83.   }  
  84.   println(ans.substring(0, ans.length()-1));  
  85.  }  
  86.   
  87.  class R implements Comparable<R>{  
  88.   int x, y, w, h;  
  89.   
  90.   R(int x, int y, int w, int h){  
  91.    this.x=x;  
  92.    this.y=y;  
  93.    this.w=w;  
  94.    this.h=h;  
  95.   }  
  96.   
  97.   @Override  
  98.   public int compareTo(R r){  
  99.    return w*h-r.w*r.h;  
  100.   }  
  101.  }  
  102.   
  103.  void debug(Object... os){  
  104.   // System.err.println(Arrays.deepToString(os));  
  105.  }  
  106.   
  107.  void print(String s){  
  108.   System.out.print(s);  
  109.  }  
  110.   
  111.  void println(String s){  
  112.   System.out.println(s);  
  113.  }  
  114.   
  115.  public static void main(String[] args){  
  116.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  117.   new Main().run();  
  118.  }  
  119. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1131 Unit Fraction Partition

■1131 Unit Fraction Partition

自明な+ちょっと工夫した枝刈りでAC．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int p0, q0, maxA, maxN;  
  17.  int ans;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    p0=sc.nextInt();  
  22.    q0=sc.nextInt();  
  23.    maxA=sc.nextInt();  
  24.    maxN=sc.nextInt();  
  25.    if((p0|q0|maxA|maxN)==0){  
  26.     break;  
  27.    }  
  28.    solve();  
  29.   }  
  30.  }  
  31.   
  32.  void solve(){  
  33.   int gcd=gcd(p0, q0);  
  34.   p0/=gcd;  
  35.   q0/=gcd;  
  36.   ans=0;  
  37.   dfs(0, 1, 1, 1, 0);  
  38.   // debug(ans);  
  39.   println(""+ans);  
  40.  }  
  41.   
  42.  void dfs(int p, int q, int qNow, int a, int n){  
  43.   if(n>maxN){  
  44.    return;  
  45.   }  
  46.   if(a>maxA){  
  47.    return;  
  48.   }  
  49.   if(p*q0-q*p0>0){  
  50.    return;  
  51.   }  
  52.   {  
  53.    int p2=maxN-n;  
  54.    int q2=qNow;  
  55.    int pp=p*q2+q*p2;  
  56.    int qq=q*q2;  
  57.    if(pp*q0-qq*p0<0){  
  58.     return;  
  59.    }  
  60.   }  
  61.   // debug(p,q,qNow,a,n);  
  62.   if(p==p0&&q==q0){  
  63.    ans++;  
  64.    return;  
  65.   }  
  66.   for(int i=qNow; i*a<=maxA; i++){  
  67.    int p2=p*i+q;  
  68.    int q2=q*i;  
  69.    int gcd=gcd(p2, q2);  
  70.    p2/=gcd;  
  71.    q2/=gcd;  
  72.    dfs(p2, q2, i, i*a, n+1);  
  73.   }  
  74.  }  
  75.   
  76.  int gcd(int m, int n){  
  77.   for(; m!=0;){  
  78.    int t=n%m;  
  79.    n=m;  
  80.    m=t;  
  81.   }  
  82.   return n;  
  83.  }  
  84.   
  85.  void debug(Object... os){  
  86.   System.err.println(Arrays.deepToString(os));  
  87.  }  
  88.   
  89.  void print(String s){  
  90.   System.out.print(s);  
  91.  }  
  92.   
  93.  void println(String s){  
  94.   System.out.println(s);  
  95.  }  
  96.   
  97.  public static void main(String[] args){  
  98.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  99.   new Main().run();  
  100.  }  
  101. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年6月20日月曜日

Aizu Online Judge 1156 Twirling Robot

■1156 Twirling Robot

(x座標，y座標，方向ベクトル)を状態としたDijkstra．コストのつけ方が特殊だが，少し注意すれば特に問題無い．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int m, n;  
  17.  int[][] a;  
  18.  int[] c;  
  19.   
  20.  void run(){  
  21.   for(;;){  
  22.    m=sc.nextInt();  
  23.    n=sc.nextInt();  
  24.    if((m|n)==0){  
  25.     break;  
  26.    }  
  27.    a=new int[n][m];  
  28.    for(int j=0; j<n; j++){  
  29.     for(int i=0; i<m; i++){  
  30.      a[j][i]=sc.nextInt();  
  31.     }  
  32.    }  
  33.    c=new int[4];  
  34.    for(int i=0; i<4; i++){  
  35.     c[i]=sc.nextInt();  
  36.    }  
  37.    solve();  
  38.   }  
  39.  }  
  40.   
  41.  void solve(){  
  42.   int[][][] d=new int[n][m][4];  
  43.   for(int j=0; j<n; j++){  
  44.    for(int i=0; i<m; i++){  
  45.     fill(d[j][i], INF);  
  46.    }  
  47.   }  
  48.   int[] dx={1, 0, -1, 0};  
  49.   int[] dy={0, 1, 0, -1};  
  50.   PriorityQueue<P> que=new PriorityQueue<P>();  
  51.   que.offer(new P(0, 0, 0));  
  52.   d[0][0][0]=0;  
  53.   for(; !que.isEmpty();){  
  54.    P p=que.poll();  
  55.    if(p.d>d[p.y][p.x][p.v]){  
  56.     continue;  
  57.    }  
  58.    int[] cost=c.clone();  
  59.    if(a[p.y][p.x]!=4){  
  60.     cost[a[p.y][p.x]]=0;  
  61.    }  
  62.    for(int i=0; i<4; i++){  
  63.     P q=new P(p.x, p.y, (p.v+i)%4);  
  64.     q.x+=dx[q.v];  
  65.     q.y+=dy[q.v];  
  66.     if(q.x<0||q.x>=m||q.y<0||q.y>=n){  
  67.      continue;  
  68.     }  
  69.     if(d[q.y][q.x][q.v]>d[p.y][p.x][p.v]+cost[i]){  
  70.      q.d=d[q.y][q.x][q.v]=d[p.y][p.x][p.v]+cost[i];  
  71.      que.offer(q);  
  72.     }  
  73.    }  
  74.   }  
  75.   int ans=INF;  
  76.   for(int i=0; i<4; i++){  
  77.    ans=min(ans, d[n-1][m-1][i]);  
  78.   }  
  79.   println(ans+"");  
  80.  }  
  81.   
  82.  class P implements Comparable<P>{  
  83.   int x, y, v;  
  84.   int d;  
  85.   
  86.   P(int x, int y, int v){  
  87.    this.x=x;  
  88.    this.y=y;  
  89.    this.v=v;  
  90.   }  
  91.   
  92.   @Override  
  93.   public int compareTo(P p){  
  94.    return d-p.d;  
  95.   }  
  96.  }  
  97.   
  98.  void debug(Object... os){  
  99.   System.err.println(Arrays.deepToString(os));  
  100.  }  
  101.   
  102.  void print(String s){  
  103.   System.out.print(s);  
  104.  }  
  105.   
  106.  void println(String s){  
  107.   System.out.println(s);  
  108.  }  
  109.   
  110.  public static void main(String[] args){  
  111.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  112.   new Main().run();  
  113.  }  
  114. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1136 Polygonal Line Search

■1136 Polygonal Line Search

回転および平行移動を適用したということは，各々の線分ベクトルを0,90,180,270°の何れかの角度回転させたことになる．従って，元の折れ線の内の1つの線分ベクトルと，探す対象の折れ線の内の1つの線分ベクトルを見れば何度回転させたか分かる．あとは，残りの線分ベクトルを回転させ，元の折れ線の線分ベクトルに一致するかを見ていけば良い．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int n;  
  17.  int[] m;  
  18.  int[][] xs, ys;  
  19.   
  20.  void run(){  
  21.   for(;;){  
  22.    n=sc.nextInt();  
  23.    if(n==0){  
  24.     break;  
  25.    }  
  26.    m=new int[n+1];  
  27.    xs=new int[n+1][];  
  28.    ys=new int[n+1][];  
  29.    for(int j=0; j<=n; j++){  
  30.     m[j]=sc.nextInt();  
  31.     xs[j]=new int[m[j]];  
  32.     ys[j]=new int[m[j]];  
  33.     for(int i=0; i<m[j]; i++){  
  34.      xs[j][i]=sc.nextInt();  
  35.      ys[j][i]=sc.nextInt();  
  36.     }  
  37.    }  
  38.    solve();  
  39.   }  
  40.  }  
  41.   
  42.  void solve(){  
  43.   for(int i=1; i<=n; i++){  
  44.    if(m[0]==m[i]&&match(m[0], xs[0], ys[0], xs[i], ys[i])){  
  45.     println(i+"");  
  46.    }  
  47.   }  
  48.   println("+++++");  
  49.  }  
  50.   
  51.  boolean match(int m, int[] xs1, int[] ys1, int[] xs2, int[] ys2){  
  52.   int[][][] a={{{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}},  
  53.     {{0, 1}, {-1, 0}}};  
  54.   
  55.   int k1=-1, k2=-1;  
  56.   for(int j=0; j<4; j++){  
  57.    int vx1=xs1[1]-xs1[0];  
  58.    int vy1=ys1[1]-ys1[0];  
  59.    int vx2=xs2[1]-xs2[0];  
  60.    int vy2=ys2[1]-ys2[0];  
  61.    if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx2  
  62.      &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy2){  
  63.     k1=j;  
  64.    }  
  65.    int vx3=xs2[m-2]-xs2[m-1];  
  66.    int vy3=ys2[m-2]-ys2[m-1];  
  67.    if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx3  
  68.      &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy3){  
  69.     k2=j;  
  70.    }  
  71.   }  
  72.   
  73.   boolean f1=k1!=-1, f2=k2!=-1;  
  74.   for(int i=0; i<m-1; i++){  
  75.    int vx1=xs1[i+1]-xs1[i];  
  76.    int vy1=ys1[i+1]-ys1[i];  
  77.    int vx2=xs2[i+1]-xs2[i];  
  78.    int vy2=ys2[i+1]-ys2[i];  
  79.    int vx3=xs2[m-i-2]-xs2[m-i-1];  
  80.    int vy3=ys2[m-i-2]-ys2[m-i-1];  
  81.    if(k1!=-1){  
  82.     f1&=vx1*a[k1][0][0]+vy1*a[k1][0][1]==vx2  
  83.       &&vx1*a[k1][1][0]+vy1*a[k1][1][1]==vy2;  
  84.    }  
  85.    if(k2!=-1){  
  86.     f2&=vx1*a[k2][0][0]+vy1*a[k2][0][1]==vx3  
  87.       &&vx1*a[k2][1][0]+vy1*a[k2][1][1]==vy3;  
  88.    }  
  89.   }  
  90.   
  91.   return f1||f2;  
  92.  }  
  93.   
  94.  void debug(Object... os){  
  95.   System.err.println(Arrays.deepToString(os));  
  96.  }  
  97.   
  98.  void print(String s){  
  99.   System.out.print(s);  
  100.  }  
  101.   
  102.  void println(String s){  
  103.   System.out.println(s);  
  104.  }  
  105.   
  106.  public static void main(String[] args){  
  107.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  108.   new Main().run();  
  109.  }  
  110. }  
投稿者 時刻: 0 件のコメント:
ラベル:

CodeChef June Cook-off 2011

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

■Correctness of Knight Move

やるだけ．出力をバッファリングしないとTLEします（しました）．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.  Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  int n;  
  16.  String s;  
  17.   
  18.  void run(){  
  19.   n=sc.nextInt();  
  20.   sc.nextLine();  
  21.   String[] ans={"Yes", "No", "Error"};  
  22.   for(int i=0; i<n; i++){  
  23.    s=sc.nextLine();  
  24.    println(ans[solve()]);  
  25.   }  
  26.   System.out.flush();  
  27.  }  
  28.   
  29.  int solve(){  
  30.   boolean legal=true;  
  31.   if(s.length()!=5){  
  32.    return 2;  
  33.   }  
  34.   legal&='a'<=s.charAt(0)&&s.charAt(0)<='h';  
  35.   legal&='1'<=s.charAt(1)&&s.charAt(1)<='8';  
  36.   legal&=s.charAt(2)=='-';  
  37.   legal&='a'<=s.charAt(3)&&s.charAt(3)<='h';  
  38.   legal&='1'<=s.charAt(4)&&s.charAt(4)<='8';  
  39.   if(!legal){  
  40.    return 2;  
  41.   }  
  42.   int x1=s.charAt(0)-'a';  
  43.   int y1=s.charAt(1)-'1';  
  44.   int x2=s.charAt(3)-'a';  
  45.   int y2=s.charAt(4)-'1';  
  46.   
  47.   int dx=abs(x1-x2);  
  48.   int dy=abs(y1-y2);  
  49.   
  50.   return (dx==1&&dy==2)||(dx==2&&dy==1)?0:1;  
  51.  }  
  52.   
  53.  void println(String s){  
  54.   System.out.println(s);  
  55.  }  
  56.   
  57.  void print(String s){  
  58.   System.out.print(s);  
  59.  }  
  60.   
  61.  void debug(Object... os){  
  62.   System.err.println(Arrays.deepToString(os));  
  63.  }  
  64.   
  65.  public static void main(String[] args){  
  66.   System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  67.   new Main().run();  
  68.  }  
  69. }  

■Super-plane

Dunnoの挙動は分岐無しなので，適当なループで解けます．コンテスト中は勘違いしていて，BFSをしようとしてTLE食らいまくっていました．さらに，Javaの入出力がバッファリングしてなかったため，少し調整しないと通りませんでした．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.  // Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  int t, n;  
  16.  int cs, ts, cg, tg;  
  17.  E[] es;  
  18.   
  19.  void run() throws Exception{  
  20.   BufferedReader br=new BufferedReader(new InputStreamReader(System.in));  
  21.   t=Integer.parseInt(br.readLine());  
  22.   for(; t>0; t--){  
  23.    n=Integer.parseInt(br.readLine());  
  24.    es=new E[n];  
  25.    for(int i=0; i<n; i++){  
  26.     String[] ss=br.readLine().split(" ");  
  27.     int c1=Integer.parseInt(ss[0])-1;  
  28.     int t1=Integer.parseInt(ss[1]);  
  29.     int c2=Integer.parseInt(ss[2])-1;  
  30.     int t2=Integer.parseInt(ss[3]);  
  31.     es[i]=new E(c1, t1, c2, t2);  
  32.    }  
  33.    sort(es);  
  34.    String[] ss=br.readLine().split(" ");  
  35.    cs=Integer.parseInt(ss[0])-1;  
  36.    ts=Integer.parseInt(ss[1]);  
  37.    cg=Integer.parseInt(ss[2])-1;  
  38.    tg=Integer.parseInt(ss[3]);  
  39.    solve();  
  40.   }  
  41.   System.out.flush();  
  42.  }  
  43.   
  44.  void solve(){  
  45.   P p=new P(cs, ts);  
  46.   boolean[] visited=new boolean[n];  
  47.   int ans=0;  
  48.   boolean ok=true;  
  49.   E key=new E(p.c, p.t, 0, 0);  
  50.   for(;; ans++){  
  51.    if(p.c==cg&&p.t<=tg){  
  52.     break;  
  53.    }  
  54.    key.c1=p.c;  
  55.    key.t1=p.t;  
  56.    int k=binarySearch(es, key);  
  57.    if(k<0){  
  58.     k=-1-k;  
  59.    }  
  60.    if(k==n){  
  61.     ok=false;  
  62.     break;  
  63.    }  
  64.    if(es[k].c1!=p.c){  
  65.     ok=false;  
  66.     break;  
  67.    }  
  68.    if(visited[k]){  
  69.     ok=false;  
  70.     break;  
  71.    }  
  72.    visited[k]=true;  
  73.    p.c=es[k].c2;  
  74.    p.t=es[k].t2;  
  75.   }  
  76.   if(ok){  
  77.    println("Yes "+ans);  
  78.   }else{  
  79.    println("No");  
  80.   }  
  81.  }  
  82.   
  83.  class E implements Comparable<E>{  
  84.   int c1, t1, c2, t2;  
  85.   
  86.   E(int c1, int t1, int c2, int t2){  
  87.    this.c1=c1;  
  88.    this.t1=t1;  
  89.    this.c2=c2;  
  90.    this.t2=t2;  
  91.   }  
  92.   
  93.   @Override  
  94.   public int compareTo(E e){  
  95.    if(c1!=e.c1){  
  96.     return c1-e.c1;  
  97.    }else{  
  98.     return t1-e.t1;  
  99.    }  
  100.   }  
  101.  }  
  102.   
  103.  class P implements Comparable<P>{  
  104.   int c, t;  
  105.   
  106.   P(int c, int t){  
  107.    this.c=c;  
  108.    this.t=t;  
  109.   }  
  110.   
  111.   @Override  
  112.   public int compareTo(P p){  
  113.    if(c!=p.c){  
  114.     return c-p.c;  
  115.    }else{  
  116.     return t-p.t;  
  117.    }  
  118.   }  
  119.  }  
  120.   
  121.  void println(String s){  
  122.   System.out.println(s);  
  123.  }  
  124.   
  125.  void print(String s){  
  126.   System.out.print(s);  
  127.  }  
  128.   
  129.  void debug(Object... os){  
  130.   System.err.println(Arrays.deepToString(os));  
  131.  }  
  132.   
  133.  public static void main(String[] args){  
  134.   System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  135.   try{  
  136.    new Main().run();  
  137.   }catch(Exception e){  
  138.    e.printStackTrace();  
  139.   }  
  140.  }  
  141. }  

■Result

--o--

またもやこれは酷い…．CodeChefとは相性が悪いようです．C++に乗り換えるのも手だと思われます．
投稿者 時刻: 0 件のコメント:
ラベル:

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に変更するためのポップの回数の最小値を返せ．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class TripleStrings {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public int getMinimumOperations(String init, String goal) {  
  15.   int n=init.length();  
  16.   int max=0;  
  17.   for(int j=1;j<=n;j++){  
  18.    boolean f=true;  
  19.    for(int i=0;i<j;i++){  
  20.     f&=init.charAt(n-j+i)==goal.charAt(i);  
  21.    }  
  22.    if(f){  
  23.     max=max(max,j);  
  24.    }  
  25.   }  
  26.   return (n-max)*2;  
  27.  }  
  28.   
  29.  void debug(Object...os){  
  30.   System.err.println(Arrays.deepToString(os));  
  31.  }  
  32.   
  33.  void print(String s){  
  34.   System.out.print(s);  
  35.  }  
  36.   
  37.  void println(String s){  
  38.   System.out.println(s);  
  39.  }  
  40. }  

■Challenge Phase

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

■Result

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

■Rating

1414 -> 1431
残念…．
投稿者 時刻: 0 件のコメント:
ラベル:

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通りなので，全部試せば良い．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  String s;  
  15.  int[] map;  
  16.   
  17.  void run(){  
  18.   for(;;){  
  19.    s=sc.next();  
  20.    if(s.equals(".")){  
  21.     break;  
  22.    }  
  23.    solve();  
  24.   }  
  25.  }  
  26.   
  27.  void solve(){  
  28.   map=new int[256];  
  29.   map['0']=0;  
  30.   map['1']=1;  
  31.   map['2']=2;  
  32.   int ans=0;  
  33.   for(int p=0; p<3; p++){  
  34.    for(int q=0; q<3; q++){  
  35.     for(int r=0; r<3; r++){  
  36.      map['P']=p;  
  37.      map['Q']=q;  
  38.      map['R']=r;  
  39.      Result res=f(0);  
  40.      if(res.value==2){  
  41.       ans++;  
  42.      }  
  43.     }  
  44.    }  
  45.   }  
  46.   println(ans+"");  
  47.  }  
  48.   
  49.  Result f(int p){  
  50.   // debug("f",p);  
  51.   if(Character.isDigit(s.charAt(p))||Character.isUpperCase(s.charAt(p))){  
  52.    return new Result(p+1, map[s.charAt(p)]);  
  53.   }else if(s.charAt(p)=='-'){  
  54.    Result r=f(p+1);  
  55.    r.value=2-r.value;  
  56.    return r;  
  57.   }else{  
  58.    Result r=f(p+1);  
  59.    Result r2=f(r.p+1); // skip '*' or '+'  
  60.    if(s.charAt(r.p)=='*'){  
  61.     r.value=min(r.value, r2.value);  
  62.    }else{ // '+'  
  63.     r.value=max(r.value, r2.value);  
  64.    }  
  65.    r.p=r2.p+1;  
  66.    return r;  
  67.   }  
  68.  }  
  69.   
  70.  class Result{  
  71.   int p, value;  
  72.   
  73.   Result(int p, int value){  
  74.    this.p=p;  
  75.    this.value=value;  
  76.   }  
  77.  }  
  78.   
  79.  void debug(Object... os){  
  80.   System.err.println(Arrays.deepToString(os));  
  81.  }  
  82.   
  83.  void print(String s){  
  84.   System.out.print(s);  
  85.  }  
  86.   
  87.  void println(String s){  
  88.   System.out.println(s);  
  89.  }  
  90.   
  91.  public static void main(String[] args){  
  92.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  93.   new Main().run();  
  94.  }  
  95. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1244 Molecular Formula

■1244 Molecular Formula

構文解析ゲー．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  HashMap<String, Integer> map;  
  15.  String s;  
  16.  boolean unknown;  
  17.   
  18.  void run(){  
  19.   map=new HashMap<String, Integer>();  
  20.   for(;;){  
  21.    String s=sc.next();  
  22.    if(s.equals("END_OF_FIRST_PART")){  
  23.     break;  
  24.    }  
  25.    int n=sc.nextInt();  
  26.    map.put(s, n);  
  27.   }  
  28.   for(;;){  
  29.    s=sc.next();  
  30.    if(s.equals("0")){  
  31.     break;  
  32.    }  
  33.    s+='\0';  
  34.    unknown=false;  
  35.    Result r=molecule(0);  
  36.    println(unknown?"UNKNOWN":r.value+"");  
  37.    debug(r.p, r.value);  
  38.   }  
  39.  }  
  40.   
  41.  Result molecule(int p){  
  42.   debug("molecule", p);  
  43.   Result r=new Result(p, 0);  
  44.   for(;;){  
  45.    if(s.charAt(r.p)=='\0'||s.charAt(r.p)==')'){  
  46.     // end of molecule  
  47.     return r;  
  48.    }else if(s.charAt(r.p)=='('){  
  49.     Result r1=molecule(r.p+1);  
  50.     Result r2=number(r1.p+1); // skip '('  
  51.     r.value+=r1.value*r2.value;  
  52.     r.p=r2.p;  
  53.    }else{  
  54.     Result r1=atom(r.p);  
  55.     Result r2=number(r1.p);  
  56.     r.value+=r1.value*r2.value;  
  57.     r.p=r2.p;  
  58.    }  
  59.   }  
  60.  }  
  61.   
  62.  Result atom(int p){  
  63.   debug("atom", p);  
  64.   String atom="";  
  65.   if(Character.isUpperCase(s.charAt(p))){  
  66.    atom+=s.charAt(p);  
  67.    p++;  
  68.    if(Character.isLowerCase(s.charAt(p))){  
  69.     atom+=s.charAt(p);  
  70.     p++;  
  71.    }  
  72.   }  
  73.   debug(atom);  
  74.   if(map.containsKey(atom)){  
  75.    return new Result(p, map.get(atom));  
  76.   }else{  
  77.    unknown=true;  
  78.    return new Result(p, 0);  
  79.   }  
  80.  }  
  81.   
  82.  Result number(int p){  
  83.   debug("number", p);  
  84.   int value=0;  
  85.   if(Character.isDigit(s.charAt(p))){  
  86.    value=s.charAt(p)-'0';  
  87.    p++;  
  88.    if(Character.isDigit(s.charAt(p))){  
  89.     value=value*10+s.charAt(p)-'0';  
  90.     p++;  
  91.    }  
  92.   }else{  
  93.    return new Result(p, 1);  
  94.   }  
  95.   return new Result(p, value);  
  96.  }  
  97.   
  98.  class Result{  
  99.   int p, value;  
  100.   
  101.   Result(int p, int value){  
  102.    this.p=p;  
  103.    this.value=value;  
  104.   }  
  105.  }  
  106.   
  107.  void debug(Object... os){  
  108.   // System.err.println(Arrays.deepToString(os));  
  109.  }  
  110.   
  111.  void print(String s){  
  112.   System.out.print(s);  
  113.  }  
  114.   
  115.  void println(String s){  
  116.   System.out.println(s);  
  117.  }  
  118.   
  119.  public static void main(String[] args){  
  120.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  121.   new Main().run();  
  122.  }  
  123. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1012 Operations with Finite Sets

■1012 Operations with Finite Sets

構文解析ゲー．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  int INF=1<<28;  
  15.  double EPS=1e-9;  
  16.  TreeSet<Integer>[] sets;  
  17.  String exp;  
  18.  TreeSet<Integer> U;  
  19.   
  20.  @SuppressWarnings("unchecked")  
  21.  void run(){  
  22.   for(; sc.hasNext();){  
  23.    sets=new TreeSet[256];  
  24.    for(char c='A'; c<='E'; c++){  
  25.     sets[c]=new TreeSet<Integer>();  
  26.    }  
  27.    U=new TreeSet<Integer>();  
  28.    for(;;){  
  29.     char c=sc.next().charAt(0);  
  30.     int n=sc.nextInt();  
  31.     if(c=='R'&&n==0){  
  32.      break;  
  33.     }  
  34.     for(int i=0; i<n; i++){  
  35.      int e=sc.nextInt();  
  36.      sets[c].add(e);  
  37.      U.add(e);  
  38.     }  
  39.    }  
  40.    exp=sc.next();  
  41.    solve();  
  42.   }  
  43.  }  
  44.   
  45.  void solve(){  
  46.   exp+='\0';  
  47.   Result r=e(0);  
  48.   debug(r.set.toArray());  
  49.   if(r.set.size()==0){  
  50.    println("NULL");  
  51.   }else{  
  52.    for(Iterator<Integer> it=r.set.iterator(); it.hasNext();){  
  53.     print(it.next()+(it.hasNext()?" ":"\n"));  
  54.    }  
  55.   }  
  56.  }  
  57.   
  58.  Result e(int p){  
  59.   debug("e", p);  
  60.   Result r=f(p);  
  61.   debug(r.set.toArray(), r.p);  
  62.   for(;;){  
  63.    if(op(exp.charAt(r.p))){  
  64.     Result r2=f(r.p+1);  
  65.     switch(exp.charAt(r.p)){  
  66.     case 'u': // or  
  67.      r.set.addAll(r2.set);  
  68.      break;  
  69.     case 'i': // and  
  70.      for(int e : U){  
  71.       if(r.set.contains(e)&&r2.set.contains(e)){}else{  
  72.        r.set.remove(e);  
  73.       }  
  74.      }  
  75.      break;  
  76.     case 'd': // diff  
  77.      r.set.removeAll(r2.set);  
  78.      break;  
  79.     case 's': // sym  
  80.      for(int e : U){  
  81.       if(r.set.contains(e)&&r2.set.contains(e)){  
  82.        r.set.remove(e);  
  83.       }else if(r2.set.contains(e)){  
  84.        r.set.add(e);  
  85.       }  
  86.      }  
  87.      break;  
  88.     }  
  89.     r.p=r2.p;  
  90.    }else{  
  91.     break;  
  92.    }  
  93.   }  
  94.   return r;  
  95.  }  
  96.   
  97.  boolean op(char c){  
  98.   return c=='u'||c=='i'||c=='d'||c=='s';  
  99.  }  
  100.   
  101.  Result f(int p){  
  102.   debug("f", p);  
  103.   if(exp.charAt(p)=='c'){  
  104.    Result r=f(p+1);  
  105.    TreeSet<Integer> c=new TreeSet<Integer>();  
  106.    for(int e : U){  
  107.     if(!r.set.contains(e)){  
  108.      c.add(e);  
  109.     }  
  110.    }  
  111.    r.set.clear();  
  112.    r.set.addAll(c);  
  113.    return r;  
  114.   }else{  
  115.    return t(p);  
  116.   }  
  117.  }  
  118.   
  119.  Result t(int p){  
  120.   debug("t", p);  
  121.   if(exp.charAt(p)=='('){  
  122.    Result r=e(p+1);  
  123.    r.p++; // skip ')'  
  124.    return r;  
  125.   }else{  
  126.    Result r=new Result(p+1);  
  127.    r.set.addAll(sets[exp.charAt(p)]);  
  128.    return r;  
  129.   }  
  130.  }  
  131.   
  132.  class Result{  
  133.   int p;  
  134.   TreeSet<Integer> set;  
  135.   
  136.   Result(int p){  
  137.    this.p=p;  
  138.    set=new TreeSet<Integer>();  
  139.   }  
  140.  }  
  141.   
  142.  void debug(Object... os){  
  143.   // System.err.println(Arrays.deepToString(os));  
  144.  }  
  145.   
  146.  void print(String s){  
  147.   System.out.print(s);  
  148.  }  
  149.   
  150.  void println(String s){  
  151.   System.out.println(s);  
  152.  }  
  153.   
  154.  public static void main(String[] args){  
  155.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  156.   new Main().run();  
  157.  }  
  158. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1162 Discrete Speed

■1162 Discrete Speed

拡張ダイクストラ．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  int INF=1<<28;  
  15.  double EPS=1e-9;  
  16.   
  17.  int n, m;  
  18.  int s, g;  
  19.  LinkedList<E>[] es;  
  20.   
  21.  @SuppressWarnings("unchecked")  
  22.  void run(){  
  23.   for(;;){  
  24.    n=sc.nextInt();  
  25.    m=sc.nextInt();  
  26.    if((n|m)==0){  
  27.     break;  
  28.    }  
  29.    es=new LinkedList[n];  
  30.    for(int i=0; i<n; i++){  
  31.     es[i]=new LinkedList<E>();  
  32.    }  
  33.    s=sc.nextInt()-1;  
  34.    g=sc.nextInt()-1;  
  35.    for(int i=0; i<m; i++){  
  36.     int x=sc.nextInt()-1;  
  37.     int y=sc.nextInt()-1;  
  38.     int d=sc.nextInt();  
  39.     int c=sc.nextInt();  
  40.     es[x].add(new E(y, d, c));  
  41.     es[y].add(new E(x, d, c));  
  42.    }  
  43.    solve();  
  44.   }  
  45.  }  
  46.   
  47.  void solve(){  
  48.   // [前][今][前から今の速度]  
  49.   double[][][] d=new double[n][n][40];  
  50.   PriorityQueue<P> que=new PriorityQueue<P>();  
  51.   for(int j=0; j<n; j++){  
  52.    for(int i=0; i<n; i++){  
  53.     fill(d[j][i], INF);  
  54.    }  
  55.   }  
  56.   d[s][s][1]=0;  
  57.   que.offer(new P(s, s, 0, 0));  
  58.   for(; !que.isEmpty();){  
  59.    P p=que.poll();  
  60.    if(d[p.q][p.p][p.v]+EPS<p.d){  
  61.     continue;  
  62.    }  
  63.    for(E e : es[p.p]){  
  64.     if(p.q==e.to){  
  65.      continue;  
  66.     }  
  67.     for(int i=-1; i<=1; i++){  
  68.      if(p.v+i<=0||p.v+i>e.c){  
  69.       continue;  
  70.      }  
  71.      if(d[p.p][e.to][p.v+i]>p.d+(double)e.d/(p.v+i)+EPS){  
  72.       d[p.p][e.to][p.v+i]=p.d+(double)e.d/(p.v+i);  
  73.       que.offer(new P(p.p, e.to, p.v+i, d[p.p][e.to][p.v+i]));  
  74.      }  
  75.     }  
  76.    }  
  77.   }  
  78.   double min=INF;  
  79.   for(int i=0; i<n; i++){  
  80.    min=min(min, d[i][g][1]);  
  81.   }  
  82.   println(""+(min<INF/2?min:"unreachable"));  
  83.  }  
  84.   
  85.  class E{  
  86.   int to, d, c;  
  87.   
  88.   E(int to, int d, int c){  
  89.    this.to=to;  
  90.    this.d=d;  
  91.    this.c=c;  
  92.   }  
  93.  }  
  94.   
  95.  class P implements Comparable<P>{  
  96.   int q, p, v;  
  97.   double d;  
  98.   
  99.   P(int q, int p, int v, double d){  
  100.    this.q=q;  
  101.    this.p=p;  
  102.    this.v=v;  
  103.    this.d=d;  
  104.   }  
  105.   
  106.   @Override  
  107.   public int compareTo(P p){  
  108.    if(d+EPS<p.d){  
  109.     return -1;  
  110.    }else if(d>p.d+EPS){  
  111.     return 1;  
  112.    }else{  
  113.     return 0;  
  114.    }  
  115.   }  
  116.   
  117.  }  
  118.   
  119.  void debug(Object... os){  
  120.   System.err.println(Arrays.deepToString(os));  
  121.  }  
  122.   
  123.  void print(String s){  
  124.   System.out.print(s);  
  125.  }  
  126.   
  127.  void println(String s){  
  128.   System.out.println(s);  
  129.  }  
  130.   
  131.  public static void main(String[] args){  
  132.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  133.   new Main().run();  
  134.  }  
  135. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1161 Verbal Arithmetic

■1161 Verbal Arithmetic

非常に汚い探索による解法．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  int INF=1<<28;  
  15.  double EPS=1e-9;  
  16.   
  17.  int n;  
  18.  String[] ss;  
  19.   
  20.  void run(){  
  21.   for(;;){  
  22.    n=sc.nextInt();  
  23.    if(n==0){  
  24.     break;  
  25.    }  
  26.    ss=new String[n];  
  27.    for(int i=0; i<n; i++){  
  28.     ss[i]=sc.next();  
  29.    }  
  30.    solve();  
  31.   }  
  32.  }  
  33.   
  34.  int size;  
  35.  int[] cs;  
  36.  int[] map;  
  37.  boolean[] used;  
  38.  int ans;  
  39.   
  40.  void solve(){  
  41.   int[] a=new int[256];  
  42.   fill(a, -1);  
  43.   size=0;  
  44.   for(String s : ss){  
  45.    for(int i=0; i<s.length(); i++){  
  46.     if(a[s.charAt(i)]==-1){  
  47.      size++;  
  48.      a[s.charAt(i)]=INF;  
  49.     }  
  50.     a[s.charAt(i)]=min(a[s.charAt(i)], s.length()-1-i);  
  51.    }  
  52.   }  
  53.   cs=new int[size];  
  54.   for(int k=0, i=0; i<256; i++){  
  55.    if(a[i]>=0){  
  56.     cs[k++]=i+1000*a[i];  
  57.    }  
  58.   }  
  59.   sort(cs);  
  60.   
  61.   used=new boolean[10];  
  62.   map=new int[256];  
  63.   fill(map, -1);  
  64.   ans=0;  
  65.   dfs(0);  
  66.   println(""+ans);  
  67.  }  
  68.   
  69.  void dfs(int k){  
  70.   if(k==size){  
  71.    if(ok(8)){  
  72.     ans++;  
  73.    }  
  74.    return;  
  75.   }  
  76.   for(int i=0; i<10; i++){  
  77.    if(!used[i]){  
  78.     used[i]=true;  
  79.     map[cs[k]%1000]=i;  
  80.     if(ok(cs[k]/1000)){  
  81.      dfs(k+1);  
  82.     }  
  83.     map[cs[k]%1000]=-1;  
  84.     used[i]=false;  
  85.    }  
  86.   }  
  87.  }  
  88.   
  89.  boolean ok(int d){  
  90.   int sum=0;  
  91.   for(int j=0; j<n; j++){  
  92.    if(map[ss[j].charAt(0)]==0&&ss[j].length()>1){  
  93.     return false;  
  94.    }  
  95.    int num=0;  
  96.    for(int i=max(0, d-ss[j].length()); i<d; i++){  
  97.     num=num*10+map[ss[j].charAt(ss[j].length()-d+i)];  
  98.    }  
  99.    if(j==n-1){  
  100.     sum-=num;  
  101.    }else{  
  102.     sum+=num;  
  103.    }  
  104.   }  
  105.   int mod=1;  
  106.   for(int i=0; i<d; i++){  
  107.    mod*=10;  
  108.   }  
  109.   return sum%mod==0;  
  110.  }  
  111.   
  112.  void debug(Object... os){  
  113.   System.err.println(Arrays.deepToString(os));  
  114.  }  
  115.   
  116.  void print(String s){  
  117.   System.out.print(s);  
  118.  }  
  119.   
  120.  void println(String s){  
  121.   System.out.println(s);  
  122.  }  
  123.   
  124.  public static void main(String[] args){  
  125.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  126.   new Main().run();  
  127.  }  
  128. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1133 Water Tank

■1133 Water Tank

実装ゲー．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import javax.swing.*;  
  7. import java.awt.*;  
  8.   
  9. import static java.lang.Math.*;  
  10. import static java.util.Arrays.*;  
  11.   
  12. // AC  
  13. public class Main{  
  14.   
  15.  Scanner sc=new Scanner(System.in);  
  16.   
  17.  int INF=1<<28;  
  18.  double EPS=1e-6;  
  19.   
  20.  int d;  
  21.  int n;  
  22.  int[] x, h;  
  23.  int m;  
  24.  int[] f, dv;  
  25.  int l;  
  26.  int[] p, t;  
  27.   
  28.  void run(){  
  29.   d=sc.nextInt();  
  30.   for(int k=0; k<d; k++){  
  31.    n=sc.nextInt()+1;  
  32.    x=new int[n+1];  
  33.    h=new int[n+1];  
  34.    x[0]=0;  
  35.    x[n]=100;  
  36.    h[0]=h[n]=50;  
  37.    for(int i=1; i<n; i++){  
  38.     x[i]=sc.nextInt();  
  39.     h[i]=sc.nextInt();  
  40.    }  
  41.    m=sc.nextInt();  
  42.    f=new int[m];  
  43.    dv=new int[m];  
  44.    for(int i=0; i<m; i++){  
  45.     f[i]=sc.nextInt();  
  46.     dv[i]=sc.nextInt();  
  47.    }  
  48.    l=sc.nextInt();  
  49.    p=new int[l];  
  50.    t=new int[l];  
  51.    for(int i=0; i<l; i++){  
  52.     p[i]=sc.nextInt();  
  53.     t[i]=sc.nextInt();  
  54.    }  
  55.    solve();  
  56.   }  
  57.  }  
  58.   
  59.  double[] y, a;  
  60.  double time;  
  61.   
  62.  void solve(){  
  63.   y=new double[n];  
  64.   a=new double[n];  
  65.   for(int j=0; j<m; j++){  
  66.    for(int i=0; i<n; i++){  
  67.     if(x[i]<f[j]&&f[j]<x[i+1]){  
  68.      a[i]+=dv[j]/30.0;  
  69.     }  
  70.    }  
  71.   }  
  72.   // Visualizer v=new Visualizer();  
  73.   
  74.   double[] ans=new double[l];  
  75.   fill(ans, -1);  
  76.   
  77.   for(time=0;;){  
  78.    double min=INF;  
  79.    for(int i=0; i<n; i++){  
  80.     if(a[i]>EPS){  
  81.      if(y[i]+EPS<h[i]){  
  82.       min=min(min, (h[i]-y[i])*(x[i+1]-x[i])/a[i]);  
  83.      }  
  84.      if(y[i]+EPS<h[i+1]){  
  85.       min=min(min, (h[i+1]-y[i])*(x[i+1]-x[i])/a[i]);  
  86.      }  
  87.     }  
  88.    }  
  89.    if(min==INF){  
  90.     for(;;);  
  91.    }  
  92.    for(int j=0; j<l; j++){  
  93.     if(time<t[j]+EPS&&t[j]+EPS<time+min){  
  94.      for(int i=0; i<n; i++){  
  95.       if(x[i]<p[j]&&p[j]<x[i+1]){  
  96.        ans[j]=min(y[i]+(t[j]-time)*a[i]/(x[i+1]-x[i]), 50);  
  97.       }  
  98.      }  
  99.     }  
  100.    }  
  101.    boolean all50=true;  
  102.    time+=min;  
  103.    for(int i=0; i<n; i++){  
  104.     y[i]+=min*a[i]/(x[i+1]-x[i]);  
  105.     all50&=abs(y[i]-50)<EPS;  
  106.    }  
  107.    // v.repaint();  
  108.    // sleep(1000);  
  109.   
  110.    if(all50){  
  111.     break;  
  112.    }  
  113.    double[] a2=new double[n];  
  114.   
  115.    for(int j=0; j<n; j++){  
  116.     boolean[] bottom=new boolean[n];  
  117.     int left, right;  
  118.     for(left=j; left>=0&&y[left]+EPS>h[left]; left--);  
  119.     for(right=j; right<n&&y[right]+EPS>h[right+1]; right++);  
  120.   
  121.     if(y[left]+EPS<y[j]){  
  122.      for(int i=left; i<n&&abs(y[i]-y[left])<EPS; i++){  
  123.       bottom[i]=true;  
  124.      }  
  125.     }  
  126.     if(y[right]+EPS<y[j]){  
  127.      for(int i=right; i>=0&&abs(y[i]-y[right])<EPS; i--){  
  128.       bottom[i]=true;  
  129.      }  
  130.     }  
  131.     if(abs(y[left]-y[j])<EPS&&abs(y[right]-y[j])<EPS){  
  132.      for(int i=left; i<=right; i++){  
  133.       bottom[i]=true;  
  134.      }  
  135.     }  
  136.     int sum=0;  
  137.     for(int i=0; i<n; i++){  
  138.      if(bottom[i]){  
  139.       sum+=x[i+1]-x[i];  
  140.      }  
  141.     }  
  142.     for(int i=0; i<n; i++){  
  143.      if(bottom[i]){  
  144.       a2[i]+=a[j]/sum*(x[i+1]-x[i]);  
  145.      }  
  146.     }  
  147.    }  
  148.    a=a2.clone();  
  149.   }  
  150.   for(int i=0; i<l; i++){  
  151.    println(ans[i]+EPS<0?"50.0":ans[i]+"");  
  152.   }  
  153.  }  
  154.   
  155.  void sleep(long millis){  
  156.   try{  
  157.    Thread.sleep(millis);  
  158.   }catch(InterruptedException e){  
  159.    e.printStackTrace();  
  160.   }  
  161.  }  
  162.   
  163.  void debug(Object... os){  
  164.   // System.err.println(Arrays.deepToString(os));  
  165.  }  
  166.   
  167.  void print(String s){  
  168.   System.out.print(s);  
  169.  }  
  170.   
  171.  void println(String s){  
  172.   System.out.println(s);  
  173.  }  
  174.   
  175.  public static void main(String[] args){  
  176.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  177.   new Main().run();  
  178.  }  
  179.   
  180.  public class Visualizer extends JFrame{  
  181.   Visualizer(){  
  182.    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);  
  183.    setVisible(true);  
  184.    getContentPane().add(new MainPanel(), BorderLayout.CENTER);  
  185.    pack();  
  186.   }  
  187.   
  188.   class MainPanel extends JPanel{  
  189.    MainPanel(){  
  190.     setPreferredSize(new Dimension(512, 512));  
  191.    }  
  192.   
  193.    public void paintComponent(Graphics g){  
  194.     int width=getWidth();  
  195.     int height=getHeight();  
  196.     for(int i=0; i<n; i++){  
  197.      g.setColor(Color.BLUE);  
  198.      g.fillRect(x[i]*4, height-(int)(y[i]*4), (x[i+1]-x[i])*4,  
  199.        (int)(y[i]*4));  
  200.      g.drawString(String.format("%.4f", a[i]), x[i]*4, height/2);  
  201.     }  
  202.   
  203.     for(int i=0; i<=n; i++){  
  204.      g.setColor(Color.RED);  
  205.      g.drawLine(x[i]*4, height-h[i]*4, x[i]*4, height);  
  206.     }  
  207.   
  208.     g.setColor(Color.BLACK);  
  209.     g.drawString(""+time, 100, 100);  
  210.    }  
  211.   }  
  212.  }  
  213. }  
投稿者 時刻: 0 件のコメント:
ラベル:

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さんが画像でアップしていましたが，フラクタルな構造をしていました．思い付かなかった．
投稿者 時刻: 0 件のコメント:
ラベル:

UAPC 2011

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

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

■A. It's our delight!!

やるだけ．

■K. Rearranging Seats

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

■Result

2AC 74th
駄目駄目でした．
投稿者 時刻: 0 件のコメント:
ラベル:

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]になるように気をつける．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class A{  
  10.  Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  int caze;  
  16.  int TT;  
  17.  int x, s, r, t, n;  
  18.  int[] b, e, w;  
  19.   
  20.  void run(){  
  21.   TT=sc.nextInt();  
  22.   for(caze=1; caze<=TT; caze++){  
  23.    x=sc.nextInt();  
  24.    s=sc.nextInt();  
  25.    r=sc.nextInt();  
  26.    t=sc.nextInt();  
  27.    n=sc.nextInt();  
  28.    b=new int[n];  
  29.    e=new int[n];  
  30.    w=new int[n];  
  31.    for(int i=0; i<n; i++){  
  32.     b[i]=sc.nextInt();  
  33.     e[i]=sc.nextInt();  
  34.     w[i]=sc.nextInt();  
  35.    }  
  36.    solve();  
  37.   }  
  38.  }  
  39.   
  40.  void solve(){  
  41.   int[] v=new int[x];  
  42.   fill(v, s);  
  43.   for(int j=0; j<n; j++){  
  44.    for(int i=b[j]; i<e[j]; i++){  
  45.     v[i]+=w[j];  
  46.    }  
  47.   }  
  48.   PriorityQueue<Integer> que=new PriorityQueue<Integer>();  
  49.   for(int i=0; i<x; i++){  
  50.    que.offer(v[i]);  
  51.   }  
  52.   double d=r-s;  
  53.   double remain=t;  
  54.   double ans=0;  
  55.   for(int i=0; i<x; i++){  
  56.    int u=que.poll();  
  57.    if(1.0/(u+d)>remain+EPS){  
  58.     double p=remain*(u+d);  
  59.     ans+=remain+(1.0-p)/u;  
  60.     remain=0;  
  61.    }else{  
  62.     remain-=1.0/(u+d);  
  63.     ans+=1.0/(u+d);  
  64.    }  
  65.   }  
  66.   answer(ans+"");  
  67.  }  
  68.   
  69.  void answer(String s){  
  70.   println("Case #"+caze+": "+s);  
  71.  }  
  72.   
  73.  void println(String s){  
  74.   System.out.println(s);  
  75.  }  
  76.   
  77.  void print(String s){  
  78.   System.out.print(s);  
  79.  }  
  80.   
  81.  void debug(Object... os){  
  82.   System.err.println(Arrays.deepToString(os));  
  83.  }  
  84.   
  85.  public static void main(String[] args){  
  86.   try{  
  87.    System.setIn(new FileInputStream(  
  88.      "D:/contest_workspace/gcj_2011_round2/dat/A-large.in"));  
  89.    System.setOut(new PrintStream(new FileOutputStream(  
  90.      "D:/contest_workspace/gcj_2011_round2/dat/A-large.out")));  
  91.   }catch(Exception e){}  
  92.   
  93.   new A().run();  
  94.   System.out.flush();  
  95.   System.out.close();  
  96.  }  
  97. }  

■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)になり間に合う．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class B{  
  10.  Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  int caze;  
  16.  int t;  
  17.  int m, n, d;  
  18.  long[][] a;  
  19.   
  20.  void run(){  
  21.   t=sc.nextInt();  
  22.   for(caze=1; caze<=t; caze++){  
  23.    n=sc.nextInt();  
  24.    m=sc.nextInt();  
  25.    d=sc.nextInt();  
  26.    a=new long[n][m];  
  27.    for(int j=0; j<n; j++){  
  28.     String s=sc.next();  
  29.     for(int i=0; i<m; i++){  
  30.      a[j][i]=s.charAt(i)-'0'+d;  
  31.     }  
  32.    }  
  33.    solve();  
  34.   }  
  35.  }  
  36.   
  37.  long[][] mx1, mx2, my1, my2, m1, m2;  
  38.  double gx, gy, g;  
  39.   
  40.  void solve(){  
  41.   mx1=new long[n][m];  
  42.   mx2=new long[n][m];  
  43.   my1=new long[n][m];  
  44.   my2=new long[n][m];  
  45.   m1=new long[n][m];  
  46.   m2=new long[n][m];  
  47.   
  48.   for(int j=0; j<n; j++){  
  49.    mx1[j][0]=a[j][0]*0;  
  50.    m1[j][0]=a[j][0];  
  51.    for(int i=1; i<m; i++){  
  52.     mx1[j][i]=mx1[j][i-1]+a[j][i]*i;  
  53.     m1[j][i]=m1[j][i-1]+a[j][i];  
  54.    }  
  55.   }  
  56.   
  57.   for(int i=0; i<m; i++){  
  58.    mx2[0][i]=mx1[0][i];  
  59.    m2[0][i]=m1[0][i];  
  60.    for(int j=1; j<n; j++){  
  61.     mx2[j][i]=mx2[j-1][i]+mx1[j][i];  
  62.     m2[j][i]=m2[j-1][i]+m1[j][i];  
  63.    }  
  64.   }  
  65.   
  66.   for(int i=0; i<m; i++){  
  67.    my1[0][i]=a[0][i]*0;  
  68.    for(int j=1; j<n; j++){  
  69.     my1[j][i]=my1[j-1][i]+a[j][i]*j;  
  70.    }  
  71.   }  
  72.   
  73.   for(int j=0; j<n; j++){  
  74.    my2[j][0]=my1[j][0];  
  75.    for(int i=1; i<m; i++){  
  76.     my2[j][i]=my2[j][i-1]+my1[j][i];  
  77.    }  
  78.   }  
  79.   
  80.   // 1クエリO(1)  
  81.   int ans=0;  
  82.   for(int y=0; y<n; y++){  
  83.    for(int x=0; x<m; x++){  
  84.     for(int w=3; x+w<=m&&y+w<=n; w++){  
  85.      calc(x, y, w);  
  86.      double mx=x+(w-1)/2.;  
  87.      double my=y+(w-1)/2.;  
  88.      if(abs(mx-gx)<EPS&&abs(my-gy)<EPS){  
  89.       ans=max(ans, w);  
  90.      }  
  91.     }  
  92.    }  
  93.   }  
  94.   answer(ans>0?(ans+""):"IMPOSSIBLE");  
  95.   debug(ans);  
  96.  }  
  97.   
  98.  void calc(int x, int y, int w){  
  99.   gx=mx2[y+w-1][x+w-1];  
  100.   gy=my2[y+w-1][x+w-1];  
  101.   g=m2[y+w-1][x+w-1];  
  102.   if(x>0){  
  103.    gx-=mx2[y+w-1][x-1];  
  104.    gy-=my2[y+w-1][x-1];  
  105.    g-=m2[y+w-1][x-1];  
  106.   }  
  107.   if(y>0){  
  108.    gx-=mx2[y-1][x+w-1];  
  109.    gy-=my2[y-1][x+w-1];  
  110.    g-=m2[y-1][x+w-1];  
  111.   }  
  112.   if(x>0&&y>0){  
  113.    gx+=mx2[y-1][x-1];  
  114.    gy+=my2[y-1][x-1];  
  115.    g+=m2[y-1][x-1];  
  116.   }  
  117.   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);  
  118.   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);  
  119.   g-=a[y][x]+a[y][x+w-1]+a[y+w-1][x]+a[y+w-1][x+w-1];  
  120.   gx/=g;  
  121.   gy/=g;  
  122.  }  
  123.   
  124.  void answer(String s){  
  125.   println("Case #"+caze+": "+s);  
  126.  }  
  127.   
  128.  void println(String s){  
  129.   System.out.println(s);  
  130.  }  
  131.   
  132.  void print(String s){  
  133.   System.out.print(s);  
  134.  }  
  135.   
  136.  void debug(Object... os){  
  137.   System.err.println(Arrays.deepToString(os));  
  138.  }  
  139.   
  140.  public static void main(String[] args){  
  141.   try{  
  142.    System.setIn(new FileInputStream(  
  143.      "D:/contest_workspace/gcj_2011_round2/dat/B-large.in"));  
  144.    System.setOut(new PrintStream(new FileOutputStream(  
  145.      "D:/contest_workspace/gcj_2011_round2/dat/B-large.out")));  
  146.   }catch(Exception e){}  
  147.   
  148.   new B().run();  
  149.   System.out.flush();  
  150.   System.out.close();  
  151.  }  
  152. }  
■Result 38pts. 756th 念願のTシャツゲットです．もう少し頑張れば，Round3に進めたかもしれないですが，ここ最近で最高レベルに集中出来たので良かったと思います．
投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder SRM 508

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

■DivideAndShift(Easy)

答えをf(n,m)として，再帰的に解きました．
素因数分解をして，素数のべき乗ごとに再帰するので， 制限時間には余裕で間に合います．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class DivideAndShift {  
  10.  int INF=1<<28;  
  11.  double EPS=1e-9;  
  12.   
  13.  int rec(int n, int m){  
  14.   if(m==0){  
  15.    return 0;  
  16.   }  
  17.   HashMap<Integer,Integer> map=primeFactor(n);  
  18.   int res=min(m,n-m);  
  19.   for(int p:map.keySet()){  
  20.    if(p==1){  
  21.     continue;  
  22.    }  
  23.    res=min(res,rec(n/p,m%(n/p))+1);  
  24.   }  
  25.   return res;  
  26.  }  
  27.   
  28.  public int getLeast(int n, int m) {  
  29.   return rec(n,m-1);  
  30.  }  
  31.    
  32.  HashMap<Integer, Integer> primeFactor(int n){  
  33.   HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();  
  34.   for(int i=2; i*i<=n; i++){  
  35.    int c=0;  
  36.    for(; n%i==0; n/=i)  
  37.     c++;  
  38.    if(c>0)  
  39.     map.put(i, c);  
  40.   }  
  41.   if(n!=1)  
  42.    map.put(n, 1);  
  43.   return map;  
  44.  }  
  45.   
  46.  void debug(Object...os){  
  47.   System.err.println(Arrays.deepToString(os));  
  48.  }  
  49.   
  50.  void print(String s){  
  51.   System.out.print(s);  
  52.  }  
  53.   
  54.  void println(String s){  
  55.   System.out.println(s);  
  56.  }  
  57. }  

■Challenge Phase

撃墜無し．

■Result

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

■Rating

1365 -> 1414
微増．目標の1500にはいつ到達できるのか…．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年5月30日月曜日

CodeChef May Cook-off 2011

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

■Popular Rice Recipe

やるだけ．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.  Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  void run(){  
  16.   int caze=sc.nextInt();  
  17.   for(int k=0; k<caze; k++){  
  18.    int n=sc.nextInt();  
  19.    HashMap<String, Integer> map=new HashMap<String, Integer>();  
  20.    int ans=0;  
  21.    for(int i=0; i<n; i++){  
  22.     String s=sc.next();  
  23.     int p=sc.next().equals("+")?1:-1;  
  24.     if(map.containsKey(s)){  
  25.      ans-=map.get(s);  
  26.     }  
  27.     ans+=p;  
  28.     map.put(s, p);  
  29.    }  
  30.    println(""+ans);  
  31.   }  
  32.  }  
  33.   
  34.  void println(String s){  
  35.   System.out.println(s);  
  36.  }  
  37.   
  38.  void print(String s){  
  39.   System.out.print(s);  
  40.  }  
  41.   
  42.  void debug(Object... os){  
  43.   System.err.println(Arrays.deepToString(os));  
  44.  }  
  45.   
  46.  public static void main(String[] args){  
  47.   new Main().run();  
  48.  }  
  49. }  

■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にて通ったコード．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.  Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  int n;  
  16.  int[] a;  
  17.   
  18.  void run(){  
  19.   int t=sc.nextInt();  
  20.   for(int j=0; j<t; j++){  
  21.    n=sc.nextInt();  
  22.    a=new int[n];  
  23.    for(int i=0; i<n; i++){  
  24.     a[i]=sc.nextInt();  
  25.    }  
  26.    println(solve()+"");  
  27.   }  
  28.  }  
  29.   
  30.  int solve(){  
  31.   int sum=0;  
  32.   for(int e : a){  
  33.    sum+=e;  
  34.   }  
  35.   if(sum%n!=0){  
  36.    return -1;  
  37.   }  
  38.   PriorityQueue<R> que1=new PriorityQueue<R>();  
  39.   PriorityQueue<R> que2=new PriorityQueue<R>();  
  40.   for(int e : a){  
  41.    que1.add(new R(e));  
  42.    que2.add(new R(-e));  
  43.   }  
  44.   int t;  
  45.   for(t=0;; t++){  
  46.    R p=que1.poll();  
  47.    for(;p.f;){  
  48.     p=que1.poll();  
  49.    }  
  50.    p.f=true;  
  51.    R q=que2.poll();  
  52.    for(;q.f;){  
  53.     q=que2.poll();  
  54.    }  
  55.    q.f=true;  
  56.    int min=p.v;  
  57.    int max=-q.v;  
  58.    if(min==max){  
  59.     break;  
  60.    }  
  61.    int r=(int)((max-min+1)/2.0);  
  62.    min+=r;  
  63.    max-=r;  
  64.    que1.add(new R(min));  
  65.    que2.add(new R(-min));  
  66.    que1.add(new R(max));  
  67.    que2.add(new R(-max));  
  68.   }  
  69.   return t;  
  70.  }  
  71.   
  72.  class R implements Comparable<R>{  
  73.   int v;  
  74.   boolean f;  
  75.   R(int v){  
  76.    this.v=v;  
  77.   }  
  78.   @Override  
  79.   public int compareTo(R r){  
  80.    return v-r.v;  
  81.   }  
  82.  }  
  83.    
  84.  void println(String s){  
  85.   System.out.println(s);  
  86.  }  
  87.   
  88.  void print(String s){  
  89.   System.out.print(s);  
  90.  }  
  91.   
  92.  void debug(Object... os){  
  93.   System.err.println(Arrays.deepToString(os));  
  94.  }  
  95.   
  96.  public static void main(String[] args){  
  97.   new Main().run();  
  98.  }  
  99. }  

■Result

----o

これは酷い…．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年5月29日日曜日

TopCoder SRM 507

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

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

■TheNumbersWithLuckyLastDigit(Easy)

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

最初にDFSで全探索しようと思ったのが間違いでした．
実際，色ごとのタイルの枚数を調べて場合分けすれば求まるのです（もっと完結に書くことも出来ます）．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class CubeStickers {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public String isPossible(String[] ss) {  
  15.   HashMap<String,Integer> map=new HashMap<String,Integer>();  
  16.   for(String s:ss){  
  17.    if(!map.containsKey(s)){  
  18.     map.put(s,0);  
  19.    }  
  20.    map.put(s,map.get(s)+1);  
  21.   }  
  22.   if(map.size()>=5){  
  23.    return "YES";  
  24.   }  
  25.   if(map.size()==4){  
  26.    int c=0;  
  27.    for(int e:map.values()){  
  28.     if(e>=2){  
  29.      c++;  
  30.     }  
  31.    }  
  32.    return c>=2?"YES":"NO";  
  33.   }  
  34.   if(map.size()==3){  
  35.    for(int e:map.values()){  
  36.     if(e<2){  
  37.      return "NO";  
  38.     }  
  39.    }  
  40.    return "YES";  
  41.   }  
  42.   return "NO";  
  43.  }  
  44.    
  45.  void debug(Object...os){  
  46.   System.err.println(Arrays.deepToString(os));  
  47.  }  
  48.   
  49.  void print(String s){  
  50.   System.out.print(s);  
  51.  }  
  52.   
  53.  void println(String s){  
  54.   System.out.println(s);  
  55.  }  
  56. }  

■CubePacking(Medium)

1辺の長さが1の立方体Ns個と，1辺の長さがLの立方体Nb個とを詰めることが出来る直方体の最小体積を求めよ．
実は結構簡単で，3辺の内の2辺を決めると，もう1辺はすぐ求まります．
ですので，2辺を全探索しつつ，体積を算出し最小値を求めれば良いのです．
本番中は解けませんでした…．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class CubePacking {  
  10.  long INF=1L<<32;  
  11.  // int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public int getMinimumVolume(int m, int n, int len) {  
  15.   long ans=INF;  
  16.   for(long a=1;a*a*a<=INF;a++){  
  17.    for(long b=a;a*b*b<=INF;b++){  
  18.     long base=(a/len)*(b/len);  
  19.     if(base==0){  
  20.      continue;  
  21.     }  
  22.     long c=((n-1)/base+1)*len;  
  23.     long rest=m-(a*b*c-len*len*len*n);  
  24.     if(rest>0){  
  25.      c+=(rest-1)/(a*b)+1;  
  26.     }  
  27.     ans=min(ans,a*b*c);  
  28.    }  
  29.   }  
  30.   return (int)ans;  
  31.  }  
  32.    
  33.  void debug(Object...os){  
  34.   System.err.println(Arrays.deepToString(os));  
  35.  }  
  36.   
  37.  void print(String s){  
  38.   System.out.print(s);  
  39.  }  
  40.   
  41.  void println(String s){  
  42.   System.out.println(s);  
  43.  }  
  44. }  

■Challenge Phase

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

■Result

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

■Rating

1442 -> 1365
前々回のレートに戻ってしまいました…．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年5月23日月曜日

Google Code Jam 2011 Round1B

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

■B. Revenge of the Hot Dogs

ご想像のとおり二分探索．
時間tに対して，各ホットドッグ屋がD離れることが出来るかを判定する必要がある．
これは，ホットドッグ屋を左から見ていき，可能な限り左に寄せていくことで判定できる．
二分探索の上限の見積もりが甘くLargeでWAってしまった…．
view plainprint?
  1. import java.util.*;  
  2. import java.util.Map.Entry;  
  3. import java.lang.*;  
  4. import java.math.*;  
  5. import java.io.*;  
  6.   
  7. import static java.lang.Math.*;  
  8. import static java.util.Arrays.*;  
  9.   
  10. public class B{  
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  long INF=1L<<40;  
  14.  double EPS=1e-9;  
  15.   
  16.  int caze;  
  17.  int n, d;  
  18.  R[] rs;  
  19.   
  20.  void run(){  
  21.   int tt=sc.nextInt();  
  22.   for(caze=1; caze<=tt; caze++){  
  23.    n=sc.nextInt();  
  24.    d=sc.nextInt();  
  25.    rs=new R[n];  
  26.    for(int i=0; i<n; i++){  
  27.     int p=sc.nextInt();  
  28.     int m=sc.nextInt();  
  29.     rs[i]=new R(p, m);  
  30.    }  
  31.    solve();  
  32.   }  
  33.  }  
  34.   
  35.  void solve(){  
  36.   long left=0, right=INF;  
  37.   for(int i=0; i<n; i++){  
  38.    rs[i].p*=2;  
  39.   }  
  40.   d*=2;  
  41.   
  42.   sort(rs, new Comparator<R>(){  
  43.    @Override  
  44.    public int compare(R r1, R r2){  
  45.     return r1.p-r2.p;  
  46.    }  
  47.   });  
  48.   
  49.   for(int i=0; i<1000; i++){  
  50.    long mid=(left+right)/2;  
  51.    if(check(mid)){  
  52.     right=mid;  
  53.    }else{  
  54.     left=mid;  
  55.    }  
  56.   }  
  57.   debug(right, right/2.0);  
  58.   answer(String.format("%.1f", right/2.0));  
  59.  }  
  60.   
  61.  boolean check(long t){  
  62.   long left=-INF;  
  63.   for(int j=0; j<n; j++){  
  64.    for(int i=0; i<rs[j].m; i++){  
  65.     if(rs[j].p+t<left+d){  
  66.      return false;  
  67.     }  
  68.     left=max(left+d, rs[j].p-t);  
  69.     // [left+d, INF) and [p-t , p+t]  
  70.    }  
  71.   }  
  72.   return true;  
  73.  }  
  74.   
  75.  class R{  
  76.   int p, m;  
  77.   R(int p, int m){  
  78.    this.p=p;  
  79.    this.m=m;  
  80.   }  
  81.  }  
  82.   
  83.  void answer(String s){  
  84.   println("Case #"+caze+": "+s);  
  85.  }  
  86.   
  87.  void println(String s){  
  88.   System.out.println(s);  
  89.  }  
  90.   
  91.  void print(String s){  
  92.   System.out.print(s);  
  93.  }  
  94.   
  95.  void debug(Object... os){  
  96.   System.err.println(Arrays.deepToString(os));  
  97.  }  
  98.   
  99.  public static void main(String[] args){  
  100.   try{  
  101.    System.setIn(new FileInputStream(  
  102.      "D:/contest_workspace/gcj_2011_round1b/dat/B-large.in"));  
  103.    System.setOut(new PrintStream(new FileOutputStream(  
  104.      "D:/contest_workspace/gcj_2011_round1b/dat/B-large.out")));  
  105.   }catch(Exception e){}  
  106.   new B().run();  
  107.   System.out.flush();  
  108.   System.out.close();  
  109.  }  
  110. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Google Code Jam 2011 Round1A

遅ればせながら，報告．

■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については，試合の勝敗を調整すれば基本的に実現可能．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class A{  
  10.  Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  int caze;  
  16.  int t;  
  17.  long n, nd, ng;  
  18.   
  19.  void run(){  
  20.   t=sc.nextInt();  
  21.   for(caze=1; caze<=t; caze++){  
  22.    n=sc.nextLong();  
  23.    nd=sc.nextLong();  
  24.    ng=sc.nextLong();  
  25.    solve();  
  26.   }  
  27.  }  
  28.   
  29.  void solve(){  
  30.   long dd=100;  
  31.   long dg=100;  
  32.   if(ng==0&&nd>0){  
  33.    answer("Broken");  
  34.    return;  
  35.   }  
  36.   if(ng==100&&nd<100){  
  37.    answer("Broken");  
  38.    return;  
  39.   }  
  40.   long gcdD=gcd(nd, dd);  
  41.   long gcdG=gcd(ng, dg);  
  42.   debug(gcdD, gcdG);  
  43.   nd/=gcdD;  
  44.   dd/=gcdD;  
  45.   ng/=gcdG;  
  46.   dg/=gcdG;  
  47.   debug(nd, dd, ng, dg);  
  48.   long d=dd;  
  49.   if(d>n){  
  50.    answer("Broken");  
  51.    return;  
  52.   }  
  53.   answer("Possible");  
  54.  }  
  55.   
  56.  void answer(String s){  
  57.   println("Case #"+caze+": "+s);  
  58.  }  
  59.   
  60.  long gcd(long m, long n){  
  61.   for(; n!=0;){  
  62.    long t=m%n;  
  63.    m=n;  
  64.    n=t;  
  65.   }  
  66.   return m;  
  67.  }  
  68.   
  69.  void println(String s){  
  70.   System.out.println(s);  
  71.  }  
  72.   
  73.  void print(String s){  
  74.   System.out.print(s);  
  75.  }  
  76.   
  77.  void debug(Object... os){  
  78.   System.err.println(Arrays.deepToString(os));  
  79.  }  
  80.   
  81.  public static void main(String[] args){  
  82.   try{  
  83.    System.setIn(new FileInputStream(  
  84.      "D:/contest_workspace/gcj_2011_round1a/dat/A-large.in"));  
  85.    System.setOut(new PrintStream(new FileOutputStream(  
  86.      "D:/contest_workspace/gcj_2011_round1a/dat/A-large.out")));  
  87.   }catch(Exception e){}  
  88.   
  89.   new A().run();  
  90.   System.out.flush();  
  91.   System.out.close();  
  92.  }  
  93. }  

■B. The Killer Word

大雑把な方針は，DFSです．
まず，辞書単語を文字列の長さで分類します．
そして，リストの文字を順番に辞書全体に適用していきます．
その際，それぞれの辞書単語の開示状態は変わります．
この開示状態が等しいもので分類して，その集合で個々にDFSを行います．
集合の要素数が1になったら終わりです．
詳しい説明は，GCJ公式のContest Analysisを御覧下さい．
ちなみに，本番では解けませんでした．
view plainprint?
  1. import java.util.*;  
  2. import java.util.Map.Entry;  
  3. import java.lang.*;  
  4. import java.math.*;  
  5. import java.io.*;  
  6.   
  7. import static java.lang.Math.*;  
  8. import static java.util.Arrays.*;  
  9.   
  10. public class B{  
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int caze;  
  17.  int m, n;  
  18.  String[] dic, lis;  
  19.  String l;  
  20.   
  21.  int[] bit;  
  22.  int[] opend;  
  23.  int[][] open;  
  24.  int[] loses;  
  25.   
  26.  void run(){  
  27.   int tt=sc.nextInt();  
  28.   for(caze=1; caze<=tt; caze++){  
  29.    m=sc.nextInt();  
  30.    n=sc.nextInt();  
  31.    dic=new String[m];  
  32.    lis=new String[n];  
  33.    for(int i=0; i<m; i++){  
  34.     dic[i]=sc.next();  
  35.    }  
  36.    for(int i=0; i<n; i++){  
  37.     lis[i]=sc.next();  
  38.    }  
  39.    solve();  
  40.   }  
  41.  }  
  42.   
  43.  void dfs(TreeSet<Integer> set, int k, int exist){  
  44.   if(set.size()<=1||k>=26){  
  45.    return;  
  46.   }  
  47.   if(((exist>>(l.charAt(k)-'a'))&1)==0){  
  48.    dfs(set, k+1, exist);  
  49.    return;  
  50.   }  
  51.   HashMap<Integer, TreeSet<Integer>> map=new HashMap<Integer, TreeSet<Integer>>();  
  52.   HashMap<Integer, Integer> exists=new HashMap<Integer, Integer>();  
  53.   for(int i : set){  
  54.    opend[i]|=open[i][l.charAt(k)];  
  55.    if(open[i][l.charAt(k)]==0){  
  56.     loses[i]++;  
  57.    }  
  58.    if(!map.containsKey(opend[i])){  
  59.     map.put(opend[i], new TreeSet<Integer>());  
  60.     exists.put(opend[i], 0);  
  61.    }  
  62.    map.get(opend[i]).add(i);  
  63.    exists.put(opend[i], exists.get(opend[i])|bit[i]);  
  64.   }  
  65.   for(Entry<Integer, TreeSet<Integer>> entry : map.entrySet()){  
  66.    dfs(entry.getValue(), k+1, exists.get(entry.getKey()));  
  67.   }  
  68.  }  
  69.   
  70.  void solve(){  
  71.   String ans="";  
  72.   for(int k=0; k<n; k++){  
  73.    TreeSet<Integer>[] sets=new TreeSet[10];  
  74.    for(int i=0; i<10; i++){  
  75.     sets[i]=new TreeSet<Integer>();  
  76.    }  
  77.    bit=new int[m];  
  78.    opend=new int[m];  
  79.    open=new int[m][256];  
  80.    loses=new int[m];  
  81.    int[] exists=new int[10];  
  82.    for(int j=0; j<m; j++){  
  83.     sets[dic[j].length()-1].add(j);  
  84.     for(int i=0; i<dic[j].length(); i++){  
  85.      bit[j]|=1<<(dic[j].charAt(i)-'a');  
  86.      open[j][dic[j].charAt(i)]|=1<<i;  
  87.      exists[dic[j].length()-1]|=1<<(dic[j].charAt(i)-'a');  
  88.     }  
  89.    }  
  90.    l=lis[k];  
  91.    for(int i=0; i<10; i++){  
  92.     dfs(sets[i], 0, exists[i]);  
  93.    }  
  94.    int max=-1;  
  95.    for(int i=0; i<m; i++){  
  96.     max=max(max, loses[i]);  
  97.    }  
  98.    for(int i=0; i<m; i++){  
  99.     if(loses[i]==max){  
  100.      ans+=dic[i]+(k==n-1?"":" ");  
  101.      break;  
  102.     }  
  103.    }  
  104.   }  
  105.   answer(ans);  
  106.   debug(ans);  
  107.  }  
  108.   
  109.  void answer(String s){  
  110.   println("Case #"+caze+": "+s);  
  111.  }  
  112.   
  113.  void println(String s){  
  114.   System.out.println(s);  
  115.  }  
  116.   
  117.  void print(String s){  
  118.   System.out.print(s);  
  119.  }  
  120.   
  121.  void debug(Object... os){  
  122.   System.err.println(Arrays.deepToString(os));  
  123.  }  
  124.   
  125.  public static void main(String[] args){  
  126.   try{  
  127.    System.setIn(new FileInputStream(  
  128.      "D:/contest_workspace/gcj_2011_round1a/dat/B-large.in"));  
  129.    System.setOut(new PrintStream(new FileOutputStream(  
  130.      "D:/contest_workspace/gcj_2011_round1a/dat/B-large.out")));  
  131.   }catch(Exception e){}  
  132.   new B().run();  
  133.   System.out.flush();  
  134.   System.out.close();  
  135.  }  
  136. }  

■Result

oo----
20pts. 870th
どうにかRound2へ進出出来ます．
投稿者 時刻: 0 件のコメント:
ラベル:

専門書を読む #20

■コンピュータの数学 5 二項係数 pp.51-59
投稿者 時刻: 0 件のコメント:
ラベル:

2011年5月18日水曜日

TopCoder SRM 504.5

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

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

■TheNumbersWithLuckyLastDigit(Easy)

実際にいくつか試してみると，10で割った余りで"ほぼ"決まることが分かります．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class TheNumbersWithLuckyLastDigit {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public int find(int n) {  
  15.   int[] a={5,2,3,5,1,3,4,1,2,4};  
  16.   boolean[] out=new boolean[20];  
  17.   out[1]=out[2]=out[3]=out[5]=out[6]=out[9]=out[10]=out[13]=true;  
  18.   if(n<20&&out[n]){  
  19.    return -1;  
  20.   }else{  
  21.    return a[n%10];  
  22.   }  
  23.  }  
  24.   
  25.  void debug(Object...os){  
  26.   System.err.println(Arrays.deepToString(os));  
  27.  }  
  28.   
  29.  void print(String s){  
  30.   System.out.print(s);  
  31.  }  
  32.   
  33.  void println(String s){  
  34.   System.out.println(s);  
  35.  }  
  36. }  

■TheJackpotDivOne(Medium)

本番ではdoubleを使っていたので，アンダーフロー(?)による精度落ちで撃墜されました． 下が修正コード．JavaならばBigIntegerが使えます．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class TheJackpotDivOne {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public long[] find(long[] a, long m) {  
  15.   int n=a.length;  
  16.   for(;;){  
  17.    int k=n-1;  
  18.    BigInteger ave=BigInteger.ZERO;  
  19.    boolean same=true;  
  20.    for(int i=n-1;i>=0;i--){  
  21.     if(a[i]<=a[k]){  
  22.      k=i;  
  23.     }  
  24.     same&=a[0]==a[i];  
  25.     ave=ave.add(BigInteger.valueOf(a[i]));  
  26.    }  
  27.    if(same){  
  28.     break;  
  29.    }  
  30.    long x=ave.divide(BigInteger.valueOf(n)).longValue()-a[k]+1;  
  31.    if(m>=x){  
  32.     a[k]+=x;  
  33.     m-=x;  
  34.    }else{  
  35.     a[k]+=m;  
  36.     sort(a);  
  37.     return a;  
  38.    }  
  39.   }  
  40.   for(int i=0;i<n;i++){  
  41.    a[i]+=m/n;  
  42.    if(i<m%n){  
  43.     a[i]++;  
  44.    }  
  45.   }  
  46.   sort(a);  
  47.   return a;  
  48.  }  
  49.   
  50.  void debug(Object...os){  
  51.   System.err.println(Arrays.deepToString(os));  
  52.  }  
  53.   
  54.  void print(String s){  
  55.   System.out.print(s);  
  56.  }  
  57.   
  58.  void println(String s){  
  59.   System.out.println(s);  
  60.  }  
  61. }  

■Challenge Phase

Easyで一人撃墜．

■Result

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

■Rating

1360 -> 1442
黄色くなれるか…?!
投稿者 時刻: 0 件のコメント:
ラベル:

2011年5月15日日曜日

TCO11 Algo Qual1

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

■MinimumLiars(Easy)

考えられる全ケースを試すだけ．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5. public class MinimumLiars {  
  6.  int INF=1<<28;  
  7.  double EPS=1e-9;  
  8.   
  9.  public int getMinimum(int[] a) {  
  10.   int n=a.length;  
  11.   for(int j=0;j<=n;j++){  
  12.    int s=0;  
  13.    for(int i=0;i<n;i++){  
  14.     if(a[i]>j){  
  15.      s++;  
  16.     }  
  17.    }  
  18.    if(j==s){  
  19.     return j;  
  20.    }  
  21.   }  
  22.   return -1;  
  23.  }  
  24.   
  25.  void debug(Object...os){  
  26.   System.err.println(Arrays.deepToString(os));  
  27.  }  
  28.   
  29.  void print(String s){  
  30.   System.out.print(s);  
  31.  }  
  32.   
  33.  void println(String s){  
  34.   System.out.println(s);  
  35.  }  
  36.   
  37.  public static void main(String[] args) {  
  38.   // MinimumLiars temp = new MinimumLiars();  
  39.   // System.out.println(temp.getMinimum(int[] claim));  
  40.  }  
  41. }  

■FoxListeningToMusic(Medium)

O(Tn)じゃないとSystem Testで落ちます．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5. public class FoxListeningToMusic {  
  6.  int INF=1<<28;  
  7.  double EPS=1e-9;  
  8.   
  9.  public double[] getProbabilities(int[] a, int t) {  
  10.   int n=a.length;  
  11.   double[] dp=new double[t+1];  
  12.   dp[0]=1./n;  
  13.   for(int k=0;k<t;k++){  
  14.    double[] d=new double[n];  
  15.    for(int i=0;i<n;i++){  
  16.     d[i]+=dp[k]/n;  
  17.    }  
  18.    for(int i=0;i<n;i++){  
  19.     if(k+a[i]<=t){  
  20.      dp[k+a[i]]+=d[i];  
  21.     }  
  22.    }  
  23.   }  
  24.   // debug(dp);  
  25.   double[] res=new double[n];  
  26.   for(int i=0;i<n;i++){  
  27.    for(int j=t;j>t-a[i]&&j>=0;j--){  
  28.     res[i]+=dp[j];  
  29.    }  
  30.   }  
  31.   return res;  
  32.  }  
  33.   
  34.  void debug(Object...os){  
  35.   System.err.println(Arrays.deepToString(os));  
  36.  }  
  37.   
  38.  void print(String s){  
  39.   System.out.print(s);  
  40.  }  
  41.   
  42.  void println(String s){  
  43.   System.out.println(s);  
  44.  }  
  45.   
  46.  public static void main(String[] args) {  
  47.  }  
  48. }  

■Challenge Phase

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

■Result

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

■Rating

1279 -> 1360
600位以内なので，次のラウンドへ．Round1も残りたいですね．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年5月14日土曜日

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

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

久し振りの投稿．

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

view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int n, m;  
  17.   
  18.  void run(){  
  19.   n=sc.nextInt();  
  20.   m=sc.nextInt();  
  21.   int max=0;  
  22.   for(int j=0; j<n; j++){  
  23.    int a=0;  
  24.    for(int i=0; i<m; i++){  
  25.     a+=sc.nextInt();  
  26.    }  
  27.    max=max(max, a);  
  28.   }  
  29.   println(""+max);  
  30.  }  
  31.   
  32.  void debug(Object... os){  
  33.   System.err.println(Arrays.deepToString(os));  
  34.  }  
  35.   
  36.  void print(String s){  
  37.   System.out.print(s);  
  38.  }  
  39.   
  40.  void println(String s){  
  41.   System.out.println(s);  
  42.  }  
  43.   
  44.  public static void main(String[] args){  
  45.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  46.   new Main().run();  
  47.  }  
  48. }  

■B (iwi)

view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  void run(){  
  17.   String s=sc.next();  
  18.   int ans=0;  
  19.   if(s.length()%2==1){  
  20.    if(!Character.isLetter(s.charAt(s.length()/2))){  
  21.     ans++;  
  22.    }  
  23.   }  
  24.   boolean[][] check=new boolean[256][256];  
  25.   check['i']['i']=true;  
  26.   check['w']['w']=true;  
  27.   check['('][')']=true;  
  28.   check[')']['(']=true;  
  29.   for(int i=0; i<s.length()/2; i++){  
  30.    if(!check[s.charAt(i)][s.charAt(s.length()-1-i)]){  
  31.     ans++;  
  32.    }  
  33.   }  
  34.   println(""+ans);  
  35.  }  
  36.   
  37.  void debug(Object... os){  
  38.   System.err.println(Arrays.deepToString(os));  
  39.  }  
  40.   
  41.  void print(String s){  
  42.   System.out.print(s);  
  43.  }  
  44.   
  45.  void println(String s){  
  46.   System.out.println(s);  
  47.  }  
  48.   
  49.  public static void main(String[] args){  
  50.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  51.   new Main().run();  
  52.  }  
  53. }  

■C [[iwi]]

全探索による解法．LCSのような解法もあるようです．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  void run(){  
  17.   String ss=sc.next();  
  18.   boolean[][] check=new boolean[256][256];  
  19.   check['('][')']=true;  
  20.   check[')']['(']=true;  
  21.   check['{']['}']=true;  
  22.   check['}']['{']=true;  
  23.   check['['][']']=true;  
  24.   check[']']['[']=true;  
  25.   int k=ss.indexOf("iwi");  
  26.   int m=k;  
  27.   int n=ss.length()-(k+3);  
  28.   String s=ss.substring(0, k);  
  29.   String t=ss.substring(k+3, ss.length());  
  30.   // debug(m, n);  
  31.   // debug(s, t);  
  32.   int max=0;  
  33.   for(int sup1=0; sup1<1<<m; sup1++){  
  34.    String s1="";  
  35.    for(int i=0; i<m; i++){  
  36.     if(((sup1>>i)&1)==1){  
  37.      s1+=s.charAt(i);  
  38.     }  
  39.    }  
  40.    for(int sup2=0; sup2<1<<n; sup2++){  
  41.     if(Integer.bitCount(sup1)==Integer.bitCount(sup2)){  
  42.      String s2="";  
  43.      for(int j=0; j<n; j++){  
  44.       if(((sup2>>j)&1)==1){  
  45.        s2+=t.charAt(j);  
  46.       }  
  47.      }  
  48.      boolean f=true;  
  49.      for(int i=0; i<s1.length(); i++){  
  50.       f&=check[s1.charAt(i)][s2.charAt(s2.length()-1-i)];  
  51.      }  
  52.      if(f){  
  53.       // debug(s1, s2);  
  54.       max=max(max, s1.length()+3+s2.length());  
  55.      }  
  56.     }  
  57.    }  
  58.   }  
  59.   println(max+"");  
  60.  }  
  61.   
  62.  void debug(Object... os){  
  63.   System.err.println(Arrays.deepToString(os));  
  64.  }  
  65.   
  66.  void print(String s){  
  67.   System.out.print(s);  
  68.  }  
  69.   
  70.  void println(String s){  
  71.   System.out.println(s);  
  72.  }  
  73.   
  74.  public static void main(String[] args){  
  75.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  76.   new Main().run();  
  77.  }  
  78. }  

■D 停止問題

BFSによる解法．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int n, m;  
  17.  char[][] cs;  
  18.   
  19.  void run(){  
  20.   n=sc.nextInt();  
  21.   m=sc.nextInt();  
  22.   cs=new char[n][m];  
  23.   for(int j=0; j<n; j++){  
  24.    String s=sc.next();  
  25.    for(int i=0; i<m; i++){  
  26.     cs[j][i]=s.charAt(i);  
  27.    }  
  28.   }  
  29.   
  30.   int[] dx={0, 0, -1, 1};  
  31.   int[] dy={-1, 1, 0, 0};  
  32.   LinkedList<P> que=new LinkedList<P>();  
  33.   boolean[][][][] visited=new boolean[m][n][16][4];  
  34.   
  35.   que.offer(new P(0, 0, 0, 3));  
  36.   visited[0][0][0][3]=true;  
  37.   
  38.   for(; !que.isEmpty();){  
  39.    P p=que.poll();  
  40.    // debug(p.x, p.y, p.mem, p.dir);  
  41.    if(cs[p.y][p.x]=='?'){  
  42.     for(int i=0; i<4; i++){  
  43.      P q=new P(p.x, p.y, p.mem, p.dir);  
  44.      q.dir=i;  
  45.      q.x=(q.x+dx[q.dir]+m)%m;  
  46.      q.y=(q.y+dy[q.dir]+n)%n;  
  47.      if(!visited[q.x][q.y][q.mem][q.dir]){  
  48.       que.offer(q);  
  49.       visited[q.x][q.y][q.mem][q.dir]=true;  
  50.      }  
  51.     }  
  52.     continue;  
  53.    }  
  54.    P q=new P(p.x, p.y, p.mem, p.dir);  
  55.    switch(cs[p.y][p.x]){  
  56.    case '<':  
  57.     q.dir=2;  
  58.     break;  
  59.    case '>':  
  60.     q.dir=3;  
  61.     break;  
  62.    case '^':  
  63.     q.dir=0;  
  64.     break;  
  65.    case 'v':  
  66.     q.dir=1;  
  67.     break;  
  68.    case '_':  
  69.     if(q.mem==0){  
  70.      q.dir=3;  
  71.     }else{  
  72.      q.dir=2;  
  73.     }  
  74.     break;  
  75.    case '|':  
  76.     if(q.mem==0){  
  77.      q.dir=1;  
  78.     }else{  
  79.      q.dir=0;  
  80.     }  
  81.     break;  
  82.    case '.':  
  83.     break;  
  84.    case '@':  
  85.     println("YES");  
  86.     return;  
  87.    case '+':  
  88.     q.mem=(q.mem+1)%16;  
  89.     break;  
  90.    case '-':  
  91.     q.mem=(q.mem+15)%16;  
  92.     break;  
  93.    }  
  94.    if(Character.isDigit(cs[p.y][p.x])){  
  95.     q.mem=cs[p.y][p.x]-'0';  
  96.    }  
  97.    q.x=(q.x+dx[q.dir]+m)%m;  
  98.    q.y=(q.y+dy[q.dir]+n)%n;  
  99.    if(!visited[q.x][q.y][q.mem][q.dir]){  
  100.     que.offer(q);  
  101.     visited[q.x][q.y][q.mem][q.dir]=true;  
  102.    }  
  103.   }  
  104.   println("NO");  
  105.  }  
  106.   
  107.  class P{  
  108.   int x, y;  
  109.   int mem;  
  110.   int dir;  
  111.   
  112.   P(int x, int y, int mem, int dir){  
  113.    this.x=x;  
  114.    this.y=y;  
  115.    this.mem=mem;  
  116.    this.dir=dir;  
  117.   }  
  118.  }  
  119.   
  120.  void debug(Object... os){  
  121.   System.err.println(Arrays.deepToString(os));  
  122.  }  
  123.   
  124.  void print(String s){  
  125.   System.out.print(s);  
  126.  }  
  127.   
  128.  void println(String s){  
  129.   System.out.println(s);  
  130.  }  
  131.   
  132.  public static void main(String[] args){  
  133.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  134.   new Main().run();  
  135.  }  
  136. }  

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

System.arraycopyを何故か忘れていたため，競技中はWAでした．下は競技終了後のコード．ちなみに，bでソートすればいいので，aは関係ないです．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import static java.lang.Math.*;  
  7. import static java.util.Arrays.*;  
  8.   
  9. public class Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  long INF=1L<<48;  
  14.  double EPS=1e-9;  
  15.   
  16.  int n;  
  17.  R[] rs;  
  18.   
  19.  void run(){  
  20.   n=sc.nextInt();  
  21.   rs=new R[n];  
  22.   for(int i=0; i<n; i++){  
  23.    int a=sc.nextInt();  
  24.    int b=sc.nextInt();  
  25.    rs[i]=new R(a, b);  
  26.   }  
  27.   
  28.   sort(rs, new Comparator<R>(){  
  29.    @Override  
  30.    public int compare(R r1, R r2){  
  31.     if(r1.b!=r2.b){  
  32.      return r1.b-r2.b;  
  33.     }else{  
  34.      return r2.a-r1.a;  
  35.     }  
  36.    }  
  37.   });  
  38.   
  39.   long[][] dp=new long[n+1][n+1];  
  40.   fill(dp[0], INF);  
  41.   dp[0][0]=0;  
  42.   for(int j=1; j<=n; j++){  
  43.    System.arraycopy(dp[j-1], 0, dp[j], 0, n+1);  
  44.    for(int i=0; i<j; i++){  
  45.     long t=dp[j-1][i]+rs[j-1].a;  
  46.     if(t<=rs[j-1].b){  
  47.      dp[j][i+1]=min(dp[j][i+1], t);  
  48.     }  
  49.    }  
  50.    // debug(dp[j]);  
  51.   }  
  52.   for(int i=n; i>=0; i--){  
  53.    if(dp[n][i]<INF){  
  54.     println(i+"");  
  55.     break;  
  56.    }  
  57.   }  
  58.  }  
  59.   
  60.  class R{  
  61.   int a, b;  
  62.   R(int a, int b){  
  63.    this.a=a;  
  64.    this.b=b;  
  65.   }  
  66.  }  
  67.   
  68.  void debug(Object... os){  
  69.   System.err.println(Arrays.deepToString(os));  
  70.  }  
  71.   
  72.  void print(String s){  
  73.   System.out.print(s);  
  74.  }  
  75.   
  76.  void println(String s){  
  77.   System.out.println(s);  
  78.  }  
  79.   
  80.  public static void main(String[] args){  
  81.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  82.   new Main().run();  
  83.  }  
  84. }  

■Result

400pt. 77th

途中で離脱してしまったので，簡単な問題しか解けず残念．
Eは解法が合っていましたし，A~Dも1時間程度で解けていたので，わずかながらに成長しているようです．
それにしても，沢山の強豪がいますね．今年のICPCが心配です．
投稿者 時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)