6,7 回目は事情があり書けるか不明

セットを開くと 2 問も数え上げがあり嬉しい気持ちになると同時に驚いた。

B を考えると m = 0 のときは元の木しかあり得なく、そこにいくつか頂点を追加していく感じになる。補助的な木を構築していくと k = 0 のときは常に今ある辺の間に入れる or 頂点の下にぶら下げるしか出来ないため簡単。それ以外のときも他の頂点を辺の間に入れて自分をその下にぶら下げる遷移をすればよく、bit DP で O(m 2^k k) で解ける。20 分程で満点が取れた。

A は線の type の包除原理を考える。予め同じタイプの線の重複を除いておく。type 1,2 の交わりは平面走査をして、type 1,3 と 2,3 と 1,2,3 の交わりは type 3 の線分が 5 本までという制約があるので type 1,2 と type 3 の線分の組を全探索出来る。実装で少し手間取ってしまい 1 時間で満点を取った。

C を見る。bfs 木であるという制約は恐らく全ての非木辺が先祖 - 子孫の関係にあることなので包除原理を用いて k <= 6 を取る。パスグラフの場合も同じようなことをすると O(N^2) で解けるが、key 頂点以外を圧縮すると頂点 1 から N を非木辺のパスを用いて覆えた場合のみ条件を満たさないという形になるので遅延セグ木を用いて dp をすればよい。(普通のセグ木だけでも包除原理を考えると行けるらしい)

一般の場合は子の方から部分木の補助的な木の状態を持ちながら dp をすれば行ける気がしたが、上手くできず 1 点も取れなかった。

100-100-52 = 252 で初めの 2 時間半で 252 点を取りそれ以降は C の一般で椅子を温めてしまった...

かなり好成績だが、B と C の 52 までは体感簡単めだったので消化不良...(B でかなり上振れを引いた気はしている)