基礎的な数え上げの範疇です。 部分集合の数を数え上げたい 要素がK個（以下サイズがKという）の集合Sの部分集合の数は、 である（空集合を含む）。これはそれぞれの要素について、その要素が部分集合に入るか？入らないか？の2 通りあり、その選び方は他の…

どういうことか 問題 整数列a = { } が与えられる。a[i] = a[j] ( i < j ) となるような(i, j) の組の数を求めてください。 (i, j) の組を全探索すると当然求められるが、 でTLEしてしまう。 そこで、片方を固定することを考えてみる。j を固定して、i < j …

期待値の問題を解きたかったので 問題のリンク E - デフレゲーム 考察 とりあえず小さいn で実験。 ・n = 2 サンプル1 通り、0.25 * 1 + 0.25 * 2 + 0.5 * 3 = 2.25。 ここで、3を1+2 と見て、(0.25 + 0.5) * 1 + (0.25 + 0.5) * 2 = 2.25 と見る。これは、 …

声に出して読みたい問題名、他にはMatch Matching 問題のリンク E - Meaningful Mean 考察 半開区間[l, r) の部分列{ } の要素の算術平均は、累積和（ ）を用いて、 と表せるので、問題の条件は、次のように言い換えられる。 簡単な変形によって、この式は …

久しぶりにこどふぉしました。それもこれもDeepLの翻訳のおかげです。 問題のリンク Problem - D - Codeforces 問題の概要 ・数列a が与えられる。以下の操作を繰り返して数列の全ての要素をk にできるか？ （操作） 数列aから連続した部分列Sを選択し、Sの…

方針ガチャ、成功！ 問題のリンク E - Colorful Blocks コンテスト中の思考過程 DP？ ・dp[i][j] := 前からi 個目のブロックまで見て、今まで同色で塗られた隣り合うブロックの組がj 個ある場合のブロックの並べ方の数。 ・これはO(NK) でTLE。この方針で高…

はじめに ありがとう、ミカミくん 問題のリンク D - Teleporter コンテスト中の思考過程 ・これは最近見たことある！延々と辞書を引かされ続けるミカミくんだ！！ D - へんてこ辞書 ・ありがとう、ミカミくん 解法１ : ループを見つけて周期性を利用する ・…

問題のリンク 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であると言える。 ・…

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