ABC103-D:Islands War(400)

問題

https://beta.atcoder.jp/contests/abc103/tasks/abc103_d

N 頂点と N-1 本の橋がある。 N-1 本の橋は i と i+1 を結ぶ。与えられる M つの要望を満たすようにするためには、最小でいくつの橋を除けばいいか。

制約

  • 1 <= N <= 105
  • 1 <= M <= 105
  • 1 <= a_i, b_i < N
  • (a_i, b_i) はすべて異なる

考え方

グラフの問題のように見えるが、橋がすべて i と i+1 を結んでいるので、数直線で考えてよい。すると M つの要望は区間が与えられていることがわかる。

サンプル2 を例に考えていこう。M 個の区間が与えられて、オレンジの縦線で各区間を切断するとき、最小の縦線は何本であるかということである。

f:id:d_tutuz:20180722082444p:plain

区間 [a_i, b_i), [a_j, b_j) (i < j)の2つの区間を同時に切断したいとする時、最適な解は切断方法は b_i の直前の区間を含むように切断するのが最適である。仮に a_j < b_i であれば同時に切断できるためである。もともと a_j >= b_i である時はどのようにしても同時に切断することはできない。

よって、すべての区間を b で昇順にソートして、各 a_j が b_i 未満であるかチェックすればいい。 b_i 未満であれば同時に切断でき、できないときは新たに b_j の直前の区間で切断する。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), m = in.nextInt();
            P[] ps = new P[m];
            for (int i = 0; i < m; i++) {
                int a = in.nextInt(), b = in.nextInt();
                ps[i] = new P(a, b);
            }

            Arrays.sort(ps);

            int s = 0, count = 0;;
            for (int i = 0; i < m; i++) {
                if (s < ps[i].b) {
                    s = ps[i].b;
                    count++;
                }
            }

            out.println(count);

        }

      class P implements Comparable<P> {
            int a, b;

            public P(int a, int b) {
                super();
                this.a = a;
                this.b = b;
            }

            @Override
            public int compareTo(P o) {
                if (this.b == o.b) {
                    return this.a - o.a;
                } else {
                    return this.b - o.b;
                }
            }
        }

ポイント

  • 隣り合う点しかないグラフは区間で考える。木で考えない。
  • 区間の被覆は終端でソートして考えてみる。
  • 見た目にダマされない。
    • 「橋」とか「島」とかの単語でグラフ問題っぽく見せているけど、実は数直線上の区間を考えれば良い。
    • 問題の構造は基本の典型と同じだけど、問題文の見せ方を変えることで難易度を上げるテクニックはありそう。