けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 091 C - 2D Plane 2N Point (ARC 092 C) (水色, 400 点)

とても教育的かつ典型的な貪欲法の問題ですね。

問題概要

二次元平面上に、赤い点と青い点が  N 個ずつあります。 i 個目の赤い点の座標は  (a_{i}, b_{i}) であり、 i 個目の青い点の座標は  (c_{i}, d_{i}) です。

赤い点と青い点は、 x 座標と  y 座標がともに赤い点よりも青い点の方が大きいとき、仲良しペアになれます。ただし,1 つの点が複数のペアに所属することはできません。

あなたは最大で何個の仲良しペアを作ることができますか?

制約

  •  1 \le N \le 100
  •  0 \le a_{i}, b_{j} \lt 2N
  •  a_{0}, \dots, a_{N-1}, c_{0}, \dots, c_{N-1} はそれぞれ互いに相異なる
  •  b_{0}, \dots, b_{N-1}, d_{0}, \dots, d_{N-1} はそれぞれ互いに相異なる

順序を定めて考える

このような問題を考察するときには、 x 座標の小さい順に考えるなど、なんらかの順序を定めて考えることが重要だと思います。

さて、ここでは、青い点たちを  x 座標が小さい順に並べてあげて、それぞれの青い点に対して順番に、どの赤い点をペアにしていくかを考えることにしましょう1。このときポイントとなるのは、 x 座標を大きくしていくたびに、青い点とマッチングされうる赤い点の選択肢が徐々に広がっていくことです。

直感的な議論

さて、基本的には「赤い点のうち、 y 座標が大きいものは売れ残りやすい」という構造になっていることに注意しましょう。 y 座標が大きい赤い点は、それよりも  y 座標が大きい青い点しか手に負えないのです。

このことを踏まえた上で、 x 座標が小さい順に青い点を見ていきましょう。結論から述べると、

  • まだ残っている赤い点のうち、
  • その青い点の左側 ( x 座標が小さい側) にあって、
  •  y 座標が最大の点

を選ぶようにしておくとよいです。その理由を考えてみましょう。とりあえず、今考えている青い点を  B として、その  y 座標を  b としておきます。

さて、その青い点  B の左側にあるまだ残っている赤い点たちの中に、 y 座標が  b よりも小さいものが複数あったとします。これらの赤い点たちの集合を  S としましょう。 S に含まれる赤い点たちのうち、将来的に最も売れ残るリスクが高いものは「 y 座標が最大である赤い点」です。よって、最も売れ残るリスクの高い哀れな赤い点を拾ってあげるのが良いということになります2

まとめると、次のように解けます。


  • 青い点たちを  x 座標が小さい順にソートして、その順に処理していく
  • 各青い点に対して、以下の条件を満たす赤い点が存在しないときはスキップして、存在するときは  y 座標が最大のものとペアにしていく
    • まだどの青い点ともペアにされずに残っている
    • その青い点よりも  x 座標も  y 座標も小さい

計算量は、「各青い点に対して条件を満たす赤い点を探索する」という単純な実装で  O(N^{2}) となります。今回の制約は  N \le 100 であるため、十分間に合います。

「交換しても悪化しない」による証明

上記の直感的な説明は、貪欲法の証明でよくある「交換しても悪化しないことを示す」という論法で示せます。

まず青い点を  x 座標が小さい順に並べたとします。そのうちの最初の点  B(b_{x}, b_{y}) ( x 座標が最小の点) について考えます。

 B よりも  x, y 座標がともに小さい赤い点が存在しないならば  B がペアを組むことはできませんし、1 個しかないならばそれと  B がペアを組んで損することは絶対にありません (その 1 個の点が他の青い点と組んだとしても、点 B に組み直して解が悪化することはありません)。

そのような赤い点が複数あったとして、そのうちの  y 座標が最大の点を  R(r_{x}, r_{y}) とします。このとき、他の赤い点  R'(r_{x}', r_{y}') と点  B とがペアを組むような解があったとしましょう。

このとき、その解を悪化させることなく、 B, R がペアになる解へと変形できることを示します。まずその解において点  R が他のどの青い点ともペアを組んでいない場合は、 B の相方を  R' から  R へと組み替えれば良いです。

 R' が他の点  B'(b_{x}', b_{y}') とペアを組んでいるとします。このとき実はペア  (B, R'), (B', R) を解消してペア  (B, R), (B', R') に組み替えることができます。なぜなら、まず

 b_{x} \gt r_{x},  b_{x}' \gt b_{x} \gt r_{x}'

が成り立っていますし、

 b_{y} \gt r_{y},  b_{y}' \gt r_{y} \gt r_{y}' ( r_{y} の最大性より)

が成り立つからです。

以上から、点  B に対して  y 座標が最大な点  R をペアにするような最適解が存在することが言えました。よって二次元平面上から 2 点  B, R を除去してよく、残った点に対して同様の手続きを進めていくことができます。

コード

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

// 二次元座標を定義
using Point = pair<int,int>;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<Point> red(N), blue(N);
    for (int i = 0; i < N; ++i) cin >> red[i].first >> red[i].second;
    for (int i = 0; i < N; ++i) cin >> blue[i].first >> blue[i].second;

    // 青い点を x 座標が小さい順にソートする (デフォルトで第一引数の辞書順比較)
    sort(blue.begin(), blue.end());

    // 各赤い点が使用済みかどうか
    vector<bool> used(N, false);

    // 青い点を順番に見ていく
    int res = 0;
    for (int i = 0; i < N; ++i) {
        // 使用済みでなく、y 座標最大の赤い点を探す
        int maxy = -1, maxid = -1;
        for (int j = 0; j < N; ++j) {
            // 使用済みの赤い点は不可
            if (used[j]) continue;

            // x 座標, y 座標がより大きい赤い点は不可
            if (red[j].first >= blue[i].first) continue;
            if (red[j].second >= blue[i].second) continue;

            // 最大値を更新
            if (maxy < red[j].second) {
                maxy = red[j].second;
                maxid = j;
            }
        }

        // 存在しない場合はスキップ
        if (maxid == -1) continue;

        // ペアリングする
        ++res;
        used[maxid] = true;
    }
    cout << res << endl;
}   

  1. なおこのとき、逆に赤い点たちを  x 座標が小さい順に並べてあげて、それぞれの赤い点に対して順番に、どの青い点をペアにしていくかを考えたくなる人も多いでしょう。しかしこの方針だとおそらく上手く解けないです。

  2. ここで、 x 座標については実は考慮する必要がないことに注意しましょう。なぜなら、今後登場してくる青い点たちは、すべて点  B よりも x 座標が大きいからです。よって、集合  S に含まれる赤い点たちは、 x 座標のことが理由で今後売れ残る心配はありません。 y 座標のことだけを考えれば良いです。

AtCoder ABC 026 D - 高橋君ボール1号 (水色)

方程式を解くタイプの二分探索の問題ですね。

問題概要

正の整数  A, B, C が与えられます。 t 秒後のボールの位置  f(t)

 f(t) = At + B \sin(C \pi t)

で表されます。 f(t) = 100 を満たす実数  t の値を十分高い精度で求めてください。

 |f(t) - 100| \le 10^{-6} を満たせば正解とみなされます。

制約

  •  1 \le A, B, C \le 100

解へのアプローチ

 f(t) = 100 の解を数学的に直接求めることはいかにも難しそうです。このようなとき、二分探索法が有効となることがあります。まず、

  •  f(\alpha) \lt 100
  •  f(\beta) \gt 100

を満たすような  \alpha, \beta ( \alpha \lt \beta) があったならば、

  •  \alpha \lt x \lt \alpha
  •  f(x) = 100

を満たすような実数  x が存在することに注意しましょう (中間値の定理)。つまり、区間  (\alpha, \beta) の中に「 f(x) \lt 100 から  f(x) \gt 100 に変わる瞬間」があるということです。そしてそのような  x をまさに二分探索法で求めることができます。

二分探索法へ

前述のように、区間  (\alpha, \beta) の中に「 f(x) \lt 100 から  f(x) \gt 100 に変わる瞬間」があることがわかったとき、この範囲を狭めていくことができます。

具体的には  \gamma = (\alpha + \beta) / 2 としたときに、

  •  f(\gamma) \le 100 ならば、範囲を区間  (\gamma, \beta) に絞る
  •  f(\gamma) \ge 100 ならば、範囲を区間  (\alpha, \gamma) に絞る

という風にできます。どちらの場合であっても、区間の幅が  1/2 になります。二分探索法をたとえば  100 回などやれば、区間の幅は  2^{-100} 倍になります。

初期値  \alpha, \beta を求める

最後に、二分探索法の初期値を決めましょう。つまり

  •  f(\alpha) \lt 100
  •  f(\beta) \gt 100

を満たすような  \alpha, \beta を具体的に決めましょう。 \alpha の方は簡単です。

 f(0) = 0

ですので、たとえば  \alpha = 0 とすればよいでしょう。

次に  \beta の方です。まず  t が大きくなればなるほど  At は大きくなることに注意しましょう。したがって、十分大きな  \beta に対しては  f(\beta) \gt 100 となることが推測されます。

ここで、 \sin t の値の範囲は  -1 \le \sin t \le 1 の範囲に限られることに注意しましょう。よって、 t = 200 などとすれば

 f(200) = 200A + B \sin(C \pi t) \ge 200 - 100 \ge 100 ( A \ge 1,  B \le 100 より)

となります。よって  \beta の値を  200 以上の値にすればよいでしょう。

コード

以上の考察は、次のように実装できます。なお、円周率  \pi は、acos(-1.0) の値を用いるのが有効です。

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

// 円周率 PI
const double PI = acos(-1.0);

int main() {
    // 入力
    int A, B, C;
    cin >> A >> B >> C;

    // 関数 f
    auto func = [&](double t) -> double {
        return A * t + B * sin(C * PI * t);
    };

    // 二分探索
    double alpha = 0, beta = 200;
    for (int iter = 0; iter < 100; ++iter) {
        double gamma = (alpha + beta) / 2;
        if (func(gamma) <= 100) alpha = gamma;
        else beta = gamma;
    }

    // 小数点第 15 位まで出力 (ヘッダ <iomanip> が必要)
    cout << fixed << setprecision(15) << alpha << endl;
}

AtCoder ARC 037 C - 億マス計算 (青色)

二分探索法の教育的典型問題ですね!!

問題概要

正の整数からなる長さ  N の数列が 2 つ ( a_{0}, a_{1}, \dots, a_{N-1} b_{0}, b_{1}, \dots, b_{N-1}) 与えられます。

 (i, j) に対して  a_{i} \times b_{j} を計算することで得られる  N^{2} 個の整数を考えます。

これらの整数を小さい順に並べたとき、 K 番目 (1-indexed) に来る値を求めなさい。

制約

  •  1 \le N \le 30000
  •  1 \le K \le N^{2}
  •  1 \le a_{i}, b_{j} \le 10^{9}

二分探索法へ帰着

単純に  N^{2} 個の値を計算して、それらを小さい順にソートする方法が最初に考えられるかもしれません。しかしこれでは  O(N^{2} \log N) の計算量を必要としてしまいます。

ここで「 K 番目に小さい値を求めなさい」という問題に対しては二分探索法が有効になることがある、ということを思い出してみましょう。求めたい値は、次の判定問題の答えが "Yes" となる最小の値  x に他ならないのです。


 N^{2} 個の整数のうち、 x 以下の値が  K 個以上あるかどうかを判定せよ


それではこの判定問題を解く方法を考えてみましょう。

判定問題

 (i, j) という 2 つの添字について考える問題では、どちらか 1 つの添字を固定して考えることが有効です。ここでは、 a_{i} を固定して考えてみましょう。

つまり、各  i = 0, 1, \dots, N-1 に対して、 a_{i} \times b_{j} の値が  x 以下となる  b_{j} の個数を数えていくことにします (それらの総和をとればよいです)。これは次の問題と等価です。


 b_{0}, b_{1}, \dots, b_{N-1} のうち、 \frac{x}{a_{i}} 以下であるものは何個あるか


この問題を解くためには、ふたたび二分探索 (lower_bound) が活用できます。具体的には、数列  b をあらかじめソートしておくことを前提として

upper_bound(b.begin(), b.end(), x / a[i]) - b.begin()

によって求められます。

コード

以上の解法は、次のように実装できます。

最後に計算量を見積もります。まず判定問題を解くのに要する計算量は  O(N \log N) となります。そして判定回数は、 C = \max_{i, j} a_{i} b_{j} として、 O(\log C) と評価できます。よって全体の計算量は  O(N \log N \log C) と評価できます。

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

int main() {
    long long N, K;
    cin >> N >> K;
    vector<long long> a(N), b(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) cin >> b[i];

    // b はあらかじめソートしておく
    sort(b.begin(), b.end());

    // 判定問題
    auto check = [&](long long x) -> bool {
        long long cnt = 0;
        for (int i = 0; i < N; ++i) {
            cnt += upper_bound(b.begin(), b.end(), x / a[i]) - b.begin();
        }
        return (cnt >= K);
    };

    // 二分探索 (right は十分大きな値に設定)
    long long left = 0, right = 1LL<<60;
    while (right - left > 1) {
        long long mid = (left + right) / 2;
        if (check(mid)) right = mid;
        else left = mid;
    }
    cout << right << endl;
}

AtCoder ABC 206 C - Swappable (灰色, 300 点)

包除原理の一番簡単な場合を試せる問題

問題概要

 N 個の整数  A_{1}, \dots, A_{N} が与えられる。以下の条件を満たす整数  (i, j) の組の個数を求めよ。

  •  1 \le i \lt j \le N
  •  A_{i} \neq A_{j}

制約

  •  2 \le N \le 3 \times 10^{5}
  •  1 \le A_{i} \le 10^{9}

考えたこと

まず、 A_{i} \neq A_{j} という条件がないバージョンを考えてみよう。そのときは単に  N 個のものから 2 個選ぶ場合の数を求めよ、という問題になる。

 {}_{N}{\rm C}_{2} = \frac{N(N-1)}{2} 通り

となる。これは AtCoder では定期的によく出されている。

drken1215.hatenablog.com

補集合を考える

さていよいよ、 A_{i} \neq A_{j} という条件を考えていこう。しかしこの条件を考えるのは難しいので、かわりに「逆」の方を数えることにしよう。つまり、逆に

  •  1 \le i \lt j \le N
  •  A_{i} = A_{j}

であるような場合の数を数えることにしよう。その答えを  P としたとき、 \frac{N(N-1)}{2} - P を出力すれば OK。

 A_{i} の値ごとに分類

さて、逆の方は数えやすい。たとえば  A = (1, 1, 2, 3, 3, 1, 1) だと

  • 1 が 4 個
  • 2 が 1 個
  • 3 が 2 個

となる。 A_{i} = A_{j} = 1 となるパターンは「4 個から 2 個を選ぶ場合の数」なので  {}_{4}{\rm C}_{2} = 6 通りで、 A_{i} = A_{j} = 2 となるパターンは  {}_{1}{\rm C}_{2} = 0 通りで、 A_{i} = A_{j} = 3 となるパターンは  {}_{2}{\rm C}_{2} = 1 通りとなる。これらを合計して  6 + 0 + 1 = 7 通りとなる。

一般に、 A_{i} の値を数値ごとに分類して、その個数を  a として  {}_{a}{\rm C}_{2} の総和を取っていけば OK。

コード

計算量は  A の値を分類するときに map などを用いた場合、 O(N \log N) となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    map<long long, long long> ma;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        ma[A[i]]++;
    }

    long long P = 0;
    for (auto it: ma) {
        long long num = it.second;
        P += num * (num - 1) / 2;
    }
    cout << N * (N - 1) / 2 - P << endl;
}

AtCoder ABC 206 D - KAIBUNsyo (緑色, 400 点)

今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。

問題概要

正の整数からなる整数列  A_{1}, \dots, A_{N} が与えられる。以下の操作を好きなだけ行うことによって、 N 個の値がすべて等しくなるようにしたい。

  1. 2 つの整数値  x, y を選ぶ
  2. 整数列中の値  x をすべて  y に書き換える

目的を達成できる操作回数として考えられる最小値を求めよ。

制約

  •  1 \le N, A_{i} \le 2 \times 10^{5}

考えたこと

この問題の真のポイントは、Union-Find ガチャを回すことでも、グラフの問題だと気づくでもなく、自然な数学的考察を積み上げることなのかなと思う。

まずは具体的な様子を見てみよう。 N = 11 A = (6, 3, 1, 2, 7, 5, 3, 7, 1, 2, 4) としてみます。このとき、下図の「線」を引かれた両端は揃っている必要があります。

f:id:drken1215:20210626153256p:plain

まず、真ん中の数値については何も考えなくてよいです ( N が奇数の場合)。たとえ真ん中の数値がどこかの操作で変わったとしても、また他の数値がどのように変化したとしても、まったく気にする必要はないです。よって、真ん中の数値は無視しましょう。また同様に、「両端の数値が等しくなっている線の両端」についても、まったく気にする必要はないです。以上のことを加味すると、次のようになります。

f:id:drken1215:20210626153921p:plain

さて、まず両端の 6 と 4 をくっつける必要がある。ここで 6 を 4 にしても、4 を 6 にしても、結局のところ変わらない。いずれにしても 6 と 4 をくっつける感じになる。この操作が Union-Find の merge っぽいな......という連想が働く。

ここで注意したいのは「両端を見て値が異なっている箇所を数える」というのは嘘解法ということだ。たとえば、上図の場合

  • 6 と 4
  • 3 と 2
  • 2 と 7

までをマージした時点で、7 と 3 はマージされている (3 と 2、2 と 7 がそれぞれマージされているので 7 と 3 はマージされている)。よって上図の場合の答えは 4 回ではなく、3 回なのだ。

なんとなくだけど、Union-Find でひたすら merge していって、すでに merge されていたら merge はやめておいて、結局 merge した回数を答えればよいのでは...という想像が働く。結局それで正しくなる。

merge 回数より少ない回数でできない理由

ここで大事なことは、Union-Find の merge 回数よりも少ない回数ではダメだということをきちんと数学的に納得することだと思う。この納得感が得られるかどうかで、今後 AtCoder のより高度な問題を解く時に数学的直観が正しく働くかどうかが分かれる気がするのだ。

とりあえず、ここまで考えてきた具体例について、結びつくべき数値の関係性を図示すると、下図のようになる。

f:id:drken1215:20210626163854p:plain

こうすると分かりやすい。一般に  K 個のノードをすべて連結にするには  K-1 本の辺が必要 (そして十分) なのだ ( K 頂点の木の辺の本数は  K-1 本)。

ここまで来たら次の解法でよいことが確定する。

  •  A_{i} A_{N-i-1} の組を順番に見ていく
  • それらの値が異なっていて、かつ、Union-Find 上で同じグループでない場合には merge する

merge した回数が答えになる。

コード

計算量は  N \alpha(N) になる。

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

const int MAX = 210000;
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    UnionFind uf(MAX);
    for (int i = 0, j = N-1; i < j; ++i, --j) {
        uf.merge(A[i], A[j]);
    }
    long long res = 0;
    for (int v = 0; v < MAX; ++v) {
        if (uf.root(v) == v) {
            res += uf.size(v) - 1;
        }
    }
    cout << res << endl;
}