これまではJavaScriptとかでやってたけどRの方が綺麗なのでRで書くことにした。とりあえず、手動で手を加えやすくしたいので中間ファイルを噛ませることにする。プログラム中で次のようなファイルを吐く。 TEXT -10 0 S POINT 5.7924 8.15157 COLOR BLUE CIR…

確率や期待値のDPで式を立てたとき、連立一次方程式 Ax = b を解きたくなることはよくあります。競技プログラミングで使うようなものに限っていくつかメモしておきます。 クラメルの公式 行列式を計算することで厳密解を求めます。nが小さい(2や3)ときに式を…

ライブラリを書くときは名前の衝突を回避するため構造体か名前空間にくるんで書くことにしているけど、蟻本を参考にSuffixArrayを構造体で書いてみたら困ったことがあった。 struct Foo{ int as[10], ids[10]; bool cmp(int i, int j){ return as[i] < as[j]…

ここを読んで勉強した。 コメント読むとKMPと等価とか書かれているけどよく分からない。とりあえずパターンマッチングのO(M+N)が使えるのは良い。 原理の解説も元記事にあるけど、とりあえず入力とパターンマッチングへの応用法だけ書いておく。 長さLの文字…

問題概要 ノード数V( 解法 まず根付き木の場合を考える。 頂点vを根とした部分木にハッシュ値f(v)を割り振る。f(v)は子の部分木のハッシュ値の集合から生成するようにする。この際ローリングハッシュ的な生成方法だと何故か頻繁に衝突してしまうことに注意。…

要素が整数の行列に対して行列式をMOD Mで計算する。Mは素数でも合成数でも構わない。 SPOJ DETER3で動作確認。 計算量はO(sqrt(P) + N^3 * log^2 P)くらい？ グラフの問題とかで役に立つ場面があるかもしれないしないかもしれない。 namespace DeterminantI…

こことか蟻本を参考にして、色々実装を試してみた。 RMQ まず、インターフェースをはっきりさせよう。とりあえずD言語で書くけど、そこまで言語依存な書き方はしていないのですぐにC++なりJavaなりに移せるはず。D言語とかコンテストでは大抵使えないし言語…

概要 サイコロを使った問題はよく出る。サイコロのクラスを作っておいたりして準備はしておくべきだけど、状態遷移図を書いたら一目で直感的に色々分かるんじゃないかと思ってgraphvizで出力してみた。書いてみて分かったことは、こんなの役に立たないので実…

keyword 最大流 Ford-Fulkerson C++ 入力 流量を表す行列、sourceの番号、sinkの番号(いずれも0-base)を与える。行列については流れないとき0(実は負でも良いけど)を入れること。流量が実数の場合はアルゴリズムが終了する保証はない。 出力 sourceからsink…