今回は以下の問題を考えます。 長さNの数列x[1], x[2], ..., x[N]と数Kが与えられます。y[i] = min{x[i], x[i+1], ..., x[i+K-1]} (i = 1, ..., N-K+1)として定義される数列y[i]を計算しなさい。 この問題は両端キュー（デック, deque）を用いることで、なん…

今回は以下のランダムウォークの問題を考えます。 I×Jの大きさのグリッドがあります。(1,1)からスタートして、1ターンに上下左右4マスのうち移動できる方向にそれぞれ確率p1,p2,p3,p4で移動します。いくつかのマスには石が置いてあり、通行不可能になってい…

「プログラミングコンテストチャレンジブック [第2版]」（通称：蟻本）という本がとてもよかったので、これから3回にわたって統計モデルを絡めた感謝の記事を書こうと思います。 プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム…