気付いたらABCがRatedになってた......
ここしばらくRatedで出てなかったのは土曜夜に働かなければならない状態だったからです
結果
oooooo(1)- 60:28 157位
Perf: 2245
1922→1958 (+36)
A
https://atcoder.jp/contests/abc438/submissions/71993982
算数の自信がなかったので $D$ を超えるまで $F$ に7を足し続けた
B
https://atcoder.jp/contests/abc438/submissions/71996609
C
https://atcoder.jp/contests/abc438/submissions/72001266
最初3個で消えると勘違いして大変だった 左から順に見て末尾を消せるタイミングで4個消せばよい
D
https://atcoder.jp/contests/abc438/submissions/72004822
今採用しているのがA/B/CでDP
E
https://atcoder.jp/contests/abc438/submissions/72013439
周期でやりたくなかったのでダブリング
F
https://atcoder.jp/contests/abc438/submissions/72030772
パス上のMEXを加算→MEXが $k$ 以上のパスの個数を数えてその総和を取る。
- MEXが1以上のパスは0を通るパスの個数、つまり $N(N+1)/2$ から0を通らない(=0の子の部分木内で完結するもの)を引く。
- MEXが2以上のパスは0と1を通るパスの個数で、これも(1の子の部分木)×(0の子の部分木のうち、1を含む部分木を除いたもの) で出せる。
- MEXが $k$ 以上 $(k \ge 3)$ のものについては、0から
までを全て含むパスが存在するかを判定し、存在するなら両端点の部分木の個数からパスの総数が求められる。存在判定はLCAを使えば可能。
$N$ をint型で受け取っているのにもかかわらず $N(N+1)/2$ の計算を実行してオーバーフローで1ペナ
G
見ただけ 周期性でどうこうする感じか？そうでもない
感想
直近だと436のGが簡単なわりにDiff高いのでその回に出たかったですね
