TopCoder SRM 508

SRM 508(6/3 0:00~2:00)

■DivideAndShift(Easy)

答えをf(n,m)として，再帰的に解きました．
素因数分解をして，素数のべき乗ごとに再帰するので， 制限時間には余裕で間に合います．

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 DivideAndShift {  
10.  int INF=1<<28;  
11.  double EPS=1e-9;  
12.   
13.  int rec(int n, int m){  
14.   if(m==0){  
15.    return 0;  
16.   }  
17.   HashMap<Integer,Integer> map=primeFactor(n);  
18.   int res=min(m,n-m);  
19.   for(int p:map.keySet()){  
20.    if(p==1){  
21.     continue;  
22.    }  
23.    res=min(res,rec(n/p,m%(n/p))+1);  
24.   }  
25.   return res;  
26.  }  
27.   
28.  public int getLeast(int n, int m) {  
29.   return rec(n,m-1);  
30.  }  
31.    
32.  HashMap<Integer, Integer> primeFactor(int n){  
33.   HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();  
34.   for(int i=2; i*i<=n; i++){  
35.    int c=0;  
36.    for(; n%i==0; n/=i)  
37.     c++;  
38.    if(c>0)  
39.     map.put(i, c);  
40.   }  
41.   if(n!=1)  
42.    map.put(n, 1);  
43.   return map;  
44.  }  
45.   
46.  void debug(Object...os){  
47.   System.err.println(Arrays.deepToString(os));  
48.  }  
49.   
50.  void print(String s){  
51.   System.out.print(s);  
52.  }  
53.   
54.  void println(String s){  
55.   System.out.println(s);  
56.  }  
57. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class DivideAndShift {
 int INF=1<<28;
 double EPS=1e-9;

 int rec(int n, int m){
  if(m==0){
   return 0;
  }
  HashMap<Integer,Integer> map=primeFactor(n);
  int res=min(m,n-m);
  for(int p:map.keySet()){
   if(p==1){
    continue;
   }
   res=min(res,rec(n/p,m%(n/p))+1);
  }
  return res;
 }

 public int getLeast(int n, int m) {
  return rec(n,m-1);
 }
 
 HashMap<Integer, Integer> primeFactor(int n){
  HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
  for(int i=2; i*i<=n; i++){
   int c=0;
   for(; n%i==0; n/=i)
    c++;
   if(c>0)
    map.put(i, c);
  }
  if(n!=1)
   map.put(n, 1);
  return map;
 }

 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
125.55pts. 406th

■Rating

1365 -> 1414
微増．目標の1500にはいつ到達できるのか…．