競プロ典型90問 001

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)