貪欲法…線分（3題）

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本の章末で紹介されている練習問題をひたすら解いている。解説だけでなくテーマに沿った類題も豊富に紹介してくれているのがこの本の良いところだよね。でも正直、第１章でもかなり難しく感じる。第２章まで読んで練習して消化できる人って、かなりの上級者な気がするんだが…世界は広い。

貪欲法。たくさんの要素から「次の一つ」を選ぶために単純なルールを作って、ルールに従って「貪欲に」次々と要素を選ぶ。ここで練習した３題は線分の被覆問題とか。

POJ2376: Cleaning Shifts

2376 -- Cleaning Shifts
長さTの線分をN本の線分で被覆する問題。
被覆するのに必要な線分の最小の本数を求める。

問題の概略

ジョンはN(1 <= N <= 25000)頭の牛のうち何頭かを使って、小屋の周りを掃除させることにした。
つねに1頭は掃除の仕事をしているようにしたいと思い、1日をT(1 <= T <= 1000000)個のシフトに分けた。
それぞれの牛は1日のうちある決まった期間にしか使えない。掃除の仕事のために選ばれた牛は、その開始時間から終了時間にわたって働き続ける。
ジョンが牛にシフトを割り当てるのを手伝ってほしい。
(1)それぞれのシフトは少なくとも1頭の牛が割り当てられている。
(2)掃除をする牛はできるだけ少ないようにしたい。
それぞれのシフトに牛を割り当てるのが不可能なら-1を出力せよ。

解法

貪欲法。牛の選び方は次の通り
(1) 最初の1頭は時間1から始まり終了時間が最も遅いものを選ぶ。
(2) i+1頭目の牛は、開始時間がi頭目の牛の終了時間以下の牛のうち、終了時間が最も遅い牛を選ぶ。
(3) 選んだ牛の終了時間がTと等しくなったら終了する。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
  // 入力
  int n, t;
  scanf("%d%d", &n, &t);
  // 各牛の開始時間と終了時間
  vector< pair<int, int> > cows(n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &cows[i].first, &cows[i].second);
  }

  // 牛の開始時間が小さい順、終了時間が小さい順にソート
  sort(cows.begin(), cows.end());

  // 計算
  int i = 0;
  int cur_end_time;
  int cnt = 1;
  // 最初の1頭は開始時間が1から始まり終了時間が最も遅いものを選ぶ
  while (cows[i].first == 1 && i < n) {
    i++;
  }
  if (i == 0) {
    cout << -1 << endl;
    return 0;
  }
  cur_end_time = cows[i - 1].second;
  // i+1頭目の牛は開始時間がi頭目の牛の終了時間+1以下の牛のうち、終了時間が最も遅い牛を選ぶ。
  while (cur_end_time < t && i < n) {

    int next_end_time = cur_end_time;

    while (cows[i].first <= cur_end_time + 1 && i < n) {
      if (next_end_time < cows[i].second)
        next_end_time = cows[i].second;
      i++;
    }

    // next_end_timeが更新されていなければ、被覆は不可能
    if (cur_end_time == next_end_time) {
      cout<< -1 << endl;
      return 0;
    }
    cur_end_time = next_end_time;
    cnt++;
  }

  // 出力
  cout << ((cur_end_time == t) ? cnt : -1) << endl;
}

POJ1328: Rader Installation

1328 -- Radar Installation
見た目は平面上にある点を円で被覆する問題だが、x軸に投影すると線分被覆問題になる。

問題の概略

xy平面のy>0の領域にn(1 <= n <= 1000)個の島がある。
島の座標が与えられている。
中心がx軸上にある半径dの円をいくつか置いて島を被覆するには、
最小で何個の円を置けばよいかを求めよ。
円は中心がx軸上にあればどこにおいてもよい。
円で島を被覆できないときには-1を出力せよ。

解法

解法
貪欲法。島をx座標が小さい順にソートする。
左の島から被覆する。次のルールに従う。
まだ被覆されていない島のうちいちばん左の島をiとする。
島iから始めて順に島i+1, 島i+2...と連続した番号の島をまとめて被覆できる最大の円を取ようにする。
島iを被覆できる円の中心が存在できるx軸上の範囲は線分となる。この線分を使って解く。

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
using namespace std;

int main() {
  int c = 0;
  while (1) {
    // 入力
    c++;
    int n, d;
    cin >> n >> d;
    if (!(n | d)) break;
    int x, y;
    double dx;
    bool fail = false;
    vector< pair<double , double> >  lines(n);
    for (int i = 0; i < n; i++) {
      cin >> x >> y;
      if (y > d) {
        fail = true;
      } else {
        dx = sqrt((double)(d*d - y*y));
        lines[i] = make_pair(x - dx, x + dx);
      }
    }
    // 被覆できない島があるなら
    if (fail) {
      cout << "Case " << c << ": -1" << endl;
      continue;
    }
    // 線分の左端が小さい順、右端が小さい順にソート
    sort(lines.begin(), lines.end());
    // 計算
    double left = lines[0].first;
    double right = lines[0].second;
    int i = 0;
    int cnt = 1;
    // 線分がなくなるまでループ
    while (++i < n) {
      // 連続して被覆できなくなったら
      if (right < lines[i].first) {
        cnt++;
        left = lines[i].first;
        right = lines[i].second;
        continue;
      }
      // 左端と右端を更新
      left = max(left, lines[i].first);
      right = min(right, lines[i].second);
    }

    // 出力
    cout << "Case " << c << ": " <<cnt << endl;
  }
}

POJ3190: Stall Reservations

3190 -- Stall Reservations
N個の線分を重ならないように並べるには直線が何本必要かという問題。貪欲法だが次を選ぶルールを考えるのに手間取った。

問題の概略

A..B(1 <= A <= B <= 1000000)の時間帯にしかミルクを出さない牛がN頭(1 <= N <= 50000)いる。ひとつの搾乳ブースには一頭の牛しか一度に使えない。
・それぞれの牛がプライベートなミルク時間を持てるような搾乳ブースの最小数を求めたい。
・牛はミルク時間のあいだずっと搾乳ブースを占領する。

解法

貪欲法。牛の選び方は、次の通り。
残っている牛の中で開始時間が最も早いものを選ぶ。
すでにあるブースの中で終了時間が最も早いものにその牛が入れば入れる。
その牛が入らなければ新しいブースを作る。

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;

struct Cow {
  int id, ts, te, stl;
  // ふつうの比較<は終了時間teにより比較（逆）
  bool operator<(const Cow& another) const {
    return another.te < te;
  }
};
// 開始時間tsにより比較
bool comp1(Cow one, Cow another) {
  return one.ts < another.ts;
}
// idにより比較
bool comp2(Cow one, Cow another) {
  return one.id < another.id;
}

int main() {
  // 入力
  int n, i, j;
  cin >> n;
  // cowsには各牛の搾乳の開始時間と終了時間を格納する
  vector< Cow > cows(n);
  for (i = 0; i < n; i++) {
    cows[i].id = i;
    cin >> cows[i].ts >> cows[i].te;
  }
  // 開始時間の早い順にソート
  sort(cows.begin(), cows.end(), comp1);
  // stallsには牛が終了時間の早い順に入る
  priority_queue<Cow> stalls;
  // 計算
  i = 0;
  j = 1;
  int tmp;
  cows[0].stl = j++;
  stalls.push(cows[0]);
  while (++i < n) {
    // すでに区画への配置が決まっている牛の中で終了時間が最も早いもの
    Cow c = stalls.top();
    // 残った牛のうち開始時間が最も早い牛が、牛cのいる区画に入れるなら
    if (cows[i].ts > c.te) {
      cows[i].stl = c.stl;
      stalls.pop();
      stalls.push(cows[i]);
    // 入れないなら新たに区画を作る
    } else {
      cows[i].stl = j++;
      stalls.push(cows[i]);
    }
  }

  // 出力
  cout << stalls.size() << endl;
  sort(cows.begin(), cows.end(), comp2);
  for(i = 0; i < n; i++)
    cout << cows[i].stl << endl;
}

感想

貪欲法は、「次を選ぶルール」をシンプルに決められれば強力なアルゴリズムなんだけど、このルールで選んでいけば正しい解答に至れるということをきちんと数学的に証明するのはわりと難しい。だからいくつかのテストケースで試してみて、これならうまくいくかなぁーと思ったら実装してみる。でも結局間違っていたり。正しいルールの見つけ方がまだよく分からない。経験か？