maspy

概要 問題文 → ■公式解説 → なさそう？自分の提出 → ■ 解法 $a_i, b_i$ の上限を $K$ とします（$K = 300$）。$1$ が $n$ 個ある状態を、「状態 $n$」と呼ぶことにします。 ...

概要 問題文 → ■公式解説 → なさそう？自分の提出 → ■ 問題文中の $E$ の数式 ${W\times H}$ は $1$ 元集合なので、何か変なお気持ち記法になっているように思います。適当に正しくしておきます...

概要 問題文 → ■公式解説 → なさそう？自分の提出 → ■ 解法 バスターの角度を固定したとき、いくつのマラカスを撃ち抜けるかを計算したいです。実際に計算しやすいのは逆で、マスカラを固定したとき、どのようなバスター...

概要 問題文 → ■公式解説 → なさそう？自分の提出 → ■ 「DAG でスタートからゴールまで移動。必要な移動回数の期待値は？」という典型パターン。 解法 とりあえず、「振り出しに戻る」を無視します。「振り出しに戻...

概要 問題文 → ■公式解説 → なさそう？自分の提出 → ■ 基礎的な問題。 解法 集合 $S\subset {1,2,\ldots,n}$ に対して、頂点集合が $S$ と一致する二分木の個数を $\text{dp...

概要 問題文 → ■公式解説 → なさそう？自分の提出 → ■ シンプルなボス問。大体何をやればよいかはすぐに分かると思いますが、重複や漏れがなく実装しやすい形で計算できるかが問われていますね。 解法 出来上がる絵の連...

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 解法 基本的なところは解説スライドがあるので省略します。 この問題は、 状態ごとの数え上げを表すベクトル $v$遷移を表す疎行列 $A$ を用い...

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 解法 $N$ を定数とします。次のように $\dp(x), \DP(x)$ を定義します。 $x$ から始めて $N$ を作る方法の数え上げ：$\DP(x)...

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 解法 直前 $1$ 行分の情報を持つタイプの DP により解けます（アリ本 p.179）。 あるところまで埋めた時点での 直前 $1$ 行分について、...

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 解法 $d_i, g_i$ のことを、この解説では $a_i, b_i$ と書いていきます（輸送コスト $a_i$・生産コスト $b_i$）。 基本方針 ...