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種類． あとは，それらを掛け合わせるだけ．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class GuessTheNumberGame {  
10.  // long INF=1L<<48;  
11.  int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  public int possibleClues(int n) {  
15.   long res=1;  
16.   long mod=1000000007;  
17.   boolean[] isP=new boolean[n+1];  
18.   int[] p=new int[n+1];  
19.   fill(isP,true);  
20.   isP[0]=isP[1]=false;  
21.   int k=0;  
22.   for(int j=0;j<=n;j++){  
23.    if(!isP[j]){  
24.     continue;  
25.    }  
26.    p[k++]=j;  
27.    for(int i=j*2;i<=n;i+=j){  
28.     isP[i]=false;  
29.    }  
30.   }  
31.   // debug(p);  
32.   for(int i=0;i<k;i++){  
33.    int c=0;  
34.    for(long m=1;m<=n;m*=p[i]){  
35.     c++;  
36.    }  
37.    // debug(i,p[i],c);  
38.    res=(res*c)%mod;  
39.   }  
40.   return (int)res;  
41.  }  
42.   
43.  void debug(Object...os){  
44.   System.err.println(Arrays.deepToString(os));  
45.  }  
46.   
47.  void print(String s){  
48.   System.out.print(s);  
49.  }  
50.   
51.  void println(String s){  
52.   System.out.println(s);  
53.  }  
54. }  

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シャツをゲットできそうです．