【競プロ】競プロ典型90問 - 001 - Yokan Party

競技プログラミング
Page content

まえがき

今回は競プロ典型90問の「001 - Yokan Party」の解法の備忘のために記事を書いています。
かなり遅いですが最近競プロ典型90問を始め、1問目から解説を見ないと解けませんでした。
自身の備忘のためにも、今後解説を見ないと解けなかった問題、解説から知見を得た問題については記事にすることにしました。

問題については上記のリンクを見ていただき、本記事では公式の解説の説明と、自身が提出したコードを載せていきます。

解法の解説

競プロ典型90問の公式解説では、要約となるようなキーワードが付けられています。
今回のキーワードは「答えで二分探索」でした。

今回やりたいのは最短長をスコアとした場合のスコア最大化ですが、解法では以下の2工程に分けて解を導いています。

  1. スコアがx以上になる切り方が存在するか判定するロジックを実装
  2. 1を使用してスコアの最大値を二分探索

最小値最大化の問題では同じ解き方ができるらしく、ABC023-D-射撃王などが解けるそうです。

反省

解法を見る前は、${}_N C_K$の組み合わせから解となる組を探索しようとしていました。
探索不要なパターンの洗い出しや、動的計画法での解法を検討し、良い方法を思いつかず諦めたという感じです。

公式の解法は初見の考え方かつ思いつきそうもないため、時間を掛けても解けないパターンの問題でした。
今回を活かして今後の類似問題では対応していきたいです。

提出コード

#include <bits/stdc++.h>

#define rep(i, n) for (auto i = 0; i < n; ++i)

using namespace std;

// vectorの標準入力
template <class T>
vector<T> input_vec(int N) {
    vector<T> result(N);
    rep(i, N) cin >> result[i];
    return result;
}

// 全要素がM以上になるようにLを分割できるか、その際の分割点個数はK以上か
bool judge(int M, const vector<int>& lengths, int K) {
    int cnt = 0;
    int current_sum = 0;
    for (int l : lengths) {
        current_sum += l;

        if (current_sum >= M) {
            cnt++;
            current_sum = 0;
        }
    }

    return cnt > K;
}

int main() {
    // Input
    int N, L, K;
    cin >> N >> L >> K;
    vector<int> A = input_vec<int>(N);

    // Process

    // N個に分割されている前提で各長さを算出
    A.insert(A.begin(), 0);
    A.emplace_back(L);
    vector<int> lengths(N + 1);
    rep(i, N + 1) lengths[i] = A[i + 1] - A[i];

    // 解となるスコアを二分探索
    // [l, r)
    int l = 1;
    int r = L;
    while (r - l > 1) {
        int m = (l + r) / 2;

        if (judge(m, lengths, K))
            l = m;
        else
            r = m;
    }
    int ans = l;

    // Output
    cout << ans << endl;

    return 0;
}