コンテスト後のツイート
D maxと小さいものを対戦させていく。残りがm*2になったら順番にやる。しばらく部分和問題とか考えて迷走。
— titia (@titia_til) December 27, 2025
E 同じ和の二つに分けると、短い方に答えがある。Flatten操作でmaximalにしか操作しないことを見逃していたせいでずっと解けなかった。
F. Conquer or of Forest
コンテスト中に考えていた方針でAC。
まず、白いnodeと親nodeを切る。
そして、それらを一列に並べれば条件を満たす。（どのnodeからどのnodeへ繋いでもOK）
結構人工的な条件なので、そこから何かを考えようとするのではなく、それっぽい必要条件を探すのが大事だった。
一列に並べた結果、問題文の条件を満たす証明は分からないけど、それっぽくはなっている。
コンテスト終盤にこの条件では？ と思ったが、数え上げが間に合わなかった。
・ROOT以外の連結成分について、どの頂点を親と結ぶか
・葉以外の連結成分について、どの頂点を親にするか
・ROOTと葉以外の連結成分について並び替え
を掛け合わせればOK。
三番目がよく分からず時間切れ。
（連結成分数）！みたいなのがいるとは思ったのだが、（連結成分数-2）!だったとは。落ち着けばできたと思うけれど、この条件自体が正しいという確証もないこともあり落ち着けなかった。
0 件のコメント:
コメントを投稿