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の個数を答えよ．
□解法
やるだけ．
□コード

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);

 void run(){
  int n=sc.nextInt();
  int[] cnt=new int[3001];
  for(int i=2; i<=3000; i++){
   cnt[i]+=cnt[i-1]+(isAP(i)?1:0);
  }
  println(""+cnt[n]);
 }

 boolean isAP(int n){
  int d=-1, e=-1;
  int m=n;
  for(int i=2; i<n; i++){
   if(m%i==0){
    if(e!=-1){
     return false;
    }else if(d!=-1){
     e=i;
    }else{
     d=i;
    }
    while(m%i==0)
     m/=i;
   }
  }
  return e!=-1;
 }

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

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

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

■B. Regular Bracket Sequence
□問題
(()))()(()(のような括弧列から，矛盾が無くなる様に括弧を取り除いた時，最大で何括弧残るか．
↑の場合(())()()となり答えは8．
□解法
左括弧が来たらカウンタ++，右括弧が来たらカウンタ--．カウンタが負になったらその分左括弧を取り除き，最終的にカウンタが正になったらその分右括弧を取り除く．
□コード

import java.util.*;
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);

 void run(){
  char[]cs =sc.nextLine().toCharArray();
  int cnt=0;
  int stack=0;
  for(char c:cs){
   if(c=='(')
    stack++;
   else{
    if(stack==0)
     cnt++;
    else
     stack--;
   }
  }
  cnt+=stack;
  int length=cs.length-cnt;
  println(""+length);
 }

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

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

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

■C. Parquet
□問題
mxnの領域に1x2，2x1，2x2のタイルを敷き詰める問題．
□解法
m，nで場合わけして敷き詰めるだけ．実装ゲー．
□コード(適当でごめんなさい)

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

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

 int n, m, a, b, c;
 char[][] map;

 void run(){
  n=sc.nextInt();
  m=sc.nextInt();
  a=sc.nextInt();
  b=sc.nextInt();
  c=sc.nextInt();
  map=new char[n][m];
  if((m*n)%2!=0){
   println("IMPOSSIBLE");
   return;
  }
  if(n%2==0&&m%2==0){
   for(int j=0; j<n; j+=2){
    for(int i=0; i<m; i+=2){
     if(c>0){
      c--;
      char s=getDifferent(new int[]{i, i+1, i, i+1},
        new int[]{j, j, j+1, j+1});
      map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
     }else if(a>=2){
      char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
      map[j][i]=map[j][i+1]=s;
      char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
      map[j+1][i]=map[j+1][i+1]=t;
      a-=2;
     }else if(b>=2){
      char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
      map[j][i]=map[j+1][i]=s;
      char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
      map[j][i+1]=map[j+1][i+1]=t;
      b-=2;
     }else{
      println("IMPOSSIBLE");
      return;
     }
    }
   }
  }
  if(m%2==1){
   for(int j=0; j<n; j+=2){
    for(int i=0; i<m-1; i+=2){
     if(c>0){
      c--;
      char s=getDifferent(new int[]{i, i+1, i, i+1},
        new int[]{j, j, j+1, j+1});
      map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
     }else if(a>=2){
      char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
      map[j][i]=map[j][i+1]=s;
      char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
      map[j+1][i]=map[j+1][i+1]=t;
      a-=2;
     }else if(b>=2){
      char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
      map[j][i]=map[j+1][i]=s;
      char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
      map[j][i+1]=map[j+1][i+1]=t;
      b-=2;
     }else{
      println("IMPOSSIBLE");
      return;
     }
    }
   }
   for(int j=0; j<n; j+=2){
    if(b>0){
     char s=getDifferent(new int[]{m-1, m-1}, new int[]{j, j+1});
     map[j][m-1]=map[j+1][m-1]=s;
     b--;
    }else{
     println("IMPOSSIBLE");
     return;
    }
   }
  }
  if(n%2==1){
   for(int j=0; j<n-1; j+=2){
    for(int i=0; i<m; i+=2){
     if(c>0){
      c--;
      char s=getDifferent(new int[]{i, i+1, i, i+1},
        new int[]{j, j, j+1, j+1});
      map[j][i]=map[j][i+1]=map[j+1][i]=map[j+1][i+1]=s;
     }else if(b>=2){
      char s=getDifferent(new int[]{i, i}, new int[]{j, j+1});
      map[j][i]=map[j+1][i]=s;
      char t=getDifferent(new int[]{i+1, i+1}, new int[]{j, j+1});
      map[j][i+1]=map[j+1][i+1]=t;
      b-=2;
     }else if(a>=2){
      char s=getDifferent(new int[]{i, i+1}, new int[]{j, j});
      map[j][i]=map[j][i+1]=s;
      char t=getDifferent(new int[]{i, i+1}, new int[]{j+1, j+1});
      map[j+1][i]=map[j+1][i+1]=t;
      a-=2;
     }else{
      println("IMPOSSIBLE");
      return;
     }
    }
   }
   for(int i=0; i<m; i+=2){
    if(a>0){
     char s=getDifferent(new int[]{i, i+1}, new int[]{n-1, n-1});
     map[n-1][i]=map[n-1][i+1]=s;
     a--;
    }else{
     println("IMPOSSIBLE");
     return;
    }
   }
  }
  for(int j=0;j<n;j++){
   for(int i=0;i<m;i++){
    System.out.print(map[j][i]);
   }
   println("");
  }

 }

 char getDifferent(int[] xs, int[] ys){
  boolean[] exist=new boolean[256];
  for(int i=0; i<xs.length; i++){
   int x=xs[i];
   int y=ys[i];
   if(x>0)
    exist[map[y][x-1]]=true;
   if(x<m-1)
    exist[map[y][x+1]]=true;
   if(y>0)
    exist[map[y-1][x]]=true;
   if(y<n-1)
    exist[map[y+1][x]]=true;
  }
  for(int i=0; i<exist.length; i++)
   if(!exist[i]&&Character.isLowerCase(i))
    return (char)i;
  return 'E';
 }

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

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

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

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

■Result
○○○××
2626p
51位

■Rating
1744 -> 1851

現時点で92位．CodeforcesでならRedCoderを狙えるかも…．