Hatena::Grouptopcoder

shnyaの参戦記録

2011-06-07練習

ちょっとした更新を使って上にあげてなかったのに間違ってあげてしまった。

練習としての自分用のメモなのでスルーしてください。

SRM 462 Div1 Easy AgeEncoding 02:08  [http://www.topcoder.com/stat?c=problem_statement&pm=10589:title=SRM 462 Div1 Easy AgeEncoding] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10589:title=SRM 462 Div1 Easy AgeEncoding] - shnyaの参戦記録

年齢ageをB進数で表した時、candlesLineという"010001"のような文字列にエンコードされる。

ageとcandlesLineが与えられた時に基数Bを答えよ。

Bは、実数。

最初は解析的に解けるかなーとちょっと考えてたけど、無理っぽかったので方針変更。単調増加なので2分探索で解く。

Div1の人間でも10%しか通っていない罠に自分もまんまとはまった。

class AgeEncoding {
  long double multi(const string &line, long double target){
    long double pow = 1.0;
    long double sum = 0.0;
    for(int i = 0; i < int(line.size()); i++){
      if(line[i] == '1') sum += pow;
      pow *= target;
    }
    return sum;
  }

public:
  double getRadix( int age, string candlesLine ) {
    long double lb = 0.0, ub = 1.0E+15;
    reverse(candlesLine.begin(),candlesLine.end());
    if(count(candlesLine.begin(),candlesLine.end(),'1') == 0)
      return -1;
    if(count(candlesLine.begin(),candlesLine.end(),'1') == 1
       && candlesLine[0] == '1'){
      if(age == 1) return -2;
      return -1;
    }
    if(count(candlesLine.begin(),candlesLine.end(),'1') > 1
       && candlesLine[0] == '1' && age == 1){
      return -1;
    }

    while(abs(ub - lb) > EPS){
      long double t = (ub - lb) / 2 + lb;
      if(multi(candlesLine,t) < (long double)age + EPS){
        lb = t;
      }else{
        ub = t;
      }
    }
    return lb;
  }
};

SRM 462 Div1 Medium CandyBox 02:08  [http://www.topcoder.com/stat?c=problem_statement&pm=10744&rd=14147:title=SRM 462 Div1 Medium CandyBox] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10744&rd=14147:title=SRM 462 Div1 Medium CandyBox] - shnyaの参戦記録

得点の違う飴がC個づつ、N個の箱に入っている。初期状態はスコアの違う飴は各箱に別れて置かれているが、S回任意の飴2個を選んで交換を行った時に、最終的に各箱の期待スコアはどうなっているか?

交換は完全にランダムとする。


Sの個数が普通にシミュレーションするだけではTLE解けないとばかり思っていて、答えを見てしまって、実はシミュレートで十分間に合うのか・・・。

ちゃんと問題を見返そう。

1問1問大事に解いていかないと意味がない。

以下kusanoさんの解答より。

http://d.hatena.ne.jp/kusano_prog/20100218/1266487237

メモとして書いておく。

class CandyBox {
public:
   vector <double> expectedScore( int C, vector <int> score, int S ) {
     vector<long double> v(score.begin(),score.end());
     int n = score.size();
     for(int i = 0; i < S; i++){
       vector<long double> v2 = v;
       for(int j = 0; j < n; j++){
         for(int k = 0; k < n; k++){
           v[j] += (v2[k]-v2[j])*2*C/(n*C)/(n*C-1);
         }
       }
     }
     return vector<double>(v.begin(),v.end());
   }
};

SRM 508 Div2 Hard YetAnotherORProblem2 02:16  [http://www.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437:title=SRM 508 Div2 Hard YetAnotherORProblem2] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437:title=SRM 508 Div2 Hard YetAnotherORProblem2] - shnyaの参戦記録

1 <= a_i <= Rの整数からなるN個の配列がある。

a_1 | a_2 | ... | a_n-1 | a_n = a_1 + a_2 + ... + a_n-1 + a_nとなるような並びは何通りあるか。

(|はOR演算)


ビットDPかなぁと思って考えてみるも、空間計算量がO(NR^2)ぐらいになってしまってちょっと厳しいなぁと思い、考え続けるも答えが出ない。


なんとか次元をひとつ落とせばなんとかなるかなぁといいなぁと思いつつも浮かばない。解いた人のコード見て、あぁ、こういう風に解けばいいのかと納得した。

ビットの部分集合を列挙するループの書き方はSigmarさんのブログを参考にしました。

http://topcoder.g.hatena.ne.jp/jackpersel/20100804/1281196966

LLI M = 1000000009LL;
LLI dp[2][1<<14];

class YetAnotherORProblem2 {
public:
  int countSequences( int N, int R ) {
    memset(dp,0,sizeof dp);
    for(int j = 0; j <= R; j++)
      dp[0][j] = 1;

    for(int i = 1; i < N; i++){
      for(int j = 0; j < (1 << 14); j++){
        dp[i%2][j] = dp[(i-1)%2][j];
        for(int k=j; k>0; k=(k-1)&j){
          if(k <= R){
            dp[i%2][j] += dp[(i-1)%2][j-k];
            dp[i%2][j] %= M;
          }
        }
      }
    }
    LLI res = 0;
    int last = (N-1)%2;
    for(int i = 0; i < (1 << 14); i++){
      res += dp[last][i];
      res %= M;
    }
    return res;
  }
};