Arantium Maestum

プログラミング、囲碁、読書の話題

PachiCockroach

最近ちょっと競技プログラミングに興味が出ている。理由としては四つあって、

  • C++の練習などにいいのではないか
  • アルゴリズムとデータ構造をより身近にしたい
  • 頭脳パズル的なものをもっとしたい
  • 最近インタビューアとしてアルゴリズム関係の質問をする側に回ることが増えてきた

それでQiitaなどで競プロ関係の記事などを漁っていたらこんなものがあった。

qiita.com

この最初の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でも非常に簡単に定義できるのは嬉しい。

アルゴリズムのポイントとしては、

  • {a_i...a_K}区間ですべてのゴキブリがKまでに退治できると仮定するなら
  • {\frac{\sum\limits_{j=i-1}^K a_j}{K-i-2} }のレートで退治すれば
  • {a_{i-1}...a_K}区間でもすべてのゴキブリがKまでに退治できる

という考えをそのままコードした形。とりあえずO(n)なはず。