mayoko’s diary

プロコンとかいろいろ。

アルゴリズム

KMP 法について

文字列処理アルゴリズム全然知らないので調べてみることにしました。とりあえず KMP 法について書きたいと思います。 そもそも KMP 法とは KMP 法は, 文字列 S (sentence?) の中で, 文字列 W(word?) が現れる場所を列挙するアルゴリズムです。例えば, S = "a…

主にこれを参考にしました。こっち読んだほうが良いと思います(これは自分用のメモ)。 http://www.i.kyushu-u.ac.jp/~eiji/GraphCombinatorics/graph-combinatorics5.pdf ラベルつき木の数は 証明の仕方も面白いですね。辺ラベルが付いている根付き木を Un, …

unordered_map について

unordered_map で辛い思いをしたので twitter でわーわー言ってたらいろいろ勉強になったのでメモします。 まとめ 基本的にチェイン法っていうのでやってるっぽい vector > みたいのをイメージするとわかりやすい 詳細 まとめで書いたように, 基本的には vec…

ラグランジュ補間について

なんとなくメモ。 ラグランジュ補間のアイデア に関する N 次多項式 を, というヒントから表したいです。この時, とすれば, と表せることに注目します。 このように書くとハッピーなのは, とすると, を満たす について, が成り立つことです。このことから, …

素因数分解について

前々から書く時ちょっと迷うことがあったのでメモ。整数 の素因数分解を O() でやります。 void calc(ll x, map<ll, int>& M) { for (ll i = 2; i*i <= x; i++) { int cnt = 0; while (x%i == 0) { x /= i; cnt++; } if (cnt) M[i] += cnt; } if (x > 1) M[x] += 1; }</ll,>

Nim について少しメモ

東京工業大学プログラミングコンテスト2015 の M - コインと無向グラフ を解こうとして Nim かなーと思って Nim について調べました。 今度はちゃんと Nim について理解できた気がしたのでざっくり書いていきます。問題設定とかは以下の記事を参考にします。…

最小カットについて

先ほどの記事(SRM 653 div1 med:Singing - mayoko’s diary)で ① ・頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない ・必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)…