Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

ウサギが座標xに居るとき,時間1後に4x+3か8x+7に移動できる.
1000000007の倍数の座標に移動するまでの最短時間を求める問題.
ただし,時間100000以下で辿り着けなければ,求めなくてよくて,それを指摘する.

解法

mod 1000000007の世界で考えれば良い.
f(x) = 2x+1とすると,f^2(x) = 4x+3, f^3(x) = 8x+7なので,
初期値からfを何回かますと0になるかを調べれば良くて,後はgreedyに8x+7から使っていく.
実際には,BFSしても,状態数が増えないことがわかるので,普通にBFSしても良い.

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

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

#define ll long long

#define N 100000
#define M 1000000007
int q[1000000],q_st,q_size;

class CarrotJumping {
public:
int theJump(int init) {
  int i,j,k,c;
  int next;
  map<int,int> mp;
  
  mp[init] = 0;
  q_st=0; q_size=0;
  q[q_st+q_size++]=init;

  while(q_size){
    k=q[q_st++]; q_size--;
    if(k==0) return mp[k];
    c=mp[k];
    if(c==N) continue;

    next = ((ll)k*4LL + 3LL)%M;
    if(mp.count(next)==0){
      mp[next]=c+1;
      q[q_st+q_size++]=next;
    }
    
    next = ((ll)k*8LL + 7LL)%M;
    if(mp.count(next)==0){
      mp[next]=c+1;
      q[q_st+q_size++]=next;
    }
  }
  
  return -1;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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