問題のリンク I - Coins 思考過程 ・N枚全てのコインを振って、表がx 枚となる確率P(x) を0 <= x <= N について求めたらよい。 ・独立な試行とDPは非常に相性が良い。 DP table というわけでDP。 ・dp[i][j] := i枚目までのコインを振って、表がj 枚出るとい…

解いた問題を忘れているので思い出そうキャンペーン 問題のリンク E - Payment 思考過程 ・めっちゃ桁DPしたい制約。 ・とりあえず、Nの桁数より2桁多い金額を支払うのは無駄。 ・桁ごとに払う金額と紙幣の枚数を決めていきたい。繰り下がりを考えないといけ…

問題のリンク Q - Flowers 思考過程 ・LIS（最長増加部分列）問題の拡張版。重み付きLIS。 ・いわゆるインラインDPというやつ。DP table を1次元にして、セグ木にのせる。 ・セグ木版LISを重み付きで行う。逆に、LISは全重みが1のFlowersであると言える。 ・…

EDPC ・順次追加していくよ A Frog 1 B Frog 2 C Vacation D Knapsack 1 E Knapsack 2 F LCS G Longest Path H Grid 1 I Coins J Sushi K Stones L Deque M Candies N Slimes O Matching P Independent Set Q Flowers R Walk S Digit Sum T Permutation U Gr…

僕はAGC好きですよ、じっくり問題が解けるので 問題のリンク D - We Like AGC 思考過程 ・禁止されたパターンがあるタイプの数えあげDP。EDPCのC。 ・禁止された状態は以下の5つ。（Xはワイルドカード） 1. AGC 2. ACG 3. CAG 4. AGXC 5. AXGC ・前の3つまで…