ABC240 参加記録

コンテスト中AC:A〜E

E - Ranges on Tree

コンテスト中は確信が持てないまま通してしまいました。
解法に至った経緯をメモしておきます。

まず、問題文の意味がパッと見で理解できませんでした。そこで、入出力例を確認して、ざっくりと以下のような制約であると理解しました。

• 親の区間を、子に分配する。この時、子の区間は親の区間をはみ出してはならず、かつ、子同士の区間が重なってはならない。

ここまでで解法は思いつかなかったので、問題の例を全て確認してみました。すると、以下がわかりました。

• 根の区間は、葉の個数をとして、
• 葉の区間は、ある正整数をとって、であり、は葉同士で相異なる

ことがわかりました。
そこで、葉にそれぞれまで割り振って、その葉の区間をとし、その後、親に向かうにつれて区間を併合していく解法を思いつきACできました。

公式解説によれば、この解法の正当性として、

• 葉には必ず異なる番号(区間)を振らなければならないので、k個の異なる整数が必要であり、答えはk以上になる。一方、先に示した方法なら、答えをkにできる。よって、この方法で得られる解は最小であり、解法の正当性が示された。

という感じでした。

提出コード