tests/kyopro_tenkei_001.cpp

• View this file on GitHub
• Last update: 2026-11-04 14:46:41+09:00
• Link: https://atcoder.jp/contests/typical90/tasks/typical90_a

Depends on

• binary_search (Optimization/binary_search.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/typical90/tasks/typical90_a"

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

#include "binary_search.hpp"

int main() {
    long long N, L, K;
    cin >> N >> L >> K;
    vector<long long> A(N+2, 0);
    for (int i = 0; i < N; i++) cin >> A[i+1];
    A[N+1] = L;

    // 長さ x 以上ずつ切って、K+1 個を切り出せるか
    auto check = [&](long long x) -> bool {
        int prev = 0;
        long long num = 0;
        for (int i = 0; i < N+2; i++) {
            if (A[i] - A[prev] >= x) {
                prev = i;
                num++;
            }
        }
        return num >= K+1;
    };
    long long res = binary_search_10(1LL, L, check);
    cout << res << endl;
}

#line 1 "tests/kyopro_tenkei_001.cpp"
#define PROBLEM "https://atcoder.jp/contests/typical90/tasks/typical90_a"

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

#line 3 "Optimization/binary_search.hpp"
using namespace std;

// binary search
template<class T, class FUNC> T binary_search_01(T ng, T ok, const FUNC &f) {
    while (abs(ok - ng) > 1) {
        T mid = ok + ng >> 1;
        if (f(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}
template<class T, class FUNC> T binary_search_10(T ok, T ng, const FUNC &f) {
    return binary_search_01(ng, ok, f);
}
#line 7 "tests/kyopro_tenkei_001.cpp"

int main() {
    long long N, L, K;
    cin >> N >> L >> K;
    vector<long long> A(N+2, 0);
    for (int i = 0; i < N; i++) cin >> A[i+1];
    A[N+1] = L;

    // 長さ x 以上ずつ切って、K+1 個を切り出せるか
    auto check = [&](long long x) -> bool {
        int prev = 0;
        long long num = 0;
        for (int i = 0; i < N+2; i++) {
            if (A[i] - A[prev] >= x) {
                prev = i;
                num++;
            }
        }
        return num >= K+1;
    };
    long long res = binary_search_10(1LL, L, check);
    cout << res << endl;
}

Back to top page