Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-08-04SRM478 Div1

SRM478 Div1 250 CarrotJumping

| 00:12 | SRM478 Div1 250 CarrotJumping - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM478 Div1 250 CarrotJumping - SRM diary(Sigmar) SRM478 Div1 250 CarrotJumping - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→Hanako・・?これがいわゆるrngさんというやつだろうか

→普通に探索すると、2^10万??うむ・・何だこれは・・・全然分からない

DPか・・?うーん状態数が多すぎる・・違う・・逆方向に探索?・・・意味ないな・・分からん・・

→(20分くらい悩む)

→というか250点なんだから、何か簡単に解く方法があるはずだ

→こういう分からないときはとりあえずシミュレーションしてみるに限る

→えーと・・4x+3を2回適用すると16x+15、3回で64x+63

→8x+7を2回適用すると64x+63・・・

→・・・ん?

→全然分岐しないじゃないか

→4x+3を15万回くらい繰り返して適当に帳尻合わせれば解ける気がしてきた

→書く→サンプル合わない

→4x+3だけ適用しているから、8x+7を1回適用でOKの場合が探索できないのがまずいみたい

→4x+3と8x+7はどちらから適用しても32x+31となり、順番には依存しないので、探索の途中で毎回8x+7追加適用を試すように変更

→書く→サンプル通る

→サンプルが網羅的な感じのケースで親切だから問題なさそうかな

→提出


チャレンジフェーズ

→みんな色んな解き方してるみたいだなぁ

→何か良く分からない。サンプル親切だし落とせそうなケースも思いつかないな

→何もせず


システムテスト

→Passed


以下、ソースです。

25分くらいかかってしまったので、もっと早くシミュレーションすれば良かった・・・

const int MOD=1000000007; 

class CarrotJumping { 
public: 
  int theJump(int init) { 
    if(init==0) return 0; 
    for(int i=1; i<=150000; i++) { 
      int tmp=((ll)init*8+7)%MOD; 
      if(tmp==0) { 
        if((i-1)/3*2+(i-1)%3+1>100000) return -1; 
        return (i-1)/3*2+(i-1)%3+1; 
      } 
      init=((ll)init*4+3)%MOD; 
      if(init==0) { 
        if(i/3*2+i%3>100000) return -1; 
        return i/3*2+i%3; 
      } 
    } 
    return -1; 
  } 
}; 

ElizaFerrerElizaFerrer2018/11/20 05:13AIやコグニティブ・コンピューティングを利用する場合、その最終的な目標は、機械が画像・音声解釈機能で人間のプロセスをシミュレートし、人間と理路整然と会話できるようにすることです。 <a href=https://jamedbook.com/12-8/>https://jamedbook.com/12-8/</a> ぬれたタオルやトイレの便座などからも感染することがあります。 女性の場合、外陰部にかゆみや灼熱感があったり、おりものが増えたりします。