Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

1~Nまでの数字が順番に並んでいる.
step kでは,残ってる数字の中で
 1, 1+(k+1), 1+2*(k+1), ... 番目
の数字が順番に消される.
最後に消える数字は何かを求める問題.
DIV1ではNは2000000以下.
DIV2ではNは10000以下.

解法

DIV1,DIV2ともに愚直にシミュレーションしても間に合う.
DIV1では,あまりにも効率的じゃない方法で実装するとTLEする可能性もある.
ヨセフス数みたいな感じでDPすると早い.
以下のコードはシミュレーション.(DIV1向け)

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 now[2100000], next[2100000];

class LockersDivOne {
public:
int lastOpened(int N) {
  int i,j,k,sz;
  int last;

  rep(i,N) now[i]=i; sz=N;
  for(k=2;sz;k++){
    j=0;
    rep(i,sz){
      if(i%k==0) last=now[i];
      else next[j++]=now[i];
    }
    sz=j;
    rep(i,sz) now[i]=next[i];
  }

  return last+1;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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