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 で区間…