AtCoder Beginner Contest 236

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 236 Fまで六完。Dで失敗した割には頑張ったか。
C set
D DFS。そう思ったのに、なぜかメモ化再帰みたいなことを書いてペナ重ねた。
E 平均値・中央値は二分探索。平均値は目標の数字を引いてDPして判定。
F xor基底
G 分からず。
H 包除原理な気がしたが……。

— titia (@titia_til) January 23, 2022

G - Good Vertices

　解説放送を見てAC。

　まず「頂点の移動を隣接行列で表そう」とすら全く考えなかった。難しいのはその後なのに……。

　その後のパートが難しいのだけど、行列累乗しようという気持ちになっていないためその難しさがよく分からず。

Ex - Distinct Multiples

　解説放送を見てAC。

　辺に関して包除原理を行う→$3^N$のDPに帰着という流れ。

　難しいが、各ステップは滅茶苦茶難しいわけではないので、素早く解く人がいるのも分かる。

　$3^N$のDPの実装に戸惑ったのは反省。

　同じものをダブルカウントしないため、「ある頂点を含むものだけ考える」などしなくてはいけない。（自分は、$p<p$ xor $i$と、「一方がそれを除いたものより小さい」と書いた）

　書いたことがあったのにここで戸惑ったのは反省。