プログラミングコンテストチャレンジブック買った

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

読み途中。各問題に対する解答例とC++のソースコードが載ってるので、暇なときにpythonに翻訳している。例えばしゃくとり法についてだと以下のようになる。

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys

def main():
    print(syakutori())

# 総和がS以上となる
# 部分列の長さの最大値を求める
def syakutori():
    INF = sys.maxint

    n = 10                      # 数列aの長さ
    S = 15                      # 総和の最低値
    a = (5,1,3,5,10,7,4,9,2,8)  # 数列

    s = 0                       # 部分和の開始地点
    t = 0                       # 部分和の終了地点
    sum_x = a[0]                # 部分和の総和
    res = INF                   # 最小区間

    while(1):
        # tを伸ばしていく
        while(sum_x < S and t + 1 < n):
            t = t + 1
            sum_x = sum_x + a[t]

        if sum_x < S:
            break
        res = min(res, t - s + 1)

        # sを伸ばしていく
        s = s + 1
        sum_x = sum_x - a[s]

    return res

if __name__=='__main__':
    main()

やってると無限に時間が潰せるのでコスパが良い。