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種類． つまり，p¹, p²,…, p^rについて有効な文字列は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シャツをゲットできそうです．