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

はじめに ABC164Eで拡張ダイクストラが出題され、解けなかった。 拡張ダイクストラを実装するときに迷わないように手続きをまとめておく。 拡張ダイクストラとは ・頂点を増やしてダイクストラをすること。 僕のダイクストラ実装 //************************…

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

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