ARC121E 解説: 包除原理と動的計画法を用いた解法
この問題は、「すべての要素が特定の条件を満たさない」ような場合の数え上げ問題であり、直接的に解くか、または「少なくとも1つの要素が条件を満たす」場合に包除原理を適用する方法があります。ここでは後者のアプローチを取ります。
(S(i)) を、「(i) 個の (k) について (a_k) が (k) に到達可能である」という条件を満たす順列の数と定義します。包除原理を使うと、以 ...
10月12日 23:04 投稿
一月の競技プログラミング問題解説
### \[ABC154F\] Many Many Paths
この問題は組み合わせ数を使用します。簡単な問題ですが、詳細な解説は後日行います。
### CF1542D
この問題では動的計画法（DP）を使用します。問題文を変換すると、各操作 \(+x\) に対して、その操作が加算されるためには、それより小さい操作が必要であることがわかります。つまり、操作の具体的な値ではなく、その大小関係に注目 ...
8月5日 01:57 投稿
CF1228E Another Filling the Grid の解法
すべての行に少なくとも 1 つの 1 を配置する必要があるため、行ごとに処理し、その行にいくつかの 1 を追加することを考えます。現在の状態を表すために、dp[i][j] を「最初の i 行を埋めた時点で、1 がすでに存在する列が j 列ある場合の埋め方の総数」と定義します。遷移では、現在の行で新たに 1 を追加する位置の数を k とし、残りの位置には任意の値を入れます。
\[ ...
5月22日 16:27 投稿