naoya_t@hatenablog

いわゆるチラシノウラであります

〈AGC埋め〉AGC 009 B - Tournament (800)

AGCのB問題で1つだけ食べ残していた問題。(多分800点だったせい)
木DP。

  • 葉=0
  • 子供の値のリストを得たら一番大きいやつ+1

→WA(1) 14'
いや例えば

10
1
1
1
1
1
1
1
1
1

とか(全員1に負ける例)考えたらそれじゃ駄目だ
子供全員と対戦するってことは、出来れば後(上)のほうで大きなsubtreeと戦いたい。
子供の値のリストを降順リストして、先頭から順に+1,+2,+3,...していった値の中の最大を上に渡す感じでどうだ
→AC 21'+1penalty
https://atcoder.jp/contests/agc009/submissions/3928495
1WA出したけど自力で20分ちょいで解けたのは嬉しい。

解説読んだ

やってることは同じだと思う(英語版解説と同じことしてる感ある)