2011年5月30日月曜日

CodeChef May Cook-off 2011

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

■Popular Rice Recipe

やるだけ.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

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

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

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

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

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

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

■Distribute idlis Equally

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

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

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

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

 int n;
 int[] a;

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

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

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

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

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

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

■Result

----o

これは酷い….

2011年5月29日日曜日

TopCoder SRM 507

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

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

■TheNumbersWithLuckyLastDigit(Easy)

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

最初にDFSで全探索しようと思ったのが間違いでした.
実際,色ごとのタイルの枚数を調べて場合分けすれば求まるのです(もっと完結に書くことも出来ます).
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

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

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

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

■CubePacking(Medium)

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

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

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

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

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

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

■Challenge Phase

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

■Result

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

■Rating

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

2011年5月23日月曜日

Google Code Jam 2011 Round1B

せめて,Bは解いておこうかと.

■B. Revenge of the Hot Dogs

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Google Code Jam 2011 Round1A

遅ればせながら,報告.

■A. FreeCell Statistics

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

次に,勝率がPD[%]となる(今日の)最小のゲーム数を求める.
つまり,
PD/100*Dが整数となるような,最小のDを求める.
つまり,
D=100/gcd(PD,100)
である.
D≦Nならば,"Possible".
PGについては,試合の勝敗を調整すれば基本的に実現可能.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

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

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

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

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

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

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

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

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

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

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

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

■B. The Killer Word

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

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

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

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

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

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

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

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

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

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

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

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

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

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

■Result

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

専門書を読む #20

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

2011年5月18日水曜日

TopCoder SRM 504.5

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

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

■TheNumbersWithLuckyLastDigit(Easy)

実際にいくつか試してみると,10で割った余りで"ほぼ"決まることが分かります.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

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

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

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

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

■TheJackpotDivOne(Medium)

本番ではdoubleを使っていたので,アンダーフロー(?)による精度落ちで撃墜されました. 下が修正コード.JavaならばBigIntegerが使えます.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

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

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

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

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

■Challenge Phase

Easyで一人撃墜.

■Result

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

■Rating

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

2011年5月15日日曜日

TCO11 Algo Qual1

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

■MinimumLiars(Easy)

考えられる全ケースを試すだけ.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class MinimumLiars {
 int INF=1<<28;
 double EPS=1e-9;

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

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

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

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

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

■FoxListeningToMusic(Medium)

O(Tn)じゃないとSystem Testで落ちます.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class FoxListeningToMusic {
 int INF=1<<28;
 double EPS=1e-9;

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

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

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

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

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

■Challenge Phase

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

■Result

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

■Rating

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

2011年5月14日土曜日

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

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

久し振りの投稿.

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

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n, m;

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

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

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

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

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

■B (iwi)

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

■C [[iwi]]

全探索による解法.LCSのような解法もあるようです.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

■D 停止問題

BFSによる解法.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

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

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

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

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

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

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

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

System.arraycopyを何故か忘れていたため,競技中はWAでした.下は競技終了後のコード.ちなみに,bでソートすればいいので,aは関係ないです.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n;
 R[] rs;

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

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

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

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

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

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

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

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

■Result

400pt. 77th

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