典型90 【001 – Yokan Party（★4）】・格闘中①

AtCoderの練習問題に「典型90」というものがあるのでトライしています。
個人的な試行錯誤の記録として投稿することにしました。
今回は第1問のYokan Partyという問題です。

問題「Yokan Party」

羊羹をk+1分割し、その中で最小の羊羹の大きさを最大化する、という問題です。

全探索で解いてみる

まずは、全パターンを洗い出して計算するアルゴリズムでコーディング。
n個中k個を選ぶ組み合わせを全パターン洗い出して最小値を配列に格納していき、最後にその中の最大値を求める、という処理です。

# 変数を取得
nl = list(map(int, input().split()))
n = nl[0]
l = nl[1]
k = int(input())
A = list(map(int, input().split()))

# N個中L個を選択
import itertools
length = list(range(n))

pair = []
pairs = []

if k != 1:
  pairs = list(itertools.combinations(length, k))
else:
  pair = length

# スコアを計算
score = []
score_arr = []
score_num = 0

# pairの場合
if k == 1:
  for i in range(len(pair)):
    num = pair[i]
    len_1 = A[i]
    len_2 = abs(l - A[num])
    score_arr.append(min(len_1, len_2))
  if len(score_arr) != 0:
    score_num = max(score_arr)

# pairsの場合
elif k != 1:
  for i in range(len(pairs)):
    score_arr = []
    tmp = pairs[i][0]
    score_arr.append(A[tmp])
    tmp = pairs[i][-1]
    score_arr.append(l-A[tmp])
    for j in range(len(pairs[i])):
      if j == 0:
        pass
      else:
        num_1 = pairs[i][j]
        num_2 = pairs[i][j-1]
        score_arr.append(abs(A[num_1]-A[num_2]))
    score.append(min(score_arr))
  if len(score_arr) != 0:
    score_num = max(score)
else:
  pass

print(score_num)

（現在整形中です……）

結果

入力例の問題はこれで全て解くことができたのですが……
いざ提出してみると、TLEとなってしまいます。

解決策

他のアルゴリズムで効率化する必要がありそう。
こういったものでは2分探索が有名らしいので、次はそちらで作成してみようと思います。