読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Facebook HackerCup Round2 : 問題B. Monopoly

なんかこれなら解けそうな気がして問題Aを飛ばして取り組んでみたものの、計算が全然合わずに終わってしまった問題Bです

本番中に焦ってる時ってunion-find的なものを自分で無駄に実装してたりとか、ちゃんと考えをまとめないままコード書こうとしてたりとか、イテレーションが長すぎたりとか。イテレーションが長くて困るのは一度に取り組むべきC++のエラーメッセージ量が増える事。clang++だと非人道度は下がるもののやっぱりSTLだのテンプレートだのが絡むエラーは面倒臭い。

Round3に進んだ人は(ペナルティポイントから推測すると)問題A, Bをそれぞれ1時間以内でさくさく解いてたと思われるのだけれど、焦っても一朝一夕に追いつけるものでもないので、まずは気を取り直して改めて解いてみようかと。

問題文はこちら

まず会社をどう表現するか。コンテスト中はpairで行けそうな気がしているのに計算あわなくて泣きそう、だったので、practiceだし遠回りだけど冗長なクラスを書いてそこから削ってみようと。どのくらい冗長かって

class Company {
 public:
  Company() {
    persons_.assign(1, make_pair(0, 0));
    person_count_ = 1;
    height_ = 1;
  }
  Company(const Company& com) {
    persons_.assign(all(com.persons_));
    person_count_ = com.persons_.size();
    height_ = com.height_;
  }
  Company& operator=(const Company& com) {
    persons_.assign(all(com.persons_));
    person_count_ = com.persons_.size();
    height_ = com.height_;
    return *this;
  }

  int height() const { return height_; }

  bool is_full() const { return persons_[0].used_capacity == g_maxCapacity; }

  bool operator<(const Company& other) const {
    if (height_ == other.height_)
      return persons_ < other.persons_;
    else
      return height_ < other.height_;
  }
  bool operator==(const Company& other) const {
    return persons_ == other.persons_;
  }

  bool merge(const Company& other) {
    if (persons_[0].used_capacity == g_maxCapacity) return false;

    height_ = max(height_, 1 + persons_[0].depth + other.height_);
    tr(other.persons_, jt) {
      persons_.push_back(
          make_pair(1 + persons_[0].depth + jt->depth, jt->used_capacity));
    }
    persons_[0].used_capacity++;
    sort(all(persons_));
    return true;
  }

  string description() const {
    stringstream ss;
    tr(persons_, it) {
      ss << "(" << it->depth << " " << it->used_capacity << "), ";
    }
    ss << "height=" << height_;
    return ss.str();
  }

  vector<i_i> persons_; // (depth, used_capacity)
  int height_, person_count_;
};

このくらい。

まあこれでも全組み合わせを試しながらDPというかオンライン処理というか出来るっちゃ出来るんだけれど… サンプルケースは小さいから良いけどD=5000とか来たら死ぬし。

  • rootにしかぶら下げないわけだし、ツリー構造を全て保持しておく必要はないよね
  • persons_[] とか person_count_ とかイラネ。高さと、あとrootノードにぶら下がってる枝の数は必要。
  • てことは pair で十分
  • スタート地点は pair(高さ:1, rootにぶら下がる枝:0) × N社分
  • 合併を1件ずつ処理して進んで行きたい。
  • どのツリーとどのツリーの合併なのか union-find しておかないと分からないのでしておく
  • AとBの合併は {Aの可能なツリー集合} と {Bの可能なツリー集合} からそれぞれ1つずつツリーを取り出して
    1. AのrootにBをぶら下げられるならぶら下げる
    2. BのrootにAをぶら下げられるならぶら下げる

してみたツリーの集合の計算。

  • 合併したツリーの表現は、pair(高さ:max(親の高さ, 1+子の高さ), rootにぶら下がる枝:親のrootにぶら下がる枝+1)

実データダウンロードしてみて走らせたら全然終わんないし><

  • あ。全部保持する必要はない
  • ツリー集合のなかで最低限保持すべきツリーとは?
  • 高さ毎にまとめてみて、rootにぶら下げる余地が一番大きいやつだけ残しておいたらよいのでは。同じ高さならそれ以外が使われることはあり得ないし。
  • rootにぶら下げる余地がない(もう片方の会社に吸収される他に生き残る道がない)ツリーは一番低いやつだけ1個持ってれば十分かと

削りに削ってようやく実データをローカル2秒で処理できるようになったのでsubmitしてみた。AC。

最終的な実装はこんな感じ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>

using namespace std;

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

typedef pair<int, int> i_i;

class UnionFind {
  vector<int> data;
 public:
  explicit UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
  bool has(int x) { return data[x] >= 0; }
};

#define height first
#define used_capacity second

int g_maxCapacity;

int main() {
  int T;
  cin >> T;  // 5-20
  for (int t = 1; t <= T; ++t) {
    int Nc, D;
    cin >> Nc >> D;  // 2-30000, 1-5000
    g_maxCapacity = D;
    int Nm = Nc - 1;

    UnionFind uf(Nc);

    vector<set<i_i> > companies(Nc);
    for (int i = 0; i < Nc; ++i) {
      companies[i].insert(make_pair(1, 0));
    }

    for (int i = 0; i < Nm; ++i) {
      int a, b;
      cin >> a >> b;
      --a;
      --b;

      int a_root = uf.root(a), b_root = uf.root(b);

      uf.unionSet(a, b);
      int new_root = uf.root(a);

      set<i_i> merged;
      vector<int> ucmin(Nc+1, INT_MAX);
      tr(companies[a_root], at) {
        tr(companies[b_root], bt) {
          if (at->used_capacity < g_maxCapacity) {
            int ht = max(at->height, 1 + bt->height);
            int uc = at->used_capacity + 1;
            if (uc < ucmin[ht]) ucmin[ht] = uc;
          }
          if (bt->used_capacity < g_maxCapacity) {
            int ht = max(bt->height, 1 + at->height);
            int uc = bt->used_capacity + 1;
            if (uc < ucmin[ht]) ucmin[ht] = uc;
          }
        }
      }
      companies[a_root].clear();
      companies[b_root].clear();
      companies[new_root].clear();
      bool filled = false;
      int mincap = INT_MAX;
      for (int ht = 1; ht <= Nc; ht++) {
        if (ucmin[ht] == INT_MAX) {
          continue;
        } else if (ucmin[ht] == g_maxCapacity) {
          if (!filled) {
            companies[new_root].insert(make_pair(ht, g_maxCapacity));
            filled = true;
          }
        } else {
          if (ucmin[ht] < mincap) {
            companies[new_root].insert(make_pair(ht, ucmin[ht]));
            mincap = ucmin[ht];
          }
        }
      }
    }

    int ans = INT_MAX;
    tr(companies[uf.root(0)], it) {
      int h = it->height;
      if (h < ans) ans = h;
    }
    printf("Case #%d: %d\n", t, ans);
  }

  return 0;
}