2010年8月18日水曜日

Codeforces Beta Round #26

Codeforces Beta Round #26 8/17(0:00~2:00)

今回は，TopCoderっぽいルール．
1.問題を解き．コードを提出．
2.Pretestsに通ったら，一先ず得点がもらえる．
3.そのコードに自信があったら"ロック"する．一度ロックしたら，コードを修正する事は出来ないし，ロックを解除する事も出来ない．
4.ロックした問題については，他の人のコードを見ることが出来る．
5.間違ってそうなコードがあったら，バグを誘発する入力を与える．撃墜できたら+100，ミスしたら-50．
これが競技中ずっと行われます．競技終了後，システムテストが行われます．
前回このルールで参加した時は，撃墜祭りでしたが，今回はそれ程でもありませんでした．

■A. Almost Prime
□問題
素因数が2種類の数をAlmost Primeという．n以下のAlmost Primeの個数を答えよ．
□解法
やるだけ．
□コード
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5. import static java.lang.Math.*;  
  6. import static java.util.Arrays.*;  
  7.   
  8. public class A{  
  9.  Scanner sc=new Scanner(System.in);  
  10.   
  11.  void run(){  
  12.   int n=sc.nextInt();  
  13.   int[] cnt=new int[3001];  
  14.   for(int i=2; i<=3000; i++){  
  15.    cnt[i]+=cnt[i-1]+(isAP(i)?1:0);  
  16.   }  
  17.   println(""+cnt[n]);  
  18.  }  
  19.   
  20.  boolean isAP(int n){  
  21.   int d=-1, e=-1;  
  22.   int m=n;  
  23.   for(int i=2; i<n; i++){  
  24.    if(m%i==0){  
  25.     if(e!=-1){  
  26.      return false;  
  27.     }else if(d!=-1){  
  28.      e=i;  
  29.     }else{  
  30.      d=i;  
  31.     }  
  32.     while(m%i==0)  
  33.      m/=i;  
  34.    }  
  35.   }  
  36.   return e!=-1;  
  37.  }  
  38.   
  39.  void println(String s){  
  40.   System.out.println(s);  
  41.  }  
  42.   
  43.  void print(String s){  
  44.   System.out.print(s);  
  45.  }  
  46.   
  47.  public static void main(String[] args){  
  48.   new A().run();  
  49.  }  
  50. }  


■B. Regular Bracket Sequence
□問題
(()))()(()(のような括弧列から，矛盾が無くなる様に括弧を取り除いた時，最大で何括弧残るか．
↑の場合(())()()となり答えは8．
□解法
左括弧が来たらカウンタ++，右括弧が来たらカウンタ--．カウンタが負になったらその分左括弧を取り除き，最終的にカウンタが正になったらその分右括弧を取り除く．
□コード
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5. import static java.lang.Math.*;  
  6. import static java.util.Arrays.*;  
  7.   
  8. public class B{  
  9.  Scanner sc=new Scanner(System.in);  
  10.   
  11.  void run(){  
  12.   char[]cs =sc.nextLine().toCharArray();  
  13.   int cnt=0;  
  14.   int stack=0;  
  15.   for(char c:cs){  
  16.    if(c=='(')  
  17.     stack++;  
  18.    else{  
  19.     if(stack==0)  
  20.      cnt++;  
  21.     else  
  22.      stack--;  
  23.    }  
  24.   }  
  25.   cnt+=stack;  
  26.   int length=cs.length-cnt;  
  27.   println(""+length);  
  28.  }  
  29.   
  30.  void println(String s){  
  31.   System.out.println(s);  
  32.  }  
  33.   
  34.  void print(String s){  
  35.   System.out.print(s);  
  36.  }  
  37.   
  38.  public static void main(String[] args){  
  39.   new B().run();  
  40.  }  
  41. }  


■C. Parquet
□問題
mxnの領域に1x2，2x1，2x2のタイルを敷き詰める問題．
□解法
m，nで場合わけして敷き詰めるだけ．実装ゲー．
□コード(適当でごめんなさい)
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5. import static java.lang.Math.*;  
  6. import static java.util.Arrays.*;  
  7.   
  8. public class C{  
  9.  Scanner sc=new Scanner(System.in);  
  10.   
  11.  int n, m, a, b, c;  
  12.  char[][] map;  
  13.   
  14.  void run(){  
  15.   n=sc.nextInt();  
  16.   m=sc.nextInt();  
  17.   a=sc.nextInt();  
  18.   b=sc.nextInt();  
  19.   c=sc.nextInt();  
  20.   map=new char[n][m];  
  21.   if((m*n)%2!=0){  
  22.    println("IMPOSSIBLE");  
  23.    return;  
  24.   }  
  25.   if(n%2==0&&m%2==0){  
  26.    for(int j=0; j<n; j+=2){  
  27.     for(int i=0; i<m; i+=2){  
  28.      if(c>0){  
  29.       c--;  
  30.       char s=getDifferent(new int[]{i, i+1, i, i+1},  
  31.         new int[]{j, j, j+1, j+1});  
  32.       map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;  
  33.      }else if(a>=2){  
  34.       char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});  
  35.       map[j][i]=map[j][i+1]=s;  
  36.       char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});  
  37.       map[j+1][i]=map[j+1][i+1]=t;  
  38.       a-=2;  
  39.      }else if(b>=2){  
  40.       char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});  
  41.       map[j][i]=map[j+1][i]=s;  
  42.       char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});  
  43.       map[j][i+1]=map[j+1][i+1]=t;  
  44.       b-=2;  
  45.      }else{  
  46.       println("IMPOSSIBLE");  
  47.       return;  
  48.      }  
  49.     }  
  50.    }  
  51.   }  
  52.   if(m%2==1){  
  53.    for(int j=0; j<n; j+=2){  
  54.     for(int i=0; i<m-1; i+=2){  
  55.      if(c>0){  
  56.       c--;  
  57.       char s=getDifferent(new int[]{i, i+1, i, i+1},  
  58.         new int[]{j, j, j+1, j+1});  
  59.       map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;  
  60.      }else if(a>=2){  
  61.       char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});  
  62.       map[j][i]=map[j][i+1]=s;  
  63.       char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});  
  64.       map[j+1][i]=map[j+1][i+1]=t;  
  65.       a-=2;  
  66.      }else if(b>=2){  
  67.       char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});  
  68.       map[j][i]=map[j+1][i]=s;  
  69.       char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});  
  70.       map[j][i+1]=map[j+1][i+1]=t;  
  71.       b-=2;  
  72.      }else{  
  73.       println("IMPOSSIBLE");  
  74.       return;  
  75.      }  
  76.     }  
  77.    }  
  78.    for(int j=0; j<n; j+=2){  
  79.     if(b>0){  
  80.      char s=getDifferent(new int[]{m-1, m-1}, new int[]{j, j+1});  
  81.      map[j][m-1]=map[j+1][m-1]=s;  
  82.      b--;  
  83.     }else{  
  84.      println("IMPOSSIBLE");  
  85.      return;  
  86.     }  
  87.    }  
  88.   }  
  89.   if(n%2==1){  
  90.    for(int j=0; j<n-1; j+=2){  
  91.     for(int i=0; i<m; i+=2){  
  92.      if(c>0){  
  93.       c--;  
  94.       char s=getDifferent(new int[]{i, i+1, i, i+1},  
  95.         new int[]{j, j, j+1, j+1});  
  96.       map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;  
  97.      }else if(b>=2){  
  98.       char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});  
  99.       map[j][i]=map[j+1][i]=s;  
  100.       char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});  
  101.       map[j][i+1]=map[j+1][i+1]=t;  
  102.       b-=2;  
  103.      }else if(a>=2){  
  104.       char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});  
  105.       map[j][i]=map[j][i+1]=s;  
  106.       char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});  
  107.       map[j+1][i]=map[j+1][i+1]=t;  
  108.       a-=2;  
  109.      }else{  
  110.       println("IMPOSSIBLE");  
  111.       return;  
  112.      }  
  113.     }  
  114.    }  
  115.    for(int i=0; i<m; i+=2){  
  116.     if(a>0){  
  117.      char s=getDifferent(new int[]{i, i+1}, new int[]{n-1, n-1});  
  118.      map[n-1][i]=map[n-1][i+1]=s;  
  119.      a--;  
  120.     }else{  
  121.      println("IMPOSSIBLE");  
  122.      return;  
  123.     }  
  124.    }  
  125.   }  
  126.   for(int j=0;j<n;j++){  
  127.    for(int i=0;i<m;i++){  
  128.     System.out.print(map[j][i]);  
  129.    }  
  130.    println("");  
  131.   }  
  132.   
  133.  }  
  134.   
  135.  char getDifferent(int[] xs, int[] ys){  
  136.   boolean[] exist=new boolean[256];  
  137.   for(int i=0; i<xs.length; i++){  
  138.    int x=xs[i];  
  139.    int y=ys[i];  
  140.    if(x>0)  
  141.     exist[map[y][x-1]]=true;  
  142.    if(x<m-1)  
  143.     exist[map[y][x+1]]=true;  
  144.    if(y>0)  
  145.     exist[map[y-1][x]]=true;  
  146.    if(y<n-1)  
  147.     exist[map[y+1][x]]=true;  
  148.   }  
  149.   for(int i=0; i<exist.length; i++)  
  150.    if(!exist[i]&&Character.isLowerCase(i))  
  151.     return (char)i;  
  152.   return 'E';  
  153.  }  
  154.   
  155.  void println(String s){  
  156.   System.out.println(s);  
  157.  }  
  158.   
  159.  void print(String s){  
  160.   System.out.print(s);  
  161.  }  
  162.   
  163.  public static void main(String[] args){  
  164.   new C().run();  
  165.  }  
  166. }  


■D. Tickets
確率問題は苦手…

■Result
○○○××
2626p
51位

■Rating
1744 -> 1851

現時点で92位．CodeforcesでならRedCoderを狙えるかも…．
投稿者 時刻:
ラベル:

0 件のコメント:

コメントを投稿

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