再帰関数はあんまり再帰が深くなるとスタックオーバーフローの危険があり、できれば非再帰で処理を書きたいというケースが稀にある。 再帰関数はスタックを使えば非再帰で書けるとたまに聞くが、実際どうやれば良いか分からなかったので調べてみた。 典型的…

フィボナッチ数をまとめてみた。 「AOJ2372 - IkaNumber」の解説も入ってる。https://www.dropbox.com/s/6nx2f9htpfyvnkv/fibonacci.pdf競技プログラミングと関係のありそうなフィボナッチ数の話題があったら教えて下さい。とりあえずProject Eulerまわりを…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 ICPC Asia Tokyo 2012 Problem I 問題 図1のようにN個の単語を配置する。 1行にはスペースを含めW文字入る。 入力としては、i番目の単語の長さがxiとして与えられる。 以下良い配置の条件 入…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 問題 頂点数Mの多角形領域の中に，N個のシェルターがある。 多角形領域の中に等確率で位置すると考えたとき、最も近いシェルターまでの距離の期待値を求めよ。 制約 M,N -1000 解法 あるシェ…

現実逃避の続き http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2211 問題 略 解法 答えについて二分探索。 答えをk以下に出来るかどうかを判定したい。 猫と餌入れはx座標でソートしておく。 解説スライドの通り dp[i] = i番目に餌を置いた時に…

現実逃避 問題 n個の椅子がある円卓がある。 ここに8人の王子が座る。 ただし、王子が隣り合ったり、ちょうど向かい合ったりしてはいけない。 このとき、何通りの座り方があるか。 回転したり反転したりして同じになるものも区別して数える。 制約 答えは10^…

しゃくとり法 POJ 2566 - Bound Found 問題 要素数nの数列aが与えられる。 各クエリでtが与えられるので、連続する部分列の中で、和の絶対値がtに最も近いものを求めよ。 制約 n ai t クエリの数やデータセットの数の制約は書いてない 解法 しゃくとり法で各…