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

0 件のコメント: