SRM478 Div2

勉強になる。

250 KiwiJuiceEasy

やるだけだった。

500 CarrotJumping

今いるところxから、「4*x+3」か「8*x+7」の場所へ飛べる。100000回まで繰り返して、100,000,007で割り切れる場所でとまれるかどうか、止まれる回数を出力。

mod 1000000007で考えるのはいいけど、

bool memo[1000000007];
for(int i=0; i<1000000007; i++) memo[i] = false; //あほ

とかやったら2秒じゃ終わらなくてorz
とりあえず全探索してみようと思ったら全然計算が終わらない＆上のせいで計算済みの場所も無駄に計算。
数学的に簡単な式で表現できるのかといじってみてもうまくできず。惨敗。

結局、聞いたところ、メモ付きBFSでできたということで、書いたら通った。

class CarrotJumping {
  public:
  int theJump(int init) {
    ll a;
    vector<ll> n, p;
    p.push_back(init);
    map<ll,int> memo;
    for(int s=1; s<=100000; s++){
      n = p;
      p.clear();
      for(int i=0; i<n.size(); i++){
        if(memo[n[i]]==0){
          memo[n[i]] = 1;
          a = n[i];
          a = (4*a+3)%1000000007;
          if(a==0) return s;
          if(memo[a]==0) p.push_back(a);
          a = n[i];
          a = (8*a+7)%1000000007;
          if(a==0) return s;
          if(memo[a]==0) p.push_back(a);
        }
      }
    }
    return -1;
  }
};

1000

見てない。

撃墜

ソース見てたら怪しいことやってたのでやってみたら失敗したorz -25
もっと慎重に。

反省

• 撃墜は慎重に。
• メモはmapを使うようにする。