physics0523's 精進ログ

主に競プロの面白い問題の解法をメモします

2023-10-01から1ヶ月間の記事一覧

Two Fairs(CFR606-D1B)

Problem - B - Codeforces $N$ 頂点 $ M $ 辺の連結な無向グラフ $G$ が与えられる。 更に、 $1 \le A,B \le N$ かつ $A \neq B$ を満たす整数 $A,B$ も与えられる。 以下の条件を満たす頂点組 $(U,V)$ を数えよ。 $U \neq A$ かつ $U \neq B$ $V \neq A$ か…

整数値を取り $f(k) \le n/k$ のように制約され単調減少する $f$ に対して、普通にひとつ計算すると $O(g(n))$ かかるところを $f(1),f(2),\dots,f(n)$ をまとめて $O(g(n) \sqrt{n} \log{n})$ で計算するテク

Problem - D - Codeforces (CFR507-D1D) に使いました 以下の条件を満たす $f$ を取り扱います。 $f$ は整数値を取る $f(k) \le N/k$ のように制約される ( $n$ 個のものをどうにかして $k$ 個ずつ個包装したい場合など… ) $f$ は(広義)単調減少する $f$ を…