■A - Leading 1s
あまり綺麗に解けなかった。
サンプルの120のケースで考える
[1,10):={1}
[10,100):={11},{10,19}
ここまではわかる
桁数がおなじになる[101,121)は
min(199,120) - 100 + 1
min(119,120) - 110 + 1
min(111,120) - 111 + 1;
のようにすればいい。
■B - Ternary Strings
辞書順最小の部分が面倒なので2から始まるものを先に考える
200000
200001
200002
200010
200011
200012
見たく作るのが最大が最小になるのは明らか
今度は、0と1から始まるものを条件を満たすように作る必要があるが
200001->011112->122220のように作ればいい。
■C - Binary Strings
ちょっと間に合わなかったね。
試しに適当に出力してみる
1
10
100
1000
10000
10001
1001
10010
10011
101
1010
10100
10101
1011
10110
10111
11
110
1100
11000
11001
1101
11010
11011
111
1110
11100
11101
1111
11110
11111
みると
{1,15,15}のようにグループになっていて
その中は{1,7,7}->{1,3,3}->{1,1,1}のようにグループになっている
ので上から決めていけばいい。
面倒なのは10***のケースの場合でこの場合はidxを-1する必要がある
が、毎回やっていると間に合わない可能性がある
これは、遅延セグ木にboolを持たせ、区間を反転することができれば実現可能。
解説に見る限り遅延セグ木は不要らしい。
■D - Sum of Min of Xor
結局これってARC112-Dじゃんという。
上からペアになる候補をどんどん決めて聞く
{a,b}がi={0,0},j={0,1}ならai*ajで組ませるなどのようにやっていく。
最後まで決まらなかったものは、どうやっても一緒なので最後に処理をする。
■E - Priority Queue
割と簡単ですねこれ。
集合の要素が最大になるときは小さいものからpushするとき
その集合が{a,b,c}として{x,y,z}がx<=a,y<=b,z<=c
な集合は構築ができる。
これがわかればDPすればいいだけになる。
