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が心配です．
投稿者 時刻:
ラベル:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)