Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2037-fc6e5138
この記事にトラックバックする(FC2ブログユーザー)

SRM508 DIV1 EASY/DIV2 MEDIUM - DivideAndShift (この記事を編集する[管理者用])

Source

TopCoder SRM508 DIV1 EASY (250pt)
TopCoder SRM508 DIV2 MEDIUM (500pt)
Problem Statement
SRM508 DIV1 自分の参加記録

問題概要

N個 (1000000以下) の箱が一列に並んでいる.
M番目 (N以下) の箱だけに中身が入っている.
先頭の箱のみ,(時間0で)中身を取り出すことができる.
中身を取り出すまでの最小時間を求める問題.
できる操作は以下の3種類.両方とも時間1消費する.
 操作1: 先頭の箱を最後の箱の後ろに置く
 操作2: 最後の箱を先頭の箱の前に置く
 操作3: 素数pで,現在の箱の総数(n)を割り切れるものを1つ選ぶ.箱を先頭からn/p個ずつ,p個のグループに分けて,中身が入ってる箱のグループのみ残して,他の箱を破棄する

解法

Shift操作 (操作1と操作2) と,Divide操作 (操作3) は可換.更に,Divide操作同士も可換.(全ての操作は可換)
Shift操作のみの場合の答えは,最初から数えるか最後から数えて小さいほうなので,すぐわかる.
最後にShift操作をするとして,考えうるDivide操作を全部試す.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int getPrime(int n,int p[]){int i,j,n2=n/2;rep(i,n2)p[i]=1;for(i=3;i*i<n;i+=2)if(p[i>>1])for(j=(i*i)>>1;j<n2;j+=i)p[j]=0;j=1;p[0]=2;REP(i,1,n2)if(p[i])p[j++]=i*2+1;return j;}
int ps, p[1200000], is_p[1200000];

int solve(int N, int M, int st){
  int i,j,k;
  int res = N, tmp;

  if(res > M) res = M;
  if(res > N-M) res = N-M;

  REP(i,st,ps){
    if(p[i] > N) break;
    if(N % p[i]) continue;

    tmp = solve(N / p[i], M % (N/p[i]), i) + 1;
    if(res > tmp) res = tmp;
  }
  
  return res;
}

class DivideAndShift {
public:
int getLeast(int N, int M) {
  int i;
  
  ps = getPrime(1200000,p);
  rep(i,1200000) is_p[i]=0;
  rep(i,ps) is_p[p[i]]=1;
  
  return solve(N,M-1,0);
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2037-fc6e5138
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。