Problem - A - Codeforces 復習。本番通ったけどコードが汚かったので書き直し。無駄に dfs とかしてたけど単なる足し算で住む話だった。 書き直しして WA になったりしたあたり本当に実装力が足りないと思った。 class Div2A { public: void solve(void) { …

いつまでも Div2 から抜け出せないへっぽこ緑コーダーなのでDPの勉強にTypical DP Contest の問題を解いてみた。 Div2 Hard は DP ができればきっと解けるようになるだろう!という願望の元に。 結果血反吐を吐くことになる。(半年くらいかかった気がする。) …

T: フィボナッチ - Typical DP Contest | AtCoder kitamasa 法 ほとんどきたまさ法メモ - よすぽの日記を見て理解した。 下のコードは再帰で書いているが再帰でない書き方もあるっぽい。そっちはまだ実装できるレベルではない。(理解できてない。) これで Ty…

S: マス目 - Typical DP Contest | AtCoder dp の状態が vector で表現される dp 接続判定は union find でやる。 class s_squares { public: // // 色の全てのぬり方のうち左上と右下が連結になるようなものの個数を数える // // 列を進めながら DP する？ …

R: グラフ - Typical DP Contest | AtCoder 強連結成分分解とtopological sort が面倒だった。 dp[i][j] を最大にする path2 の経路の保存が必要か?と思いきやそんなこともなかったというのがミソなんだと思った。 class r_graph { public: SCC scc_; // // …

Q: 連結 - Typical DP Contest | AtCoder わけがわからないよ simezi_tan ...(´・ω・｀) 他の人の解説記事をみってもさっぱりわからず、悩みに悩んだ問題。 ループの処理上、いろんな状態遷移を計算しているが、結局初期状態からの遷移が可能なもの以外は消…

P: うなぎ - Typical DP Contest | AtCoder dp の更新のためにさらに dp を使う問題。 const int MOD = (int)(1e+9)+7; class p_unagi { public: // // 根を一つ決めて有向木にして考える // // dp[x][i][j] := x を頂点とする部分木からパスを i 本選び、x …

O: 文字列 - Typical DP Contest | AtCoder 「同じ文字が隣り合わない」というのを同じ文字がとなりあう部分に別の文字を挿入していくことで表現している。 const int MOD = (int)(1e+9)+7; static vector<vector<ll>> nCr_impl; void nCr_init(int maxN) { nCr_impl.re</vector<ll>…

N: 木 - Typical DP Contest | AtCoder dp の問題かと思いきや dp じゃなくても解けた問題。c++ じゃなかったら dp じゃないときついのかな。 MOD が素数なのでフェルマーの小定理を使って割り算を表現する。 const int MOD = (int)(1e+9)+7; static vector<ll> </ll>…

M: 家 - Typical DP Contest | AtCoder bit dp + 繰り返し二乗法。 bit dp すらまともに書けなかった。orz template<typename T> using V = vector<T>; template<typename T> using VV = V<V<T>>; // O(N^3) VV<ll> mul(const VV<ll> &a, const VV<ll> &b, const int M) { int n = a.size(); VV<ll> c(n,V<ll>(n,0</ll></ll></ll></ll></ll></v<t></typename></t></typename>…

L: 猫 - Typical DP Contest | AtCoder 普通に dp すると TLE するが式変形をすると間に合うタイプ class l_cat { public: void solve(void) { int N; cin>>N; vector<vector<int>> f(N, vector<int>(N,0)); REP(i, N) REP(j, N) cin>>f[i][j]; // // dp[i][j] := 猫iまで並べ</int></vector<int>…

K: ターゲット - Typical DP Contest | AtCoder 理解してしまえば簡単に見えるが、理解できるまでに時間がかかった。 class k_target { public: // // Longest Increasing Subsequence の応用 // #define L(a) a.first #define R(a) a.second void solve(voi…

TopCoder Statistics - Problem Statement 復習。本番通せたとおもったら system test で落とされた。 与えられた点が三角形をなし、かつ原点がその三角形含まれるとき、その三角形から脱出するための safe level を計算する必要がある。 本番では三角形の内…

Problem - 557E - Codeforces editorial を見て解くも TLE しまくった問題。結局他の人コードを参考に Trie の add 関数を修正して解いた。 コメントにあるように int と size_t を比較して意図どおりに動かないというバグに見舞われた。 class Div2E { publ…

Problem - 557D - Codeforces 他の人のコードを見て union find を使う方法を知った。グラフの二色塗り分けを union find でやるなんて発想に目から鱗が落ちた。 以下は dfs と union find を使う2つの実装。 class Div2D { public: void solve_dfs(void) { …

Problem - 557C - Codeforces復習、復習。 足の長い方から処理する方針は立ったけど、ある長さの足よりも小さいものからなる最小のエネルギー値を高速で計算する方法が思いつかなかった。 d の上限が小さいことを利用して dcnt を使うのがミソ。 class Div2C…