典型90 - 001 - Yokan Party（★4）

考え方

最小値を最大にする問題なので，二分探索ぽい．

実際，

• 答え$x$を決め打ちすれば，$K+1$個に分割できるかどうかは$O(N)$でシミュレーションでき（※），
• ある値を堺に$K+1$分割できる / できなくなるが決まる

となるから二分探索でできる．

※：シミュレーションは，左から見ていき$x$以上になるたびに切れ込みを入れればよい．

【2 日目】
昨日の解説と今日の典型問題です。問題 001 については E869120 の想定ソースコードも GitHub に追加しました。今日は昨日と比較すると少し易しい問題だと思います。（昨日と同様、入力形式・入出力例は GitHub を参照のこと） #競プロ典型90問 pic.twitter.com/ewcAKEKEP1

— E869120@本発売 (@e869120) March 30, 2021

回答例 (Python)

N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split())) + [L]

def f(x):
  cnt = 0
  i = 0
  l, r = 0, 0
  while i < N + 1:
    r = A[i]
    if r - l >= x:
      cnt += 1
      l = r
    i += 1
  if cnt > K:
    return True
  else:
    return False
  
ok = 1
ng = L + 1
while ng - ok > 1:
  mid = (ok + ng) // 2
  if f(mid):
    ok = mid
  else:
    ng = mid
    
print(ok)

回答例 (C++)

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

int N, L, K;
vector<int> A(1 << 20);

bool f(int x) {
  int i = 0, l = 0, r = 0, cnt = 0;
  while (i < N + 1) {
    r = A.at(i);
    if (r - l >= x) {
      cnt++;
      l = r;
    }
    i++;
  }
  if (cnt > K) {
    return true;
  } else {
    return false;
  }
}
         
int main() {
  cin >> N >> L;
  cin >> K;
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  A.at(N) = L;
  int ok = 1, ng = L + 1; int mid;
  while (ng - ok > 1) {
    mid = (ok + ng) / 2;
    if (f(mid)) {
      ok = mid;
    } else {
      ng = mid;
    }
  }
  cout << ok << endl;
  return 0;
}