SRM564 - 不定期プログラミング覚え書き

ついに黄色から一発落ちしなかったのは久しぶりである。2012年最後のするめ。仮眠とってたら開始2分前とかに起きてわろた。

結果報告

Level	ProblemName	Status	Point
Easy	MonstersValley	PassedSystemTest	157.55
Medium	TheDivisionGame	Opened(practiced)	0.0
Hard	--	Unopened	0.0

2012年最後のレートは1599でした。
2011年最後が1488なので、あまり成長していないかも。あんまり体系的な練習してないしなあ、ううむ。

Easy MonstersValley

問題

モンスターが次々と現れてくる路がある。
モンスターの強さはdread[i]で表される。
プレイヤーはモンスターにお金を払い、モンスターを手下にすることが出来る。
モンスターはお金に目がないので、お金は1円か2円のどちらかで良い（必要額はprice[i]で表される）
プレイヤーの引き連れたモンスターの強さ合計値も新たに現れたモンスターの方が強く、かつモンスターを懐柔するだけのお金もない場合。
プレイヤーは喰われてしまう。
＊モンスターの強さが新たなモンスターより十分大きければ、プレイヤーはそのモンスターを手下にしても良いし、スルーしても良い。
この路を無事に渡り切るための最小な金額を答えよ

考えたこと

モンスター数は最大50なので、
どんだけ多く見積もっても100円あれば無事に生きて帰れる。
dp[i][j]を、i番目(i=0,1,...,モンスター数-1)のモンスターと対峙しており、これまでにj円支払った時の、自軍の強さの最大値とする。(-1の時、そのようなシチュエーションが存在しないとする)

dread[i] > dp[i][j]の時、かならずお金は払わなくてはいけない。dp[i+1][j+p[i]]よりdp[i][j]+dread[i]が大きい場合はそれに更新
dread[i] <= dp[i][j]の時、お金を払っても良いし、払わなくても良い。上の更新に加えて、dp[i+1][j]よりdp[i][j]が大きい場合はそれに更新。

これを繰り返して行って、dp[モンスター数][k]が-1でない最小のkを持ってくれば良い。

コード

  int minimumPrice(vector<long long> dread, vector <int> price){
   int size = dread.size();
      long long dp[51][202];
      for( int i = 0 ; i < 51; i++ ) for( int j = 0 ; j < 202; j++ ) dp[i][j] = -1;
      dp[0][0] = 0;
      for( int j = 0 ; j < size; j++){
        int p = price[j];
        ll d = dread[j];
        for( int k = 0 ; k <= 2*j; k++ ){
          if( dp[j][k] == -1 ) continue;
          //pay 
          dp[j+1][k+p] = max( dp[j+1][k+p],dp[j][k]+d );
          // not pay
          if( d <= dp[j][k] ){
            dp[j+1][k] = max( dp[j+1][k], dp[j][k] );
          }
        }
      }

      for( int j = 0 ; j <= size; j++ ){
        for( int k = 0 ; k <= 2*size; k++ ){
          cout << dp[j][k] << ", ";        
        }
        cout << endl;
      }
    for( int k = 0 ; k <= 201; k++ ){
      if( dp[size][k] >= dread[size-1] ) return k;
    }
    return 201;

  }

Medium TheDivisionGame

問題

数字の集合がある。
プレイヤーはその中の一つの数Xと、その1以外の約数Yを選び、XをX/Yで置き換えるとする。
この操作が行えなくなったプレイヤーが負けとなる。
[L,R]に含まれる連続した整数集合で、先手が勝つような集合は何通りあるか

考えたこと

grundy数の香りがやばい。
ゴリゴリ考えた結果
ある値が $p^2p_1^3$ と素因数分解出来た時のgrundy数って5だよね、と結論付ける。
素数K個（重複を許す）の積で表される値は、約数として素数m個（重複を許す)の積で表される物をとり、素数K-m個(重複を許す)の積で表される値となる
これはNimでいう、K個のコインからm個のコインをのぞいた状態に相当する。
じゃあとりあえず素因数分解して素因数の個数を覚えとくかー
…そっからどうするの？
てか、素因数分解TLEするんだけど？

復習

素因数分解を高速にする場合は、まずはエラトステネスの篩である。
何かRが1001000000を最大で取りうるからびびってたけど、実際に必要な素数ってその平方根で良かった。

また、素因数分解の個数を求めるだけならば、
for( n in [L,R] ) for(p in 素数列) if( n%p==0 )...
とするのは効率が悪いようだ。
確かにこれだと数列の要素数*素数列の個数if文が行われる事になるし、
この場合の素数ベクトルは3000くらいになるので、R-Lの最大値1000000と合わせると3*10^9で激しく微妙。

int calc[R-L+1];
int cnt[R-L+1];
for( int i = L ; i <= R; i++ ) calc[i-L]=i;
for( int i = L ; i <= R; i++ ) cnt[i-L]=0;
for( p in 素数列){
 start = L以上のpの倍数;
 for( int val = start ; val <= R ; val += p ){
  while( calc[val-L] % p == 0 ){
   calc[val-L]/=p;
   cnt[i-L]++;
  }
 }
}
for( int i = L ; i <= R; i++ ){
  if( calc[i-L]!= 1) cnt[i-L]++;
}

とすると、素数の値だけスキップされるので効率が良い。

最後に、素因数分解の個数をした後はどうするか？というと
「与えられた数列の連続部分列で、その要素をすべてxorしたら0となる個数」
が、先手が負けるパターン数である。
先頭からi番目までの値のxorをXORS[i]で表すような配列と、
先頭〜j(

コード

  long long countWinningIntervals(int L, int R){
    // thanks Leo.DingliYu 
    long long result = 0;
    int times[1000001];
    vector<int> primes;
    bool isprime[100000];
    memset( isprime, true, sizeof(isprime) );
    memset( times, 0 , sizeof(times) );
    isprime[0]=false;
    isprime[1]=false;
    for( ll i = 2 ; i*i <= R; i++ ){
      if( isprime[i] ){
        primes.push_back( i );
        for( ll j = i+i ; j*j <= R; j+= i ){
          isprime[j] = false;
        }
      }
    }
    int primesize = primes.size();
    //cout << primesize << endl;
    int NUM[1000001];
    for( int i = 0 ; i <= R-L ; i++ ){
      NUM[i] = L+i;
    }
    for( int j = 0 ; j < primesize; j++){
      ll p = primes[j];
      ll start = ((L+p-1)/p)*p;
      for( int i = start ; i <= R ; i+=p ){
        while( NUM[i-L]%p == 0 ){
          NUM[i-L]/=p;
          times[i-L]++;
        }
      }
    }
    for( int i = 0 ; i <= R-L ; i++ ){
      if( NUM[i] != 1 ) times[i]++;
      //cout << times[i] << endl;
    }
    int XORS[1000001];
    XORS[0] = times[0];
    for( int i = 1 ; i <= R-L ; i++ ){
      XORS[i] = XORS[i-1]^times[i];
    }
    long long tim[128];
    memset( tim , 0 , sizeof(tim) );
    tim[0]=1;
    for( int i = 0 ; i <= R-L ; i++ ){
      // see [L+?,L+i] = [L,L+i]-{L,L+?] 
      int tot = i+1;
      //cout << XORS[i]<<endl;
      tot -= tim[XORS[i]];
      result += tot;
      tim[XORS[i]]++;
    }
    return result;
    }