なぜ， 最小費用流 @ C++ - 落書き、時々落学 をしたかというと，仇打ちです．当初，最小費用循環流を実装していた． →できた →検証しよう →UVa 10594 時間オーバー，別の問題（2部グラフの最小費用最大マッチング）ではOKだった． →別のアルゴリズムで UVa …

最小費用流実装した． 最小費用流のアルゴリズムは少なくとも3種類ぐらいある． とりあえず，フローを求めてから，負閉路を頑張って消していく 最小費用0フローからはじめて，augmenting shortest path で増やしていく push, relabelの一般化（よく知らない…

まず基本から． const Struct s; // s is a const Struct.const Struct* s; // s is a (non-const) pointer to a const Struct.Struct* const s; // s is a const pointer to a (non-const) Struct.では， const Struct** s; const Struct* const* s; const …

Problem 279 - Project Euler似た問題を昔やったような．なぜか愚直な方法と賢い方法の答えがあわずに苦戦した． どうやってもあわない． 実は愚直な方法が間違っていたという，情けないオチ．Haskellで約2秒． C++で約0.3秒． こんなもん？

最大流アルゴリズムを実装した．Edmonds Karpは増大道に沿ってフローを更新（大域的操作）に対して， Push RelabelはPush か Relabel（局所的更新）のみ． だから，楽に実装できると思ったら，実はたいして変わらなかった．Edmons Karp // O(VE^2), BFS = O(…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=117&problem=2870&mosmsg=Submission+received+with+ID+7753701有向グラフが与えられる．何個の頂点を選べば，それらから出る有向道で頂点を被覆できます…

前回の続き．今回は強連結成分分解する． しかも，DFS1回だけ実行． アルゴリズムは非常にシンプル．そして，結構分かりやすいと思うのだが． アルゴリズムの解説等は以下が比較的分かりやすいと思う． http://www.ics.uci.edu/~eppstein/161/960220.html#sc…

Project Euler等で時々C++を使うのだが， いまだかつて，classを一度たりとも使っていないことに気がついた． まぁ，僕は「オブジェクト指向なんてくそくらえ」な立場なので問題ないといえば問題ないが．しかし，使えるに越したことはない． ということで練…

C++ には関数内関数がないらしい． struct使えば，似非関数内関数は作れるが， この似非関数内関数は親関数の変数に触ることができない．例えば，以下のプログラムはコンパイルエラーになった． // test.cpp int main() { int c = 0; struct Func { void ope…

問題は Partitioning for fun and profit． 雰囲気． 入力は自然数 m, n, k． m を n 個 の昇順な自然数に分割する分割を考える．分割の間に辞書式順序を入れたときの k 番目の分割を求める． 例えば，m = 5, n = 3, k = 1 なら，求める分割は [1, 1, 3]． …

UnionFindさえあれば，結構簡単に実装できるのね． ただ，正しく動くかほとんど確認していないので，バグがあるかも． // disjoint_set.h #include <iostream> using namespace std; class UnionFind { private: int *root, *rank; // root < 0 のときはサイズの情報 p</iostream>…

有限体上で連立方程式を解くプログラム（ガウスの消去法の実装）． 基本は実数体上のガウスの消去法と同じ． 除算を有限体での逆元にするだけ（拡張ユークリッドの互除法）． ランク落ち？対策は思ったより簡単だった． 例えば，2元体上で 1 1 1 1 1 1 0 1 0…

vector<foo> xs; として， *(xs.begin()) とすれば，xsの先頭要素にアクセスできる． しかし， *(xs.end()) では，xsの最終要素にアクセスできない． xs.back() で良い．</foo>

Problem 275 - Project Euler問題の概要． ある条件を満たす，polyominoを探す． その条件の１つは，横方向にバランスがとれていること（重心のx座標が0）． 詳細な条件は上のリンクで． 絵でみると分かりやすい． 下図はproject eulerからの引用． 求めるの…

Problem 271 - Project Euler Problem 272 - Project Euler 誤解を恐れずに，問題の雰囲気を紹介すると．「n が与えられて，x^3 = 1 (mod n) となる x は？」です． ある性質が鍵だと思う． 271のほうは多分簡単． Haskellでも実行は一瞬． 272はそんなに難…

Problem 264 - Project Euler いつもの整数問題． とりあえず，愚直な方法をHaskellで実装して， 遅くて，遅くて，しかたなったので， C++ならいけるはず（この計算量なら）と思い， C++で実装したら，約60倍速くなった．びっくり．しかし，愚直な方法なので…

Problem 261 - Project Eulerん？運良く解けた？ 計算スピードのために，多分正しいショートカットを使っているから，良く分からない． はじめは N=10^11だと思ってました．しかし，また，フォーラムにマジカルな（理解できない）解法が載っていた．うーん．…

Problem 260 - Project Euler 21ゲーム（交互に数字を言って，21を言ったら負け）みたいなノリ．メモリが沢山あるマシンなら，簡単（比較的簡単な全探索で解ける）だと思う．最初は，loosing configurationの条件が，バシッと書けると思い，小さい数字でいろ…

累乗って，いままで， inline void pow(int a[N], long long n) { if (n == 1) { return; } else if (n%2) { int b[N]; REP (i, N) b[i] = a[i]; pow(b, n-1), mul(a, b); } else { mul(a, a), pow(a, n/2); } } こんな，ふうに書いていた． （配列を累乗し…

けっこう，（といっても，4，5日前だが）に解いた．問題文は簡単．g(k) = 1 if 0 g(k) = g(k-2000) + g(k-1999) if 2000 find g(10^18) (mod 20092010)普通のFibonacciだったら，簡単ですが． そう簡単にはいかない．まぁ，それが今回の問題ですか． Haskell…

NTL は Number Theory Library の略．詳しくは，以下の公式（？）ページで． http://www.shoup.net/ntl/ AURにパッケージがあったが，libntl.a しかインストールされなかったので，自前で．PKGBUILDつくって．makepkg -s.でおしまい． pkgname=ntl pkgver=5.…

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml に参照はconstで使うように．って書いてあった． 理由はたしか，意味はポインタなのに，構文は値だから，だったような． いわれてみれば，そのとおり． でも読みにくよね．

http://www.google.co.jp/url?sa=t&source=web&ct=res&cd=2&url=http%3A%2F%2Fwww.amazon.co.jp%2F%25E7%25B5%2584%25E5%2590%2588%25E3%2581%259B%25E6%259C%2580%25E9%2581%25A9%25E5%258C%2596-%25E7%2590%2586%25E8%25AB%2596%25E3%2581%25A8%25E3%2582%…

書いてみた． Haskellでは，面倒になることが予想されたので，C++で． 多分，標準的な解法だと思う．ただのDP. #include <iostream> #include <cstdlib> using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) const int R = 50, C = 50, U = R*C+1; char</cstdlib></iostream>…

2008年のGoogle Code Jamをちょっとだけやった． 2部グラフのマッチングの応用があった． 模範回答（？）のコードが想像以上に短かった．こんな感じ． #include <iostream> #include <vector> #include <cstring> using namespace std; #define FILL(xs, x) memset(xs, x, sizeof((xs)))</cstring></vector></iostream>…

ある規則性を観察できれば，おしまい． もう，解けたも同然である． （と思っていた．今，考えなおすと，たんなる必要十分条件を求めただけで，それが偶然十分必要条件でもあった．ラッキー）しかし，アホなコーディングしたせいで，時間がかかった． どうに…

haskellで書いたら遅かったので，C++で書いてみた． アルゴリズムはほぼ同じ．メモ化再帰ではなく，配列でビルドアップ．実は numeric_limits::max() で intの最大値がとりだせるらしい． #include<iostream> #include<cmath> #include<limits> using namespace std; int main() { int</limits></cmath></iostream>…

練習のためやってみた． Bは問題文が長いので，まだ読んでいない．（前回と同じテンプレート使用） A 各baseに対するhappy数達を,無限リストとして，計算しておいて，最後にintersectionをとる． という，作戦だが，どうも遅い．メモリを沢山使う． やはり，…

Problem 255 - Project Euler解いた．前2問に比べると簡単だと思う（もう内容忘れかけているが）．はじめにHaskellで解いたら，実行時間は3分ぐらいだった． 再帰を使おうとしたら，stack space overflow． seq入れてみたり，!入れてみたりして，stack space…

Container classes, C++ FAQ によると，生のarrayより，vectorを使ったほうがベターだそうです． 理由としては より生産定期になる ロバストなコードになる 他人がメンテしやすい vetorにはat()がある(out of bounds を検知） メモリ管理が楽 インサートした…