ABC303
■A - Similar String
どっちも変換して比較
■B - Discord
適当にやれ
■C - Dash
アイテムは取ると消えるらしい
■D - Shift vs. CapsLock
dp
■E - A Gift From the Stars
次数３だけ先に処理して、辻褄を合わせる
■F - Damage over Time
t,dをうまいことソートすると使う順番と不要なものがわかる。
あとは適当に区間に分けて二分探索でできる
■G - Bags Game
区間dp適当にやるとO(n^3)なので高速化したい。
単純走査は簡単なのでいいとして
oooooから
xx--xとxを取るとすると
Σx-dp[l][r]みたすするがΣxは選んだ区間に依存するので
(Σx+Σ-)-(dp[l][r]+Σ-)とすればセグ木に乗る
■Ex - Constrained Tree Degree
知識問題
次数列がaな木の通り数は？
答え(n-2)!Π1/(a-1)!
