2023 予選 https://web.archive.org/web/20230909072222/https://radon.u-aizu.ac.jp/pckosien/stats/pck2023pre_standings.html 2022 本選 web.archive.org web.archive.org 2022 予選 web.archive.org 2021 本選 web.archive.org web.archive.org 2021 予…

(個人的には珍しく) まじめに証明を書く． 問題概要 2 人のプレイヤーが交互に，木に対して次の操作を行っていく． 辺を 1 つ削除する． 頂点を 1 つ削除する．その頂点が辺を持つならそれらの辺はすべて削除する． 操作ができなくなった方が負けである． 先…

パスを求める dfs をして v[i] -> u[i] のパスを求めておく．このパス上に含まれる辺の集合を p[i] と置く． 問題の言い換え 以上により，この問題は次のように変換された． N-1 個の白い辺があり，いくつかを黒く塗る．このとき，各 i (1 <= i <= M) につい…

まず思うこと ソートしても題意が変わらないので，ソートします．(頻出中の頻出なので普通やる．) ついでに座標圧縮もしちゃいましょう． これで，問題が次のように変わりました． 爆弾が N 個あり，i 番目の爆弾は座標 i にある．各爆弾のオンオフ状態は s[…

まず，f(r, c) を表形式で図示します．数字が大きすぎて省略されてしまっている部分がありますが，無視してください． f(r, c) を表形式で表したもの ところで，この値は パスカルの三角形 (のちょっと内側) と一致しています．ゆえに，f(r, c) = f(r-1, c) …