💪

【チャレンジ記録】競プロ典型 90 問_1問目

2022/01/06に公開

競技プログラミング

※勉強中のため、考察など後ほど付け加える可能性があります。

問題

考えたこと

ソートして小さいものから何かするのかと考えてしまった。
セグ木なら一度に区間の和を求められるかもと考えた。

解答

twitterを見てから解答した。

#include <bits/stdc++.h>
#include <atcoder/all>
#include <vector>
#include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
#define ll long long
using namespace std;
using namespace atcoder;
const ll MX = 1e6;
const ll inf = 1e13;
const int mod = 1000000007;
vector<int> a;
int n,l,k;
bool check(int now) {
    int cnt = n-k;
    int b = 0;
    FOR(i,1,n+2) {
        if(a[i]-a[i-1]>=now) {
            b++;
            if(b==k+1) return true;
            continue;            
        }
        int curr = i;
        while(cnt>0 && a[i]-a[curr-1]<now && i<n+1) {
            i++;
            cnt--;
        }
        if(a[i]-a[curr-1]<now) return false;
        else b++;
        if(b==k+1) return true;
    }
    return true;
}
signed main() {
    cin>>n>>l>>k;
    a.resize(n+2);
    a[0]=0;
    rep(i,n) cin>>a[i+1];
    a[n+1]=l;

    int h = 0;
    int e = l;
    int now = l/2;
    while(h<e) {
        now = (h+e)/2;
        if(check(now)) {
            h=now+1;
        }else{
            e=now;
        }
    }
    if(check(now)){
        cout << now << endl;
        return 0;
    }
    cout << now-1 << endl;
    return 0;
}

問題

考えたこと

解答

Discussion