アルゴリズムの勉強にどうせなら新しい言語を使おうと思って D 言語を見つけたので、試しに手元のダイクストラ法の実装(c++)を移植してみた。 DMD v2.060 だとコンパイルできないので AtCoder / AOJ 等で verify できんかった...orz(2015/5/31現在)。まあ多…

D: サイコロ - Typical DP Contest | AtCoder 最初素因数分解ライブラリ関数をつかって D を分解しようとして TLE していた。 template <typename T> using V = vector<T>; template <typename T> using VV = V<V<T>>; using Vd = V<double>; class d_saikoro { public: void solve(void) { int N; ll</double></v<t></typename></t></typename>…

C: トーナメント - Typical DP Contest | AtCoder class c_tournament { public: // x が y に勝つ確率 double win(int x, int y, const vector<int> &el) { return 1.0/(1.0+pow(10.0,(el[y]-el[x])/400.0)); } void solve(void) { int K; cin>>K; int N = (1<<K); vector<int> e</k);></int>…

プログラミングコンテストの問題を解いていて dp[i][j][k] += dp[i-1][j][k] みたいに多重配列が必要なときがわりとある。この多重配列を用意して初期化する方法は２つあって、 std::vector を使って多重配列を用意する。 vector<vector<vector<int>>> dp(100,vector<vector<int>>(50,vector<int></int></vector<int></vector<vector<int>…

B: ゲーム - Typical DP Contest | AtCoder どうやって最適化戦略をとった状態を表現するのか？ すぬけ君の得点を dp 対象にして、すぬけ君はそれを最大化・すめけ君はそれを最小化しようとする。 山の高さが i,j のとき先方の得点を dp 対象にして、それを…

A: コンテスト - Typical DP Contest | AtCoder class a_contest { public: void solve(void) { int N; cin>>N; vector<int> p(N,0); REP(i, N) cin>>p[i]; sort(RANGE(p)); int M = 10100; vector<bool> dp(M, false); dp[0] = true; REP(i, N) { // 順方向だとたった</bool></int>…

Chinese Postman Problem | Aizu Online Judge 元のグラフにいくつかパスを加えてオイラー閉路にする。 あらかじめダイクストラ法最小パスを求めておいて、dp を使ってそれらのうち最適なものを計算する。 // // オイラー路とは、グラフ（グラフ理論）の全て…

Traveling Salesman Problem | Aizu Online Judge 蟻本にものっていたやつ。 bit DP を使う。 class traveling_salesman_problem { public: // O(2^V*V^2) void solve(void) { const int inf = (1<<30); int V, E; cin>>V>>E; vector<vector<pair<int,int>>> tree(V); REP(i, E) {</vector<pair<int,int>…

赤黒木を実装してみた。 本当は永続赤黒木を実装してみたくてまずは赤黒木からやることに。 merge/split ベースでやる merge/split の中で new/delete をやるせいか、実装が悪いせいか、Treap の方が insert がずっと速い...orz new/delete を boost pool に…

Treap を実装してみた。 merge/split ベース。 実装は プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～ を参考にした。 遅延評価を使った add も実装。 実装するまで merge/split って何に使うのかいまいちわかんなかったけど、split で区間…

最大正方形 | 動的計画法 | Aizu Online Judge * 隣接する三点の dp 結果だけで現在の地点を含む最大正方形の幅がわかってしまう。 * ALGORITHM NOTE 最大正方形の面積 正方形探索を参照した。 class max_square { public: // O(H*W) void solve(void) { int…

一度蟻本を読んでいたんだけど、動的計画法が全く使いこなせないので改めて練習。 そのときのメモとコードを備忘録としてのせておく。 0-1 Knapsack Problem | Aizu Online Judge * 基本的な 01 knapsack。 * ループの方向を変えないといけないのはどんなと…