問題
http://community.topcoder.com/stat?c=problem_statement&pm=11434&rd=14437
数字の列と、現在の位置が与えられる。
２つの操作のいずれかによって、位置を１番目に移動させたい。
・位置を右か左に移動
・現在の列数の素数で割り、列の長さを列／素数に変換
このときの最小の操作回数を求める。
解き方
N,Mが大きいのでdpでは配列を確保できない。
今回２つの匝瑳のうち、
移動の操作は割る操作よりも後で行えばよいので
各列についてたかだか１回の操作でよい。
よって各列について割る操作すべてについてBFSで調べていき、
また移動についても各列1度のみ調べていけばよい。
コード
class DivideAndShift {
public:
int getLeast(int N, int M) {
int ret=1e+9;
int prime[N+1];
memset(prime,1,sizeof(prime));
prime[0]=0,prime[1]=0;
for(int i=2;i<=N;i++)if(prime[i]){
for(int j=i+i;j<=N;j+=i)prime[j]=0;
}
queue<pair<pair<int,int>,int> > q;
q.push(make_pair(make_pair(N,M-1),0));
while(!q.empty()){
int x=q.front().first.first;
int pos=q.front().first.second;
int turn=q.front().second;
q.pop();
ret=min(ret,turn+min(pos,x-pos));
vector<int> vx;
for(int i=2;i*i<=x;i++)if(x%i==0){
if(prime[i])vx.push_back(i);
if(prime[x/i])vx.push_back(x/i);
}
if(prime[x])vx.push_back(x);
FORE(i,0,vx.size()){
int len=x/vx[i];
q.push(make_pair(make_pair(len,pos%len),turn+1));
}
}
return ret;
}
};
public:
int getLeast(int N, int M) {
int ret=1e+9;
int prime[N+1];
memset(prime,1,sizeof(prime));
prime[0]=0,prime[1]=0;
for(int i=2;i<=N;i++)if(prime[i]){
for(int j=i+i;j<=N;j+=i)prime[j]=0;
}
queue<pair<pair<int,int>,int> > q;
q.push(make_pair(make_pair(N,M-1),0));
while(!q.empty()){
int x=q.front().first.first;
int pos=q.front().first.second;
int turn=q.front().second;
q.pop();
ret=min(ret,turn+min(pos,x-pos));
vector<int> vx;
for(int i=2;i*i<=x;i++)if(x%i==0){
if(prime[i])vx.push_back(i);
if(prime[x/i])vx.push_back(x/i);
}
if(prime[x])vx.push_back(x);
FORE(i,0,vx.size()){
int len=x/vx[i];
q.push(make_pair(make_pair(len,pos%len),turn+1));
}
}
return ret;
}
};
Share this
Related Posts
SRM 500 DIV1 Easy - MafiaGame
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11342&rd=14429
解き方
投票数が一番多い人が最後に残る候補となる。
- SRM 492 DIV1 Easy - TimeTravellingGardener
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11060&rd=14245
解き方
２つの木のペアのいずれかの傾きが、最適な傾き
- SRM 559 DIV1 Easy - HyperKnight
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12201&rd=15181
解き方
サンプルを表に書いて見ると、各動ける数ごとに
- SRM 498 DIV1 Easy - FoxSequence
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11219&rd=14427
解き方
システムテストで落ちないような実装の正確性が求