KUPC 2019

　オンラインから参加しました。

A問題

　ソートして最大-Xの要素を数える。

B問題

　200点問題なので簡単ですね（）。まずUnionFindして次に根以外は根に重み、価値を付加して自信の重み、価値を0にする。最後に普通のナップサック。

C問題

　今回一番面白かった問題。とりあえず1gのやついっぱい欲しい！と思ったので1gをk個は確定。これでkgまでは測れる。次に2k+1gが欲しい（1gをk個反対側に置けばk+1~測れるので）！となるので2k+1gを用意する。いっぱいあった方がお得感あるのでまたk個用意する。これでk(2k+2)gまでは測れる。・・・、とやっていくと答えが出る。2倍とかkの累乗とかが出てくるので（語彙力不足）時間が足りる。

D問題

　とりあえず0が連続している部分と1が連続している部分に分けて考えればいいことがわかる（0と1の境目のところで両者の持っている枚数が等しくなる必要があるので）。次に分け方を例えば1~6をAが勝つように分配するならBBBAAAとかBABBAAとか、Aの数が途中でBを超えない並べ方を数え上げればいいことがわかる（かっこの並べ方みたいに）。ここでよく考えるとカタラン数、という言葉がふと頭の中に浮かび上がったのでググるとまさにこれだということがわかる。OEISより天啓の方が早くて楽なのでオススメですよ。modの逆元めんどくさいけど10^5は流石に埋め込めないのでちゃんと計算する。

　E問題結構考えたけどわからなかったので撤退し4完。順位表見た感じまあまあいい結果（その後のこどふぉ爆死したけど）。