codeIQ ホリエもんからの挑戦状解けず(Python)

Pythonで書きましたが、制限時間一秒以内という制約を突破できませんでした。Pythonで解けた人いたらコード見てみたい。

後述(2015年7月10日): 解説が発表されていました。


【問題】

つなぎ合わせたときの長さLと、N個(1≦N≦5000)の棒の長さが標準入力から与えられるとき、N個の棒の中から3つをつなぎ合わせて長さがLになる組み合わせの総数を求めるプログラムを書いてください。ただし、個々の棒の長さや、つなぎ合わせた長さ(L)は正の整数で、32bit整数で十分扱える範囲です。また、棒の長さはすべて異なるものとします。


【入力】

標準入力から、以下の形式で複数の整数値を読み込みます。

L
Na1
a2


aN

1行目のLは、つなぎ合わせた棒の長さです。
2行目のNは、棒の数です。
3行目以降のN行は個々の棒の長さで、長さはすべて異なるものとします。

import fileinput

numbers = []

append = numbers.append

for line in fileinput.input():

    append(line)



numbers = [int(i) for i in numbers]



lngth = numbers[0]

N = numbers[1]

numbers = sorted(numbers[2:])[::-1]



cnt=0

sl = lngth//3

for i in range(N):

    x0 = numbers[i]

    if x0>sl:

        for j in range(i+1,N):

            x1 = numbers[j]

            rest = lngth-x0-x1

            rest_numbers = numbers[j+1:]

            cnt+=len([1 for x2 in rest_numbers if x2==rest])

    else:

        break

        
print(cnt)

コメント