2008-10-04

SRM418 Div1 Medium: StampsCollection

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

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さん)

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081004

		2008/10
日	月	火	水	木	金	土
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

naoya_t@topcoder

2008-10-04

SRM418 Div1 Medium: StampsCollection

ps.