https://db.tt/KixudqAX ライセンスはCC0です。何でも自由に使って・コピペ・改変・再配布してよいです。これを使用した場合のいかなることにも責任を持ちません。 '#'で始まるファイルは未検証、'!'で始まるファイルは検証済みであることを表していましたが…

part1 フィボナッチ数の小ささ fib(n)は指数オーダーで結構大きいが、2^nよりは全然小さい。 "SRM 451 DIV1 Hard BrickPuzzle"は列DPを特定の形のブロックでするもの。ブロックの形が、下側が絶対2つ単位で隣接しているため、そのような形の状態しか覚えなく…

SRM400代のHardで使ったものを見てみる。最初は全部記事書こうかと思ったがめんどくさくてやめた。 桁落ち誤差回避 ほとんど等しい2つの数を引き算すると、有効桁数が減少する。 式変形をして引き算をなくしたりする必要がある。 SRM 400 DIV1 Hard Collecti…

http://db.tt/vepDPsYK ライセンスはCC0です。 '#'で始まるファイルは未検証、'!'で始まるファイルは検証済みであることを表しています。 これを使用した場合のいかなることにも責任を持ちません。 "~template.cpp"はTopCoder以外用のテンプレートです。 "a.…

非常に雑多。しばらく作問もしないので、吐き出しておきます。 単純でない辞書順greedy 辞書順最大の経路履歴みたいに極小・極大であることを利用するとか？ 永続データ構造使いたい meldable-Priority-queue DPしたい 既存の計算結果を埋め込んでどうにかで…

参照 ウェーブレット木の世界 http://code.google.com/p/wat-array/ コメント ウェーブレット木のほうも実装してみたが、ウェーブレット木の世界のスライドに「(ウェーブレット木よりウェーブレット行列を)"常にこちらを利用すべき？"」とあるように、ウェー…

※Wikipedia読んだだけ Reference: http://en.wikipedia.org/wiki/Nimber http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem ゲーム 二人、有限、確定完全情報、 「normal play condition」(動きができない時、かつその時に限り負ける) 「imparti…

三分探索は、ある1つ以下の点で傾きの正負が入れ替わる場合に、その点(最小値/最大値)を求めるアルゴリズム。 また、その分割を黄金比にすると多少効率がよくなるらしい。 たまに想定解でなくてもこれで解ける時があると思う。 二分探索は、ある1つ以下の点…

※あくまでメモ・信頼性は全くない N文字のK種類の文字からなる文字列strで、「i番目以降に文字cが出てくる最初のインデックスを各i,cについて全て求める」は後ろからやるとO(NK) int dp[K][N+1]; for(int c = 0; c < K; c ++) { dp[c][N] = INF; for(int i =…

頂点被覆(vertex cover)とは、あるグラフの点のサブセットであって、全ての辺がその点に接しているものをいう。 最小点被覆とは、点被覆の大きさをできるだけ少なくするもので、一般の場合では(決定問題に"グラフCに大きさk以下の頂点被覆があるか"として変…