Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM529 DIV1 MEDIUM - MinskyMystery (この記事を編集する[管理者用])

Source

TopCoder SRM529 DIV1 MEDIUM (600pt)
Problem Statement

問題概要

バッグ0~4のが5個あり,最初バッグ0にN個の石が入っている.(Nは10^12以下)
問題文に書かれている通りの動作を行った時,バッグに石を1個入れるという操作を何回することになるか mod 1000000009 で求める問題.
処理が終わらないならそれを指摘する.

解法

問題文の処理を噛み砕いて書くと,

  答え = 1;
  for(i=2;;i++){
    答え += 1;
    if(Nは正で,Nはiで割り切れる){
      答え += 3*N;
      答え += ceil(N/i)
      exit(0);
    } else {
      答え += 4*N;
      答え += ceil(N/i)
    }
  }

みたいな感じ.
ここで,iがどこで終了するかはO(sqrt(N))で計算でき,非自明な部分はceil(N/i)の和だけ.
これは,ceil(N/i)が一定になるiの範囲を計算して端折りつつ計算すればO(sqrt(N))でできる.
Nが0か1のときは終わらない.

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

#define ll long long
#define M 1000000009

class MinskyMystery {
public:
int computeAnswer(ll n) {
  ll i,j,lim;
  ll add;
  ll res = 1;

  if(n<=1) return -1;

  lim = n;
  for(i=2;i*i<=n;i++) if(n%i==0){ lim = i; break; }

  res += ( ((4*n)%M) * ((lim-1)%M) )%M;
  res += (lim-1)%M;
  res -= n;
  res %= M;

  for(i=2;i<=lim;i++){
    add = (n+i-1) / i;
    if(add > 1) j = (n-1) / (add-1); else j = i;
    if(j < i) j = i;
    if(j > lim) j = lim;
    res += (add%M) * ((j-i+1)%M);
    res %= M;
    i = j;
  }

  res %= M;
  if(res < 0) res += M;
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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