Dが解けそう見えたけど解けませんでした
Cはざっくりとした方針は立っていましたが
実装が大変そうなのと、正当性に確信が持てず。
■A - Remove One Character
X??????XのXを削除すると
??????XとX??????になるわけでこれらが一致するためには
XXXXXXXXじゃないと駄目だよねというお話。
なので尺取法などで同じ文字列が連続する範囲を調べ上げる
■B - Colorful Lines
典型的な逆から考える問題。
必要な情報を管理することと、不要な処理は行わないこと。
■C - Digit Sum Minimization
5+8=13のように繰り上がりが発生すると
桁和は5+8-9になる。
繰り上がりはできるだけ数多く発生したほうがありがたい。
そのためには、一番下で10以上を作って
それより上で9以上を作っていけばいい。
実装が少し面倒。
上位者の実装を覗き見してラムダ式の賢い使い方を学ぶ。
[=, &x, &y, &z]()mutable {
}();
このようにすれば、x,y,zは変更可能で、
それ以外の変数はラムダ式の中で使うならコピーが走るらしい。
ふーん。
■D - Zigzag Tree
解けると思ったんだよなぁ。。
まあ適当にマージすればいいんですよ
rootがv、rootの子供要素をa,bとして
vとaをマージし、さらにbをマージする。
２乗の木DP
dp[v][i]:=今のvの要素(マージされたものも含む)のうちi番目の要素が頂点に書き込まれている場合の数
として
dpのマージの方法は
a0.......an-1
b0.....bm-1
と合計n+m要素があったとし
マージ後のdp[v][i]は
aのi番目をa+bのj番目になるとし、頂点要素を満たすようにしたければ
[0,i+j)と[i+j+1,n+m)をそれぞれ[a0,ai)[b0,bj)と[ai+1,an)[bj,bn)に振り分けて
さらにbとaのrootの大小関係が正しいもののみ考えればいいので
累積和を使ってうまいことすればいい
