AtCoder Beginner Contest 246

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 246 Fまで六完。
B 三平方の定理
C ソートして大きい方からa/X枚クーポンを使う。その後、余りをソートして大きい方からクーポンを使う
D aを全探索し、bを二分探索
E BFS。ちゃんと枝狩りする
F 包除原理

— titia (@titia_til) April 2, 2022

G - Game on Tree 3

　自力でAC。

　答で二分探索して判定問題にするのはこういう問題の定石。その後、どうやら葉から木DPしていけば良いと分かる。

　……が、その後を詰められなかった。

　「答えがx以上になるか？」という判定問題を考えるとき、例えば、根から整数x以上が書かれたノード2つと繋がっていればOK（答えはx以上）となる。

　根から1つだけ辺が出て、その頂点から整数x以上が書かれたノード3つと繋がっていればOK。

　そういう感じで考えると、頂点pに対して、

・DP[p]=1 if 頂点pに書かれた整数がx以上

　としておき、さらに、

・DP[p]+=DP[pの子達]の和 - 1

　とした感じになる。

　が、それだけではダメ（ここまではコンテスト中に考えられていた）で、

・「頂点pに書かれた整数がx以上」のとき、「DP[p]は少なくとも1になる」

　と気付くことが重要。

　式の説明・証明をしようと思えばできるんだけど、その説明を得るためにも実験しなくちゃいけなさそうなので、ギリギリの場合などを色々試して調べるしかなさそう。