分割数で鮮やかに解ける！ 問題へのリンク 問題概要 人のクラスで総額 円を集めることにした。 このクラスの生徒は皆見栄っ張りであり、出席番号順が１つ前の生徒に比べて 円以上高い金額を寄付しないと気が済まない。 この条件を満たす方法の個数を 1000000…

木上で bit DP する感じ 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。各頂点 には重み が付されている。 この根付き木はタスクの依存関係を表している。各頂点に対して、対応するタスクの「実行」と「削除」ができる。 頂点 のタスクを実行する…

分割数のいい感じの問題！ 問題へのリンク 問題概要 長さ の数列 killA, killB が与えられる。この 2 つの広義単調減少である。 次の条件を満たす長さ の数列 deathA, deathB の組の個数を 1000000007 で割ったあまりを求めよ。 killA の総和 = deathB の総…

重心分解！ 問題へのリンク 問題概要 (インタラクティブ) 頂点の木が与えられる。なお、この木はどの頂点の次数も 以下であることが保証されている。 A さんは、この木のいずれかの頂点 を考えている。その頂点 を当てるゲームを行う。 あなたは最大 14 回の…

2-SAT は強連結成分分解の典型的な応用例！ 問題へのリンク 問題概要 旗 を数直線上に設置したい。旗 は、座標 または座標 に設置可能である。 ただし、どの 2 つの旗も、その距離が 以上となるようにする必要がある。 本の旗を設置することが可能かどうかを…