D - 1D Coulomb メモ 以後以下のように言葉を定義する S[i] := iの電荷(+か-) R(s) := sと逆の電荷, R(+) == -, R(-) == + cnt(i, s) := [0, i)にある符号sの数(つまりiより左にあるsの個数) まず各iがどちらに動くかを考える iが+の場合、i以外の合計は-1に…

G - Ban Permutation メモ 制約的に箱根駅伝dpを考える from(1~N)からto(1~N)の全単射について、fromからtoへ辺を貼っていく問題だと考えると 箱根dpの性質から、まだ行き先が決まってないfromと元が決まっていないtoの数が一致する。この決まってない数をn…

F - Figures メモ プリュファーコード問題 //下の式は(N-2 )!を掛けるのを忘れている //上の式は(N-2 )!を掛けるのを忘れている プリューファーコードより、各次数(ei)が決まっているときの木の場合の数は (N-2!) / *1というような形になる 上の式は、それに…

F - Anti-DDoS メモ 以下ではDDoS文字を数える まず判定問題を考えて問題を簡潔にしたい。 これは排反に数え上げる上でも役立つ。 ある文字列にDDoS文字が含まれていても、その文字列を複数回数えないようにしたい。 こういうものはよく、最初に現れる何かの…

C - YY Square メモ グリッド上を通った経路について、スコアがあるものの^2で定まる時 そのスコアの合計を求めろという問題 スコアの計算がそのままでは複雑で、dpで漸化的に扱いにくい。 合計の合計という形にできれば、寄与について考えられる 解法1 n^2 …

Ex - Constrained Tree Degree メモ プリューファー列について調べた するとSi-1をN回組み合わせてN-2を作る問題になり、 出現回数について重複を除くようにすると 指数型母関数で解ける

D - Mahjong メモ 以下の二つの操作を使って作れる、長さNで総和がMの数列Aは何通りあるか ・長さKの区間に1を足す ・あるAiの値をK足す この問題の難しさは、異なる操作によって同じ数列が作られる事があるという点にある これは、数えあげpdfのgreedyから…

D - Sum of SCC メモ トーナメントグラフを強連結成分分解して得られる縮約グラフはパスである。 それが本質だった。 また、強連結成分の数え上げに苦戦した。 こういう良く分からないものの数え上げは、何か別のものの数え上げに言い換えられればいいが、今…

G - Increasing K Times メモ 問題の形からT - Permutationを連想し dp[i][k] := i個置いたときに、前回置いた数よりも大きい数が何個残っているか として遷移しようとしたがうまくいかなかった。 O(N^3)になってしまった permutationの場合は、各iについて…

概要 包除原理と期待値の線形性（誤用かも）で解きました 既存の解説はメビウス変換が多かったので自分の解法を書いておきます。 問題 N個の整数S1...Snが与えられ、それらの整数をランダムにいくつか選ぶ。ここで(1<=i<=n)なるiで各Siが選ばれる確率はPi/10…

E - 和風いろはちゃん / Iroha and Haiku余事象を考えるとわかりやすい 桁毎に全探索するメモ化で解く ある桁iで使える数vは、iを右端としたときに575とならないようなvだが これは右端から数の累積和を取ってbitに持たせれば575になるか判定できる 18以上の…