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

J: ボール - Typical DP Contest | AtCoder 条件付き期待値による方程式を立ててとく問題。以下の記事が超わかりやすい。 期待値と条件付確率 - math314のブログ // // いつまでたってもボールがあたらない場合の計算式はどうなる？ // p*p*p*... // // => …

I: イウィ - Typical DP Contest | AtCoder // // iwiwii -> iwi -> // ~~ ~ ~~~ // 残りが連結されることを考慮しないとダメ // // 区間に対する DP でやる // // ある区間 [l,r) の削除数がわかったとして、 // // wiwiwi -> wwi // -> wiw // // のように…

H: ナップザック - Typical DP Contest | AtCoder // // * 普通に考えると dp[used_color_sum][weight_sum] を更新する。 // => どの色を使ったのかの判定はどうする？ // => 色ごとに DP を更新していけばよい。 // class h_knapsack { public: void solve(…

G: 辞書順 - Typical DP Contest | AtCoder class g_lexicographical_order { public: void solve(void) { string S; ll K; cin>>S>>K; // dp[i] := i 文字目の文字をつかい、i 文字以降の文字を使うまたはつかわないときのユニークな文字列総数 // // 01234…

F: 準急 - Typical DP Contest | AtCoder const int MOD = (int)1e9+7; class f_semi_express { public: // // dp[i][k] := i 番目にとまり k 駅連続で停車する組み合わせ数 // // として計算できる。しかしこれだと O(N*K) なので間に合わない // void solv…

E: 数 - Typical DP Contest | AtCoder static const ll MOD = (int)1e9+7; class e_number { public: void solve(void) { string N; // 10^10000 は大きすぎるので string で取る int D; cin>>D>>N; int n = N.length(); // // * 単純な DP をかんがえると …

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>…

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>…