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 をかんがえると …