問題一覧 > 通常問題

No.3513 Greedy Yokan Party

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : yt142857 / テスター : aa36 yu23578 Yoyoyo8128 GaLLium Germanium32
ProblemId : 13250 / yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1 (順位表) / 自分の提出
問題文最終更新日: 2026-04-24 21:45:17
yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1の他の問題:

問題文

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

このようかんを用いて、聖君と光君がゲームを行う。ゲームは以下の手順で進行する。
1. 光君が $N$ 個の切れ目の内 $K$ 個を選び、ようかんを $K + 1$ 個のピースに分割する
2. 聖君が $K + 1$ 個のようかんの中から好きなものを1つ選ぶ。
3. 光君が残り $K$ 個のようかんの中から好きなものを1つ選ぶ。ここで選んだようかんのサイズを $H$ とする。

光君は $H$ の最大化を、聖君は $H$ の最小化を目指して行動する。
両者が最適に行動した時の $H$ の値を求めてください。

制約

  • $1 \leq K \leq N \leq 2 \times 10^5$
  • $1 \leq A_1 < A_2 < A_3 < \cdots < A_N < L \leq 10^9$
  • 入力はすべて整数

入力

$N$ $L$
$K$
$A_1$ $A_2$ $A_3$ $\cdots$ $A_N$

サンプル

サンプル1
入力
3 10
2
5 6 9
出力
4

左から5[cm],6[cm]の所で切るのが最適です。
また、左から5[cm],9[cm]の所で切っても最適です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。