いつまでも 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…