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. }  

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

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

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

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

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

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

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

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

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

■Distribute idlis Equally

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

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. }  

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

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

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

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

 int n;
 int[] a;

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

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

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

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

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

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

■Result

----o

これは酷い…．

TopCoder SRM 507

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. }  

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

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

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

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

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

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

■CubePacking(Medium)

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

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. }  

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

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

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

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

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

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

■Challenge Phase

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

■Result

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

■Rating

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

Google Code Jam 2011 Round1B

せめて，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. }  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Google Code Jam 2011 Round1A

遅ればせながら，報告．

■A. FreeCell Statistics

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

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

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. }  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

■B. The Killer Word

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

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. }  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

■Result

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

専門書を読む #20

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

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. }  

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

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

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

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

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

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

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

■TheJackpotDivOne(Medium)

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

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. }  

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

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

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

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

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

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

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

■Challenge Phase

Easyで一人撃墜．

■Result

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

■Rating

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

TCO11 Algo Qual1

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. }  

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

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

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

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

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

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

■FoxListeningToMusic(Medium)

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

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. }  

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

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

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

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

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

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

■Challenge Phase

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

■Result

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

■Rating

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

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

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. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n, m;

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

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

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

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

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

■B (iwi)

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. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

■C [[iwi]]

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

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. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

■D 停止問題

BFSによる解法．

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. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n;
 R[] rs;

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

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

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

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

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

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

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

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

■Result

400pt. 77th

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