TopCoder SRM 508

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

■DivideAndShift(Easy)

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

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にはいつ到達できるのか…．