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)