SRM 508 Div1 easy DivideAndShift

問題概要

長さNの配列のM番目にあるものがはいっている。
一番前にそれをもっていきたい。
以下の二つの操作がゆるされる。

• 任意の素数pについて、長さN/pのp個の配列に分割し、目標が含まれているものだけを残す。NはN/pになる。
• 全体を左にシフト、右にシフトできる。溢れたものは反対側に回る。

以下の操作はそれぞれ一回1個すとである。
何コストでM番目のものを一番左にもっていけますか。

解法

よこに動かす操作は後でまとめて行えばよい。
なぜなら、事前に動かしておかないとある場所に動かすのが遠くなるということが存在しないため。
それは、配列の最初と最後は繋がっていることから、より短い状態の時の方が移動コストが必ず少ないため。
分割の仕方を全部試す。
つまり約数を全部試す。
その分割に何コストかかるか計算する＝素因数の数。
分割された状態で、一番まえに持っていくのはどれだけコストがかかるか求め、
その合計の最小が答えである。

ソース

#include<vector>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

const int INF = 1000000000;
const int P = 1000001;

bool isPrime[P];
vector<int> V;

void makePrime(){
  rep(i, P)isPrime[i] = true;
  isPrime[0] = isPrime[1] = false;
  rep(i, P){
    if(!isPrime[i])continue;
    V.push_back(i);
    for(int j = 2; j*i < P; j++){
      isPrime[i*j] = false;
    }
  }
}

int CNT(int n){
  int cnt =0;
  FOR(it, V){
    while(n % (*it) == 0){
      cnt++;
      n/= (*it);
    }
  }
  return cnt;
}
class DivideAndShift {
public:
  int getLeast(int N, int M) {
    V.clear();
    makePrime();
    M--;
    int ans = INF;
    REP(i, 1, N+1){
      if(N%(i) != 0)continue;
      int cost = CNT(i);
      int length = N / (i);
      ans = min(ans, cost + min(M%length, length - M%length));
    }
    return ans;
  }
};