CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) Dまで四完。
A 最小と最大を取る
B 全然分からず実験して気付いた。二回やると打ち消すので、二数の差が作れる
C 1→0にできない。連続する二数は両方1にできない。
D 奇数なら2、2ベキはダメ。x*2^nならxか2^(n+1)を試す。

— titia (@titia_til) March 24, 2022

E. Equal Tree Sums

　解法ツイートを見てAC。コンテスト中は最初にに頂点が決まると他が埋まるな～という方針しか考えていませんでした。そこから方針転換するのは難しい。

　頂点に書かれた整数の総和をSとする。ある頂点に書かれた整数をx、その頂点から出ている辺の本数をyとすると、S-xはyで割り切れなくてはいけない。特に、Sが0だとバランスが良くて上手くいきそうなので、試してみると上手くいく。

　つまり、木を二部グラフにして、片方に(その頂点から出ている辺の本数)を、片方に-(その頂点から出ている辺の本数)を割り当てれば良い。