naoya_t@topcoder

SRM421

10.08+.2008

TopCoder SRM (Single Round Match) 参加６回目。DIV1では３回目。

同じ部屋にnyaさんとかいるし

DIV	level	問題名	競技中	後で	System Test	備考
1	250	EquilibriumPoints	途中	o	passed	10/22 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081022/p1 74.05%
1	500	CakesEqualization	◎		passed
1	1000	(TeamManagement)

250点問題: EquilibriumPoints

ごにょごにょ書いてるうちに頭が真っ白になったので飛ばすことにした。500点問題に専念。

500点問題: CakesEqualization

解けた。でかい数字を入れたテストケースも作って試してみる。激しい腹痛に襲われたのでsubmit。250点問題ってもしかしてバイナリサーチで解けるじゃないか？とふと思ったが残り時間わずか。

1000点問題

開いたけど覚えてない。トイレに直行。

500点×1で238.64点。

• チャレンジタイム：何人かにチャレンジされたけど耐えた。皆さんの250点問題のソース見たらやっぱりバイナリサーチでやってる。
• システムテスト：OK

250点問題を飛ばしたにも関わらず、20人部屋で上から5番目。DIV1全体では118/677位。

レーティングは 1212 → 1441 に上がる。青丸の中身がほぼ一杯になっている。500点問題を確実に取れれば上（黄色）に上がれるということか。引き続き頑張ろう。

SRM418 Div1 Medium: StampsCollection

過去問, 練習 | 18:14 |

練習のために過去問を解いてみる。

SRM418の時はDIV2だったので、DIV1の500点問題「StampsCollection」に挑戦、の巻。いい勉強になったので、たどった道順を（覚えている範囲で）メモに残しておく。

最初、greedyな感じにざっくり書いてみる。

#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class StampsCollection {
public:
  int sell(int n, vector<string> demand, vector<int> price) {
    // n[1..50] stamps : [0 .. n-1],
    // demand[i] 1..50 elements, 0..n-1 [space 0..n-1]
    // price: 1..1000000
    int buyers = demand.size();
    vector<bool> sold_out(n);
    int amount = 0;
    tr(sold_out,it) *it = false;

    vector< vector<pair<double,int> > > candidates(n);
    vector< pair<double,pair<int,vector<int> > > > demand_(buyers);
    for (int i=0; i<buyers; i++) {
      vector<int> buyer_wants = map_atoi( split(demand[i]) );
      int total_price = price[i];
      double unit_price = 1.0 * total_price / buyer_wants.size();
      
      tr(buyer_wants,it) candidates[*it].push_back( make_pair(-unit_price, i) );
      
      demand_[i] = make_pair( -unit_price,
                              make_pair( total_price, buyer_wants ));
    }
    sort(demand_.begin(), demand_.end());
    // cout << demand_ << endl;
    tr(candidates,it) sort(it->begin(), it->end());
    cout << candidates << endl;
    
    tr(demand_,it) {
      vector<int> buyer_wants = it->second.second;
      bool sellable = true;
      tr(buyer_wants,jt) {
        if (sold_out[*jt]) { sellable = false; break; }
      }
      if (sellable) {
        amount += it->second.first;
        tr(buyer_wants,jt) sold_out[*jt] = true;
      }
    }
    return amount;
  }
};

当然のことながら、これは問題文についているようなTest Caseでは通るがChallenge Phaseで撃沈するタイプ。

DPに切り替えてみる。

• 最初に、buyersを提示価格の高い順にソート
• 高いほうから１人ずつ、その売人(Aとする)に売る場合と売らない場合に分けて考える。
• 売る場合）希望商品が売人Aとかぶっている売人を全部消す。売人Aの提示価格は売上に確定。残った商品を残った売人で競う。
• 売らない場合）売人Aを消して、残りの売人で商品を競う。残りの売人の提示価格の合計が売人Aの提示価格に満たない場合はこれは考慮する必要がない。

#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class StampsCollection {
  map<vector<pair<int,long long> >,int> m;
private:
  int sub(vector< pair<int,long long> > price_and_mask, int sum) {
    int size = price_and_mask.size();
    if (size == 0) return 0;
    if (size == 1) return -(price_and_mask[0].first);
    if (m.find( price_and_mask ) != m.end()) return m[ price_and_mask ];
    
    // take #0
    long long sold_out = price_and_mask[0].second;
    vector< pair<int,long long> > price_sub1;
    int sum1 = 0;
    for (int i=1; i<size; i++) {
      if ((sold_out & price_and_mask[i].second) == 0) {
        price_sub1.push_back( price_and_mask[i] );
        sum1 -= price_and_mask[i].first;
      }
    }
    int amount1 = - price_and_mask[0].first + sub(price_sub1, sum1);

    m[ price_and_mask ] = amount1;
    int *m_it = &m[ price_and_mask ];

    // don't take #0
    sum -= price_and_mask[0].first;
    if (sum < amount1) {
      return amount1;
    } 

    price_and_mask.erase(price_and_mask.begin(), price_and_mask.begin()+1);
    int amount2 = sub(price_and_mask, sum);
    if (amount2 > amount1) {
      *m_it = amount2;
      return amount2;
    } else {
      return amount1;
    }
  }

public:
  int sell(int n, vector<string> demand, vector<int> price) {
    long long n_mask = ((long long)1 << n) - 1;

    int buyers_cnt = demand.size();
    vector< pair<int,long long> > price_and_mask(buyers_cnt);
    int sum = 0;
    for (int i=0; i<buyers_cnt; i++) {
      vector<int> demand_i = map_atoi( split(demand[i]) );
      long long mask = 0;
      tr(demand_i,it) mask |= ((long long)1 << *it);
      mask &= n_mask;
      price_and_mask[i] = make_pair(-price[i], mask);
      sum += price[i];
    }
    sort(price_and_mask.begin(), price_and_mask.end());
    
    return sub(price_and_mask,sum);
  }
};

• 提示価格, 買いたい商品リスト（long longのビットマスクで表現）のペアをリストにして再帰関数に渡している。
• 同じサブセットについて計算が行われることがあるのでメモ化。

これで解けるんだけど、件数が増えると時間オーバーでシステムテストは通らない。

• mapのキーにペアのvectorを渡しても行けるということは分かったがどう考えても遅そう
• 残った売人（高々50人）のビットを立てた signature という数値を用意し、これをキーにしよう
• その為には個々の売人のID（ないしマスク）が必要
• price_and_mask について。第１要素を消すだけの処理なら、vectorよりdeque使ったらどうなんだろう

#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class StampsCollection {
  map<long long,int> m;

private:
  int sub(deque<pair<int,pair<long long, long long> > > price_and_mask, long long signature, int sum) {
    int size = price_and_mask.size();
    if (size == 0) return 0;
    if (size == 1) return -(price_and_mask.front().first);
    if (m.find( signature ) != m.end()) return m[ signature ];

    // take #0
    long long sold_out = price_and_mask.front().second.second;
    deque< pair<int,pair<long long, long long> > > price_sub1;
    long long new_signature = 0;
    int sum1 = 0;
    tr(price_and_mask,it) {
      if ((sold_out & it->second.second) == 0) {
        price_sub1.push_back( *it );
        new_signature |= it->second.first;
        sum1 -= it->first;
      }
    }
    int amount1 = - price_and_mask.front().first + sub(price_sub1, new_signature, sum1);

    // don't take #0
    sum -= price_and_mask.front().first;
    if (sum < amount1) {
      m[ signature ] = amount1;
      return amount1;
    } 

    new_signature = signature - price_and_mask.front().second.first;
    price_and_mask.pop_front();
    int amount = max(amount1, sub(price_and_mask, new_signature, sum));
    m[ signature ] = amount;
    return amount;
  }

public:
  int sell(int n, vector<string> demand, vector<int> price) {
    m.clear();
    // n[1..50] stamps : [0 .. n-1],
    // demand[i] 1..50 elements, 0..n-1 [space 0..n-1]
    // price: 1..1000000
    long long n_mask = ((long long)1 << n) - 1;

    int buyers_cnt = demand.size();
    long long signature = ((long long)1 << buyers_cnt) - 1;
    vector< pair<int,pair<long long,long long> > > price_and_mask_v(buyers_cnt);
    int sum = 0;
    for (int i=0; i<buyers_cnt; i++) {
      vector<int> demand_i = map_atoi( split(demand[i]) );
      long long mask = 0;
      tr(demand_i,it) mask |= ((long long)1 << *it);
      mask &= n_mask;
      price_and_mask_v[i] = make_pair(-price[i], make_pair((long long)1 << i, mask));
      sum += price[i];
    }
    sort(price_and_mask_v.begin(), price_and_mask_v.end());
    deque< pair<int,pair<long long, long long> > > price_and_mask(price_and_mask_v.begin(), price_and_mask_v.end());
    
    return sub(price_and_mask,signature,sum);
  }
};

まだ時間切れケースがある。

• 希望商品が同じ組合せの売人が大量にいるケースでexponentialに時間を消費しているっぽいので、提示価格がいちばん高い売人を残して消すようにしてみる。
• dequeにした速度的メリットはなかったようなのでvectorに戻す。
• 売人：提示価格、売人：希望商品の対応は外で持っておき、売人リストだけを渡すようにしてみる。

#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class StampsCollection {
  map<long long,int> memo;
  map<long long, long long> demand_patterns; // demand_patterns[buyer_signature] = demand_pattern
  map<long long, long long> demand_patterns_rev; // demand_patterns_rev[demand_mask] = buyer_signature
  map<long long, int> prices;

private:
  int sub(vector<long long> buyers_sorted, long long all_buyers_signature, int sum) {
    int size = buyers_sorted.size(); // = __builtin_popcount(all_buyers)
    if (size == 0) return 0;

    long long top_buyer = buyers_sorted[0];
    if (size == 1) return prices[top_buyer];
    if (memo.find( all_buyers_signature ) != memo.end()) return memo[ all_buyers_signature ];

    long long sold_out = demand_patterns[top_buyer];
    vector<long long> buyers_sub;
    long long buyers_sub_signature = 0;
    int sum1 = 0;
    for (int i=1; i<size; i++) {
      long long one = buyers_sorted[i];
      if ((sold_out & demand_patterns[one]) == 0) {
        buyers_sub.push_back(one);
        buyers_sub_signature |= one;
        sum1 += prices[one];
      }
    }
    int amount1 = prices[top_buyer] + sub(buyers_sub, buyers_sub_signature, sum1);

    sum += prices[top_buyer];
    if (sum < amount1) {
      memo[ all_buyers_signature ] = amount1;
      return amount1;
    }

    buyers_sorted.erase(buyers_sorted.begin(), buyers_sorted.begin()+1);
    buyers_sub_signature = all_buyers_signature - top_buyer;

    int amount = max(amount1, sub(buyers_sorted, buyers_sub_signature, sum));
    memo[ all_buyers_signature ] = amount;
    return amount;
  }

public:
  int sell(int n, vector<string> demand, vector<int> price) {
    memo.clear();
    demand_patterns.clear(); // demand_patterns[buyer_signature] = demand_pattern
    demand_patterns_rev.clear(); // demand_patterns_rev[demand_mask] = buyer_signature
    prices.clear();

    // n[1..50] stamps : [0 .. n-1],
    // demand[i] 1..50 elements, 0..n-1 [space 0..n-1]
    // price: 1..1000000
    long long n_mask = ((long long)1 << n) - 1;

    int buyers_cnt = demand.size();
    long long all_buyers_signature = ((long long)1 << buyers_cnt) - 1;

    set<long long> buyers;
    int sum = 0;
    for (int i=0; i<buyers_cnt; i++) {
      long long buyer_signature = (long long)1 << i;
      buyers.insert(buyer_signature);

      vector<int> demand_i = map_atoi( split(demand[i]) );
      long long demand_pattern = 0;
      tr(demand_i,it) demand_pattern |= ((long long)1 << *it);
      demand_pattern &= n_mask;
      demand_patterns[buyer_signature] = demand_pattern;
      prices[buyer_signature] = price[i];
      
      if (demand_patterns_rev.find(demand_pattern) != demand_patterns_rev.end()) {
        long long old_buyer_signature = demand_patterns_rev[demand_pattern];
        if (prices[old_buyer_signature] < price[i]) {
          all_buyers_signature -= old_buyer_signature;
          buyers.erase(old_buyer_signature);
          demand_patterns_rev[demand_pattern] = buyer_signature;
        } else {
          buyers.erase(buyer_signature);
        }
      } else {
        demand_patterns_rev[demand_pattern] = buyer_signature;
      }
      sum += price[i];
    }
    vector< pair<int,long long> > price_and_buyers;
    tr(buyers,it) {
      long long buyer_signature = *it;
      price_and_buyers.push_back( make_pair( -prices[buyer_signature], buyer_signature ) );
    }
    sort(price_and_buyers.begin(), price_and_buyers.end());

    vector<long long> buyers_sorted(price_and_buyers.size());
    for (int i=price_and_buyers.size()-1; i>=0; i--) buyers_sorted[i] = price_and_buyers[i].second;

    return sub(buyers_sorted, all_buyers_signature, sum);
  }

だいぶ速くなったけれど、まだSystemTestで間に合わないケースがある。

• 合計額で枝切りするのやめたらどうなる？→ちょっと速くなった

          Test Case #1...PASSED (0.195 msec)
          Test Case #2...PASSED (0.112 msec)
          Test Case #3...PASSED (0.131 msec)
          Test Case #4...PASSED (0.781 msec)
          Test Case #6...PASSED (1.607 msec)
          Test Case #8...PASSED (0.24 msec)
          Test Case #11...PASSED (1.123 msec)
          Test Case #22...PASSED (7046.26 msec)
          Test Case #31...PASSED (15168.6 msec)

• とすると最初にソートしなくても良さげ→ソートやめたら速くなった

          Test Case #0...PASSED (0.95 msec)
          Test Case #1...PASSED (0.173 msec)
          Test Case #2...PASSED (0.081 msec)
          Test Case #3...PASSED (0.099 msec)
          Test Case #4...PASSED (0.496 msec)
          Test Case #6...PASSED (1.808 msec)
          Test Case #8...PASSED (0.486 msec)
          Test Case #11...PASSED (1.164 msec)
          Test Case #22...PASSED (3379.36 msec)
          Test Case #31...PASSED (2347.7 msec)

• 順番関係ないならvectorの頭じゃなくて末尾から切れば良くね？→また速くなった

最終的にこんな感じのコードになった：

#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class StampsCollection {
  map<long long,int> memo;
  map<long long, long long> demand_patterns; // demand_patterns[buyer_signature] = demand_pattern
  map<long long, long long> demand_patterns_rev; // demand_patterns_rev[demand_mask] = buyer_signature
  map<long long, int> prices;

private:
  int sub(vector<long long> buyers, long long all_buyers_signature) {
    int size = buyers.size(); // = __builtin_popcount(all_buyers)
    if (size == 0) return 0;
    if (size == 1) return prices[buyers[0]];//.front()];

    typeof(memo.begin()) m_it = memo.find( all_buyers_signature );
    if (m_it != memo.end()) return m_it->second; //memo[ all_buyers_signature ];

    long long top_buyer = buyers[size-1]; //.front();
    long long sold_out = demand_patterns[top_buyer];
    vector<long long> buyers_sub;
    long long buyers_sub_signature = 0;

    for (int i=0; i<size-1; i++) {
      long long one = buyers[i];
      if ((sold_out & demand_patterns[one]) == 0) {
        buyers_sub.push_back(one);
        buyers_sub_signature |= one;
      }
    }
    int amount = prices[top_buyer] + sub(buyers_sub, buyers_sub_signature);

    buyers.pop_back();
    buyers_sub_signature = all_buyers_signature - top_buyer;

    memo[ all_buyers_signature ] = amount = max(amount, sub(buyers, buyers_sub_signature));
    return amount;
  }

public:
  int sell(int n, vector<string> demand, vector<int> price) {
    memo.clear();
    demand_patterns.clear(); // demand_patterns[buyer_signature] = demand_pattern
    demand_patterns_rev.clear(); // demand_patterns_rev[demand_mask] = buyer_signature
    prices.clear();

    // n[1..50] stamps : [0 .. n-1],
    // demand[i] 1..50 elements, 0..n-1 [space 0..n-1]
    // price: 1..1000000
    long long n_mask = ((long long)1 << n) - 1;
  
    int buyers_cnt = demand.size();
    long long all_buyers_signature = ((long long)1 << buyers_cnt) - 1;

    set<long long> buyers;
    for (int i=0; i<buyers_cnt; i++) {
      long long buyer_signature = (long long)1 << i;
      buyers.insert(buyer_signature);

      vector<int> demand_i = map_atoi( split(demand[i]) );
      long long demand_pattern = 0;
      tr(demand_i,it) demand_pattern |= ((long long)1 << *it);
      demand_pattern &= n_mask;
      demand_patterns[buyer_signature] = demand_pattern;
      prices[buyer_signature] = price[i];
      
      if (demand_patterns_rev.find(demand_pattern) != demand_patterns_rev.end()) {
        long long old_buyer_signature = demand_patterns_rev[demand_pattern];
        if (prices[old_buyer_signature] < price[i]) {
          all_buyers_signature -= old_buyer_signature;
          buyers.erase(old_buyer_signature);
          demand_patterns_rev[demand_pattern] = buyer_signature;
        } else {
          buyers.erase(buyer_signature);
        }
      } else {
        demand_patterns_rev[demand_pattern] = buyer_signature;
      }
    }

    vector<long long> buyers_v(buyers.begin(), buyers.end());
    return sub(buyers_v, all_buyers_signature);
  }
};

これで、数秒単位で時間がかかっていた幾つかのテストケースもローカルで２秒以内に収まるようになった。（TopCoderのサーバの方がローカルより速いようなので、こちらで５秒ぐらいでも通るっぽい）

    Test Case #0...PASSED (0.839 msec)
    Test Case #1...PASSED (0.188 msec)
    Test Case #2...PASSED (0.12 msec)
    Test Case #3...PASSED (0.15 msec)
    Test Case #4...PASSED (0.391 msec)
    Test Case #6...PASSED (1.332 msec)
    Test Case #8...PASSED (0.263 msec)
    Test Case #11...PASSED (0.988 msec)
    Test Case #22...PASSED (1751.05 msec)
    Test Case #31...PASSED (1899.39 msec)

これでSystem Testは通った。□

ps.

MEDIUM (500pt)

グラフ理論．

難しい．未だにわからない．

パッと見，僕以外の日本人は結構皆解けてる…，凄いな．

(2008/09/21 03:32追記)

Mediumは http://d.hatena.ne.jp/tsubosaka/20080920 の解説が究極にわかりやすかった．

SRM418 DIV1 - ゲームにっき(仮)

　↓

　次数2以下のグラフの最大重み独立集合を求めよという問題。次数2以下のグラフは孤立点か直線か円しかなくて、孤立点は単に重みを足してやればよくて、円は適当な一ノードを使うか使わない場合に分ければ直線の場合に帰着できる。

　直線の場合の最大重み独立集合は端から見ていって現在のノードを使った場合と使わなかった場合の最大重みを計算していけばよい。

[TopCoder]SRM 418 - tsubosakaの日記

• TopCoder SRM 418 DIV1 - 総合的な学習のお時間 (tomerunさん)

SRM420 Div1 Medium: RedIsGood

過去問, 練習 | 18:14 |

昨日DIV1 500points問題を時間オーバーしながら解きつつもTest Case#5の計算が合わない辺りで中断していたところから、試行錯誤の末System Testに通るコードが書けるまでの記。

問題文はこちら。（要TopCoderアカウント）

Scheme脳の恐怖

• 気がつけば、そこまでに引いた赤と黒の差を再帰関数に渡すやり方で書いている。別に間違ってはいないのだけれど、なんとなく末尾再帰脳。（ちなみにこの例では末尾再帰になるわけではない）
• Test Case #5が通らなかったのは、eRかeBが負の場合に枝切りしていた（コメントアウト部分）ため。引いた場合の期待値が引かない場合より良ければ引く、のであればこれは不適切。

class RedIsGood {
private:
  double expected(int curr, int R, int B) {
    if (R + B == 0) return curr;   // (R≧0, B≧0 が分かっているので R = B = 0 の場合)

    double eR = -1.0, eB = -1.0, rR = 0.0, rB = 0.0, eTotal = 0.0;
    if (R > 0) {
      eR = expected(curr+1, R-1, B);
      // if (eR < 0) return curr;
      rR = 1.0 * R / (R + B);
      eTotal += eR * rR;
    }
    if (B > 0) {
      eB = expected(curr-1, R, B-1);
      // if (eB < 0) return curr;
      rB = 1.0 * B / (R + B);
      eTotal += eB * rB;
    }

    return (eTotal > curr) ? eTotal : static_cast<double>( curr );
  }
public:
  double getProfit(int R, int B) {
    return max(expected(0, R, B), 0.0);
  }
};

赤黒それぞれ最大5000枚まで

• 赤、黒それぞれ少ない枚数であればこれで十分解けるのだが、問題文では赤黒各0枚〜5000枚ということになっている。getProfit(5000,5000)は呼んだきりなかなか帰ってこない。TopCoderは制限時間２秒らしい。駄目すぎる。
• とりあえずメモ化してみますか。

その１。

class RedIsGood {
  map<pair<int,int>,double> m;

public:
  double getProfit(int R, int B) {
    if (R == 0) { return 0.0; }
    if (B == 0) { return static_cast<double>(R); }

    if (m.find( make_pair(R,B) ) != m.end()) return m[ make_pair(R,B) ];

    double eR = getProfit(R-1, B) + 1;
    double eB = getProfit(R, B-1) - 1;

    double expected = max((eR*R + eB*B)/(R + B), 0.0);
    
    m[ make_pair(R,B) ] = expected;
    return expected;
  }

• map遅いです。赤黒各5000枚では全然帰ってきません。
• mapだとO(n*log(n))だし、0〜5000までまんべんなく入ると思うのでベタな配列（またはvector）でよいような気が。

というわけでその２。

class RedIsGood {
  double m[5001*5001];

public:
  RedIsGood() {
    for (int i=0;i<=5000;i++)
      for (int j=0;j<=5000;j++)
        m[i*5001 + j] = -1;
  }
  double getProfit(int R, int B) {
    if (R == 0) { return 0.0; }
    if (B == 0) { return static_cast<double>(R); }
    if (m[R*5001+B] >= 0) return m[R*5001+B];

    double eR = getProfit(R-1, B) + 1;
    double eB = getProfit(R, B-1) - 1;
    double expected = max((eR*R + eB*B)/(R + B), 0.0);
    
    m[R*5001+B] = expected;
    return expected;
  }

• segmentation fault で動かない
• double m[5001*5001]が駄目っぽい。

その２（改）。動的確保。

class RedIsGood {
  double *m;
  int m_base;

public:
  double expected(int R, int B) {
    if (R == 0) { return 0.0; }
    if (B == 0) { return static_cast<double>(R); }
    if (m[R*m_base+B] >= 0) return m[R*m_base+B];

    double eR = expected(R-1, B) + 1;
    double eB = expected(R, B-1) - 1;
    double expected = max((eR*R + eB*B)/(R + B), 0.0);
    
    m[R*m_base+B] = expected;
    return expected;
  }
  double getProfit(int R, int B) {
    m = new double[(R+1)*(B+1)];
    m_base = B + 1;
    for (int r=0; r<=R; r++)
      for (int b=0; b<=B; b++)
        m[r*m_base + b] = -1;

    double e = expected(R, B);
    delete[] m;
    return e;
  }

• これでgetProfit(5000,5000)も２秒前後で帰ってくるようになった。
• しかし・・・これを TopCoder で Save - Compile - SystemTest してみると通らない。なんでだろう・・・

メモリは 64MB まで

要はそういうことらしい。作戦変更。

• expected(r,b) は expected(r-1,b) と expected(r,b-1) のみに依存する
• expected(r,0) = r
• expected(0,b) = 0

なので、(R+1) x (B+1) のマトリックスのうち、処理中の行と１つ上の行のみを記憶しておく作戦。これならdoubleを高々10002個持っておくだけで足りる。

その３。

class RedIsGood {
public:
  double getProfit(int R, int B) {
    if (B == 0) return static_cast<double>(R);
    if (R == 0) return 0.0;

    double *last_line = new double[B+1]; // 1つ上 (r-1) の行
    double *curr_line = new double[B+1]; // 処理中の行
    double expected = 0.0;

    for (int b=0; b<=B; b++) last_line[b] = 0;  // r=0 の行。すべて 0

    for (int r=1; r<=R; r++) {
      curr_line[0] = static_cast<double>(r); // expected(r,0) = r

      for (int b=1; b<=B; b++) {
        double eR = last_line[b]   + 1;  // eR = expected(r-1,b  ) + 1
        double eB = curr_line[b-1] - 1;  // eB = expected(r,  b-1) - 1
        curr_line[b] = max((eR*r + eB*b)/(r + b), 0.0);
      }
      if (r == R) { expected = curr_line[B]; break; }

      swap( last_line, curr_line );
    }

    delete[] last_line;
    delete[] curr_line;
    return expected;
  }

• これでようやくSystem Testも通った。
• getProfit(5000,5000)でも所要時間777ms。

一件落着。□

ps

ゲーム慣れした某氏のにっきには

MEDIUM (500pt)

典型的なDP．

2次元配列でドカンとメモリとっちゃうとMLE食らうので1次元で頑張るだけ．

SRM420 DIV1 - ゲームにっき(仮)

とのみ記されていました。

今日の試行錯誤がこんな１、２行のメモに収まる日が来ることを期待。

その他の鉄人たち：

• [TopCoder][SRM]TopCoder SRM 420 Div1 - chokudaiの日記（仮）
• TopCoder SRM 420 Div1 Medium - 西尾泰和のはてなダイアリー
• [contest]TopCoder SRM 420 DIV1 - 総合的な学習のお時間

SRM420

10.02.2008

TopCoder SRM (Single Round Match) 参加５回目。DIV1では２回目。

DIV	level	問題名	競技中	後で	System Test	備考
1	250	SolitaireSimulation	◎		passed	94.96%
1	500	RedIsGood	途中	o	passed	10/3 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081003/p1
1	1000	ChangeOMatic	-	△	x11,12,13,20	10/23 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081023/p1

250点問題: SolitaireSimulation

はやくvectorの各種操作に慣れないと時間が無駄すぎる。

500点問題: RedIsGood

解きかけ。DPで解くべく書いていたら脳内無限ループ。チャレンジタイム中も書き続けるが、Test Case #5(赤11,黒12)の数値が合わない。

1000点問題

開いてない

250点×1で144.82点。

• チャレンジタイム：耐えた
• システムテスト：OK

20人部屋で下から８番目。DIV1全体では489/632位。

今回は500点問題が解けてる人もそれなりにいた。レーティングは 1249 → 1212 に下がる。かろうじてDIV1残留。

今後の課題：

1. 基本的操作
   • vector,pair,set,map などの基本的な操作に慣れたい。
2. スピード
   • 解き方がわかってもコーディング時間は少ないのでてきぱきと。
   • 250点問題をもっと速く解けるように。
   • 500点問題も時間を区切って練習しといた方がよいかも。

来週の目標：

• 250点問題は取る
• 500点問題もsubmitまでこぎつけたい

SRM419

09.24+.2008

TopCoder SRM (Single Round Match) 参加４回目。

DIV1に上がったらやっぱり難しくなってた。

DIV	level	問題名	競技中	後で	System Test	備考
1	250	Undo	◎		passed	.. 79.47%
1	500	NimForkK	途中
1	1000	(CactusAutomorphisms)

250点問題: Undo

なんか実装に手間取った。残り40分強。

500点問題: NimForkK

解きかけ。

1000点問題

開いてない

250点×1で146.12点。

• チャレンジタイム：耐えた
• システムテスト：OK

20人部屋で下から５番目。レーティング落ちるかな？と思ったけど 1206 → 1249 に上がっていた。

DIV1全体では291/452位。