PachiCockroach
最近ちょっと競技プログラミングに興味が出ている。理由としては四つあって、
それでQiitaなどで競プロ関係の記事などを漁っていたらこんなものがあった。
この最初のPachiCockroach問題、パッと解けそうだなーと思ったのでPythonで書いてみた。
import operator import math def reductions(f, v, seq): x = v for y in seq: x = f(x, y) yield x def roach(nums): reductioned = reductions(operator.add, 0, reversed(nums)) running_averages = (n/(i+1.) for i, n in enumerate(reductioned)) return int(math.ceil(max(running_averages)))
reductionsはclojureではじめて知った関数で、reduceの途中経過を一つずつsequenceとして返す。
reductions(f v seq)
は[f(v, seq[0]), f(f(v, seq[0]), seq[1]) ...]
となる。
この高階関数、決まる時はすごく便利なのだが使われているのも開設されてるのもあまり見なくて寂しい。Pythonでも非常に簡単に定義できるのは嬉しい。
アルゴリズムのポイントとしては、
という考えをそのままコードした形。とりあえずO(n)なはず。