2011年6月29日水曜日

TCO Algorithm Round2

TCO Algorithm Round2(6/26 1:00~3:00)

驚異の悪運によりRound1を通過することが出来ていましたが,果してRound2は….

■GuessTheNumberGame(Easy)

ある数字Mを1~Nまでの数で割り切れるかどうかを表す文字列を考える. 例えばM=4,N=5とすると4は1,2,4で割り切れ,3,5では割り切れないので, YYNYN となる. さて,N=5のとき, YNNYN となるようなMは存在しないため, この文字列は無効である(4で割り切れて、2で割り切れないから). 長さMの文字列で,有効なものは何種類あるか. 2種類以上の素数の積からなる合成数は, 素因数のY or Nで一意に決まってしまうので,考慮しない. 例えば, YYY--XならX=Y YYN--XならX=N YNY--XならX=N YNN--XならX=N となる. 次に,ある素数の冪乗を考える. 例えば,M=9とすると,2の冪乗は2,4,8まで.この3つに着目した有効な文字列は, NNN YNN YYN YYY の4種類. つまり,p1, p2,…, prについて有効な文字列はr+1種類. あとは,それらを掛け合わせるだけ.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class GuessTheNumberGame {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int possibleClues(int n) {
  long res=1;
  long mod=1000000007;
  boolean[] isP=new boolean[n+1];
  int[] p=new int[n+1];
  fill(isP,true);
  isP[0]=isP[1]=false;
  int k=0;
  for(int j=0;j<=n;j++){
   if(!isP[j]){
    continue;
   }
   p[k++]=j;
   for(int i=j*2;i<=n;i+=j){
    isP[i]=false;
   }
  }
  // debug(p);
  for(int i=0;i<k;i++){
   int c=0;
   for(long m=1;m<=n;m*=p[i]){
    c++;
   }
   // debug(i,p[i],c);
   res=(res*c)%mod;
  }
  return (int)res;
 }

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

■Challenge Phase

撃墜無し.

■Result

o-- +0/-0
196.11pts. 341th
辛くも逃げきることが出来ました.

■Rating

1431 -> 1530
Round3進出+初YellowCoderです. 今年のICPCは国内予選で落ちてしまったので,中々にショックでしたが, 代わりにGoogleとTopCoder両方のTシャツをゲットできそうです.

0 件のコメント: