0424進捗

Atcoder典型90問 001 - Yokan Party

▶︎ https://atcoder.jp/contests/typical90/tasks/typical90_a

問題

左右の長さが
L [cm] のようかんがあります。
N 個の切れ目が付けられており、
左から i 番目の切れ目は左から Ai [cm] の位置にあります。

あなたは N 個の切れ目のうち K 個を選び、ようかんを K+1 個のピースに分割したいです。
そこで、以下の値を スコア とします。

K+1 個のピースのうち、最も短いものの長さ（cm 単位）
スコアが最大となるように分割する場合に得られるスコアを求めてください。

制約

1 \leq K \leq N \leq 100000 \\
0 < A_1 < A_2 < ... < A_N < L \leq 10^9 \\
入力はすべて整数

試したこと

・全パターン数え上げは悪手じゃろ...ということでそもそも選ばない。
・動的計画法でやろうとしたがうまく組めなかった。今回の場合、「長さLの中でi+1個の切れ目の中からj+1個の切れ目を選ぶこと」を、「長さLの中でi個の切れ目の中からj個の切れ目を選ぶこと」にうまく帰着できないため失敗したと思われる。たしかに、i+1個目の切れ端を選んだ時点で長さがLじゃなくなってしまうのはあまりにまずい解法な気がする。
・一つのアルゴリズムにこだわりすぎるのはよくない。

適切な方針

・貪欲法で「x以上のスコアを実現できるか」を判定する。それを用いて二分探索で実行可能な領域の最大値の探索。
・スコアxで実現可能ならスコアx-1でも実現可能、という最小値の性質を活かした解法。
・あるスコアxに関して実行可能かどうかが貪欲法でO(N)で全探索して判定できることに気づいて、その実行可能領域が上または下のみに有界なら二分探索で境界を求められる って思考をすべきだった。言われてみればそりゃそうかって話。
・解けなかったの悔しい。次は解きたい。

解説付きコード

#すべての長さをx以上にできるかどうか判定する関数
def is_cutable(x, N, A):
  #何回切ったか
  num = 0
  #最後に切ったのはいつか
  pre = 0
  
  #xを超えたタイミングで切っていく
  for i in range(N):
    if A[i] - pre >= x:
      num += 1
      pre = A[i]
      
  #Lから最後のpreまでのあまりも、x以上なら切ったと考える
  if L - pre >= x:
    num += 1
  
  #numにはx以上の切れ端の数が格納されている。
  #numがK+1を超える→切れ端をK+1個用意できる→K回切った上で最小の切れ端はx以上
  return (num >= K + 1)
 
[N, L] = list(map(int, input().split()))
K = int(input())
A = list(map(int, input().split()))

#二分探索(最大のxを探しにゆくのさ)
left = -1
right = L+1

while (right - left) > 1:
  mid = (left + right) // 2
  
  #midになるよう切れるなら探索範囲はmidより上側
  if is_cutable(mid, N ,A):
    left = mid
  
  #midになるよう切れないなら探索範囲はmidより下側
  else:
    right = mid

print(left)

参考コード