typical90a

2月くらいにある社内のコードコンテストに向けて典型問題復習中

競プロとかちゃんとやってたの7年ぶり？

その頃も別に特段強くはなかったけど久しぶりにやったら絶望.

問題見た瞬間になんかLでかいけどDPとか行けんのか?

って思って少し考えたけどギブ

なるほど二分探索か

わかってしまえば まぁなんとか.

#include<bits/stdc++.h>

using namespace std;

    int n, l;

    int k;

    int a[100009] = {0};

   

int solve(int x){

    int p = 0;

    int cnt = 0;

    for(int i=0;i<n;i++){

        if(a[i] - p >= x){

            p = a[i];

            cnt++;

        }

    }

    if(l - p < x) cnt--;

    if(cnt >= k) return true;

    else return false;

}

int main(){

    cin >> n >> l;

    cin >> k;

    for(int i=0;i<n;i++) cin >> a[i];

    int ok = -1;

    int ng = l;

    while(ng - ok > 1){

        int mid = (ok + ng)/2;

        if(solve(mid)) ok = mid;

        else ng = mid;

    }

    cout << ok << endl;

}