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

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

※全然まとまってない 参照 http://imoz.jp/algorithms/imos_method.html 早稲田大学プログラミングコンテスト I: その味は甘くて 解説スライド 呼び方 自分はこの記事では、以下の呼び方を使います。特に、演算とそれを用いたアルゴリズムの違いに、"〜法"を…

参照 Matrix Reference Manual "Special Matrices" Autumn Fest 2012 解説スライド "Ninja of Train" あとwikipedia。(wikipediaをreferenceにするのって…) このエントリについて 行列累乗の高速化としての問題が作れる、行列の特殊形を3つメモする。 実際の…

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

今まで見た問題の SRM 300〜SRM 400 くらいのコメント部分から、適当にメモを見て、適当に書きだしてみる。 非常に雑多。 行列累乗 最後にベクターを掛けるのを、結合律によって先に掛けちゃえる、ということ。 v*A*B*C*... = v*(A*B*C*...) ベクターをv[N]…

確率・期待値を求める問題で多い、漸化式。 f(x) = c + g(x)*f(x-1) + (1-g(x))*f(x) <-> f(x) = (c + f(x-1)*g(x)) / g(x)f(x) = c + (p*x)*f(x-1) + (1-p*x)*f(x) f(0) = 0 <-> f(x) = c * H(x) / pここで、 H(x) = Σ_(k=1..x) (1 / k)このHは調和数(Harmo…

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

SRM 360 DIV1 Easy のこのhttp://community.topcoder.com/stat?c=problem_statement&pm=7875&rd=10772問題で。 想定解ではないらしいが、何回かSystem Testをやっても通る。 コードのメイン部分 #define N 1000000 int t[55][55]; struct SumOfSelectedCells…

今、bfs力が非常に足りない。問題を見てbfsだとわからないし、書けない。それを直そう。 とりあえず色々列挙してみる。 状態の管理には、queueを使う。イテレーションが少ない時には、配列でヘッドとテイルのポインタやインデクスを持つ形にしてもいい。 cur…

行列累乗がよくわからない。どうしたらその遷移行列を見つけられるのか？ とりあえず制約からヒントを得よう。 n k nはアルファベットの数など、見えにくい形のものも多い。 そもそも行列の掛け算とは、 C_ij = Σk (A_ik B_kj)というシンプルな形。 新しい状…

今やっていた、SRM 430 DIV1 Medium TwinTowns。 このrng_58さんの解答を参考に書いた下のコード。 typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii; const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL; </pii></int,int></int>…

DPは最終的な評価のみが要素になるわけじゃない。 最小化したかったりしたいものが有ればそれがDPになる。 逆に、最終的な評価などをインデックスにできる。 最後には全部とかを舐めて、Validであるインデックスのmaxを取ったりすれば良い SRM 451 DIV1 Medi…

練習でも、 問題を読む 制約を見る 〜10: O(n!) 15〜20: O(2^n) 30〜40: O(2^(n/2)) 50: O(n^4)程度, DP, グラフ 〜10^14: O(√n) 考えて 適当に分割してみる サブ問題に再帰的に分割できる？ 小さな場合を制約式のようなものに展開する 一旦考えなおす さら…

不等式の場合、それは順序関係で、 順序関係で有向グラフにするという考え方はありだ。 循環があるかの判定(dfs/bfsでおｋ)で矛盾があるかが判定できる 矛盾がない場合それはDAGということなので、DAGとして色々考えられる グラフにしよう

DAGの最小パス被覆 パス被覆(path cover)とは、あるグラフのパスの集合であって、そのグラフの全ての点がそのパスに含まれているものをいう。 最小パス被覆とは、パス被覆の中で、パスの数が最小のものをいう。 DAGの最小パス被覆は二部グラフの最大マッチン…