【AtCoder】競プロ典型90問 001 - Yokan Party（★4）

001 - Yokan Party（★4）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1199 / NoviSteps: 2Q / 配点: 4 点

問題概要

左右の長さが $L \, \mathrm{[cm]}$ のようかんがある。 ようかんには $N$ 個の切れ目が付けられており、左から $i$ 番目の切れ目は左から $A_i \, \mathrm{[cm]}$ の位置に付けられている。

これから $N$ 個の切れ目のうち $K$ 個を選び、ようかんを $K+1$ 個のピースに分割したい。 ここで、以下の値をスコアとするとき、スコアが最大となるようにようかんを分割する場合に得られるスコアを求めよ。

• $K+1$ 個のピースのうち、最も短いものの長さ( $\mathrm{[cm]}$ 単位)

制約

• $1 \leq K \leq N \leq 100000$
• $0 \lt A_1 \lt A_2 \lt \cdots \lt A_N \lt L \leq 10^9$
• 入力はすべて整数

考察

「ピースの最小値の最大化」ということで、これは答えで決め打つ二分探索の典型問題であり、いわゆるめぐる式二分探索で解くことができる。

判定問題について

このタイプの問題では、まず以下のような Yes / No 判定問題を考える。

• $K+1$ 個のピースすべてを長さ $x$ 以上にできるか？

これは、「左端から順に切れ目を見ていって、前回の切断箇所からの長さが初めて $x$ 以上になる箇所で切断していく」という貪欲なやり方で解くことができる。

最終的に $K+1$ 個以上のピースが得られれば Yes、そうでなければ No である。

めぐる式二分探索

今回は、この問題が Yes となるような最大の $x$ を求めたいので、使うべきなのは最終的なokの値である。

また、初期値は $\mathrm{ok} = -1, \, \mathrm{ng} = L+1$ とすればよいだろう。

計算量についてだが、判定問題は $O(N)$ で解け、二分探索は $O(\log L)$ で処理できるので、全体では $O(N \log L)$ となる。

実装例

判定問題の関数はラムダ式で書いてあげると実装が楽。

なお、 $K+1$ 個目のピースが長さ $x$ 以上になるかどうかの判定も忘れないこと。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.using ll = long long;
7. 
8.// ======================================== //
9. 
10.int main()
11.{
12.    int N, L, K;
13.    cin >> N >> L >> K;
14.    vector<int> A(N);
15.    rep(i, 0, N) cin >> A[i];
16. 
17.    auto is_ok = [&](ll x) -> bool
18.    {
19.        ll cnt = 0;
20.        ll last = 0;
21.        rep(i, 0, N)
22.        {
23.            if (A[i] - last >= x)
24.            {
25.                cnt++;
26.                last = A[i];
27.            }
28.        }
29. 
30.        if (L - last >= x)
31.            cnt++;
32. 
33.        return (cnt >= K + 1);
34.    };
35. 
36.    ll ok = -1, ng = L + 1;
37.    while (ng - ok > 1)
38.    {
39.        ll mid = midpoint(ok, ng);
40.        if (is_ok(mid))
41.            ok = mid;
42.        else
43.            ng = mid;
44.    }
45. 
46.    cout << ok << endl;
47. 
48.    return 0;
49.}

https://atcoder.jp/contests/typical90/submissions/70374316

atcoder.jp

実装時間: 15 分

コメント

競プロでよく見る「最大(最小)値の最小(最大)化」問題である。

めぐる式二分探索の実装も合わせて覚えておきたい。