SRM541

眠気に負けて不参加だったので，後日EasyMediumだけ解いた．
どちらもre-submitを１回以上要したので，参加してたら痛い目にあっていただろうなあ.
ちなみに250-550-1000回．

Level	ProblemName	Status	Point
Easy	AntsMeet	PassedSystemTest(Practice)	----
Medium	AkariDaisukiDiv1	PassedSystemTest(Practice)	----
Hard	XorLife	Unopened	----

Easy AntsMeet

問題

アリの初期位置と移動方向の組合せが与えられる．
複数のアリが出会うとそこでアリは消滅することが知られている．
最後まで生き残るアリの数を答えよ

考えたこと

初期位置の範囲が-1000から1000くらいで，移動方向は座標軸に平行な１方向．
つまり2000ステップくらいでアリの数は収束するはずなので，愚直にシミュレーションすれば良い．

と思って書いたら，(0,0)から右に行くアリと(1,0)から左に行くアリの衝突を無視していた／(^o^)＼

ならばマイステップ0.5ずつ進むようにすれば，まあ4000ステップのシミュレートだし，なんとかなるよね．

コード

 int countAnts(vector <int> x_, vector <int> y_, string direction) {
    int result;
    bool exist[51];
    vector<double> x ;
    vector<double> y ;
    double dx[51];
    int size = x_.size(); 
    double dy[51];
    memset( exist, true, sizeof( exist ) );
    memset( dx, 0 , sizeof( dx ) );
    memset( dy, 0 , sizeof( dy ) );
    for( int i = 0 ; i < size; i++ ){
      if( direction[i] == 'N' ) dy[i] =0.5;
      if( direction[i] == 'S' ) dy[i] =-0.5;
      if( direction[i] == 'W' ) dx[i] =-0.5;
      if( direction[i] == 'E' ) dx[i] = 0.5;
      x.push_back( x_[i] );
      y.push_back( y_[i] );
    }
    for( int loop = 0 ; loop <= 4000; loop++ ){
      //move
      for( int i = 0 ; i < size; i++ ){
        if( exist[i] ){
          x[i] += dx[i];
          y[i] += dy[i];
        }
      }
      //check
      for( int i = 0 ; i < size; i++ ){
        if( !exist[i] ) continue;
        for( int j = i+1 ; j < size; j++ ){
          if( !exist[j] ) continue;
          if( x[i] == x[j] && y[i] == y[j] ){
            exist[i]= false;
            exist[j] = false;
          }
        }
      }
    }
    result = 0;
    for( int i = 0 ; i < size; i++ ){
      if( exist[i] ) result++;
    }
    return result;
  }

計算量はありの数をNとして．
Nが最大50なので許容範囲．

Medium AkariDaisukiDiv1

問題文

文字列に対して，
関数を，と定義する．
の中に文字列Fが何個含まれているかをmod 1000000007で返せ

考えたこと

問題文の出落ちっぷりがやばい．

説明を呼んで

Sigmar氏の説明（http://topcoder.g.hatena.ne.jp/jackpersel/20120425/1335370326）を読んだら理解した気になった．
ポイントは，Fの長さが50以下であることから，

• fを50回繰り返したらWaai+...の部分に含まれるFの個数，...+Akari+...に含まれるFの個数，...+Daisukiに含まれるFの個数はすべて定常状態に達する
• 50回繰り返して無いにしても，Waai,Akari,Daisukiに連結する箇所で覚えるべきなのは，前の文字列の最初50文字＆後ろ50文字までで良い

という事らしい．
でもいざ実装してみると結構グダグダになった＆細かなミスで3回くらいre-submitした．
本番でこういうの書けるようになりたいなあ

コード

  int countF(string Waai, string Akari, string Daisuki, string S, string F, int k) {
    long long result=0;
    int mod = 1000000007;
    string now = S;
    string first50,last50;
    int Flen = F.size();
    int result_tmp =0;
    int loop;
    for( loop = 0 ; loop < min( 51, k ) ; loop++ ){
      if( now.size() < 51 ){
        now = Waai + now + Akari +now + Daisuki;
        result_tmp = 0;
        for( int i = 0 ; i < (int)now.size(); i++){
          if( now.substr( i, Flen ) == F ){
            result_tmp++;
          }
        }
        result = result_tmp;
        if( (int)now.size() >= 51 ){
          first50 = now.substr(0,50);
          last50 = now.substr( now.size()-50 );
        }
        result %= mod;
      }else{
        // in this case, it is impossible we can find F from Waai+S+Akari and
        // Akari+S+Daisuki.
        // we can just find F from Waai+S, S+Akari+S, or S+Daisuki
        string middle = last50+Akari+first50;
        int last50size = last50.size();
        first50 = Waai + first50;
        last50 = last50 + Daisuki;
        //Waai + ...
        result_tmp = 0;
        for( int i = 0 ; i < (int)Waai.size() ; i++ ){
          if( first50.substr(i,Flen) == F ) result_tmp++;
        }
        // ....+ Daisuki
        for( int i = 0 ; i < (int)Daisuki.size(); i++ ){
          if( last50.substr(last50.size()-Flen-i,Flen) == F ) result_tmp++;
        }
        // ...+Akari+...
        for( int i = 0 ; i < last50size+(int)Akari.size(); i++ ){
          if( i+Flen <= last50size ) continue;
          if( middle.substr( i , Flen ) == F ) result_tmp++;
        }
        result = result*2+result_tmp;
        result %= mod;
        first50 = first50.substr(0,50);
        last50 = last50.substr( last50.size()-50);
      }
    }
    for( ; loop < k ; loop++ ){
      result = result*2 + result_tmp;
      result %= mod;
    }
    return result;
  }