https://atcoder.jp/contests/typical90/tasks/typical90_a
話題になっていた問題です。
少し考えれば、スコア以上が成り立つかは簡単に求められるので、二分探索するだけですね。これで十分速いです。
以下は、PyPy2のコードです。
# coding: utf-8 # Yokan Party from itertools import count #################### library #################### def read_int(): return int(raw_input()) def read_tuple(): return tuple(map(int, raw_input().split())) def read_list(): return list(map(int, raw_input().split())) #################### naive #################### #################### process #################### def read_input(): N, L = read_tuple() K = read_int() As = read_list() return (L, K, As) def F(L, K, As): def is_cuttable(length): n = 0 prev_pt = 0 for A in As: if A - prev_pt >= length: n += 1 if n == K+1: return True prev_pt = A else: return L - prev_pt >= length and n == K def bin_search(first, last): if first == last - 1: return first mid = (first + last) / 2 if is_cuttable(mid): return bin_search(mid, last) else: return bin_search(first, mid) return bin_search(1, L/(K+1)+1) #################### main #################### L, K, As = read_input() print F(L, K, As)