TopCoder SRM617 DIV1 EASY - MyLongCake/DIV2 HARD - MyVeryLongCake

Source

TopCoder SRM617 DIV1 EASY (250pt)
TopCoder SRM617 DIV2 HARD (1000pt)
Problem Statement (DIV1 EASY)
Problem Statement (DIV2 HARD)

問題概要

$1$ 次元の長さ $N$ の棒ケーキがある.
明日はパーティーで,$N$ 未満の $N$ の約数の人数だけ友だちが来ることがわかっているが,実際に何人来るかは最初の友だちが来る直前にわかる.
ケーキを幾つかの長さに切っておいて,最初の人から,まだ渡していない連続する左の部分を幾つかを渡して,全員に合計としては同じ量だけ渡したい.
今日のうちにどんな人数が来ても対応できるように,ケーキを切っておきたい.
最小で,ケーキを何個の部分に分割すればよいかを求める問題.

解法

DIV1 EASYでは,何人来るかを全部試して,切らなければいけない場所を切って行って,最後に切れている部分の数を数えれば良い.
約数の数は大きくないし,人数が小さいと飛ばし飛ばし切るので十分に間に合う.高々$O(N \log N)$.
DIV2 HARDでは,それでは間に合わない.(メモリも足りない)
左から長さ $k$ の部分が切られるかどうかを考える.
もし,${\rm GCD}(N, k) = x > 1$ であれば,友達が $N/x$ 人来た時にその場所は切られないといけない.
そこで,切られない場所は ${\rm GCD}(N, k) = 1$ となる場所のみで,切られない場所の数を数えるのはEulerの $\varphi$ 関数を計算することになる.
Eulerの $\varphi$ 関数は $N$ の素因数さえわかれば計算できるので,$O(\sqrt{N})$ 程度で計算できる.

C++によるスパゲッティなソースコード (DIV1 EASY)

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int a[1000000];

class MyLongCake {
public:
int cut(int n) {
  int i, j, k;
  int res=1;

  rep(i,n+1) a[i] = 0;
  REP(k,1,n) if(n%k==0){
    for(i=n/k;i<n;i+=n/k) a[i]++;
  }
  rep(i,n) if(a[i]) res++;

  return res;
}

}

C++によるスパゲッティなソースコード (DIV2 HARD)

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class MyVeryLongCake {
public:
int cut(int n) {
  int i, res = n, tot = n;

  for(i=2;i*i<=n;i++) if(n%i==0){
    while(n%i==0) n /= i;
    res = res / i * (i-1);
  }
  if(n > 1) res = res / n * (n-1);

  return tot - res;
}

}

Current time: 2024年03月30日00時09分18秒
Last modified: 2014年04月22日13時12分55秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM617 SRM_Div1_Easy SRM_Div2_Hard
トップページに戻る

Logged in as: unknown user (not login)

ログイン: