5完4WA
この 4WA があることに大きく響くことに...
各問題
A - Divisible
いわれたとおりやりましょう。
B - Substring
すべての部分文字列を set に入れて、set の要素数が答えです。
最初連続しない部分列の問題を考えていてパニックになってました。
C - Ideal Holidays
実装をわかりやすくするため、0 日目から (A + B - 1) 日目までが一週間と考えます。以下、D は与えられたものを -1 したものとして考えます。
D % (A + B)
を set に入れていきます。これで 0 日目を基準として何日目に予定があるかがわかります。
すべての予定が休日にあるということは、平日に予定がないということなので、各予定間の間が B 日より大きいところがひとつでもあればよいとなります。
あとは set の隣り合う要素の差が B より大きいかどうかを確認すればよいとなります。(先頭と末尾の組をチェックすることを忘れずに)
D - Popcount and XOR
まず C の popcount を求めてこれを c とします。c > (a + b)
, c < abs(a - b)
, c % 2 != (a + b) % 2
のとき構築不可能です。
あとは構築できるので、C の下位の桁から解決していきます。
C に 1 が立っている場合 (0, 1) か (1, 0) です。a, b の余っている方を当てればよいです。
C に 1 が立っていない場合 (0, 0) か (1, 1) です。X, Y それぞれについて ((a + b) - c) / 2
分の popcount が余ることになるので、このあまり分があるうちは (1, 1) として、そうでないときは (0, 0) とすればよいです。
あとはそのビット情報を 10 進に直して終了です。
E - Set Add Query
各番号についていつ S に追加されたかを保存する配列を用意しておきます。(追加されていないときは -1 などを入れておきます)
また、|S| が各クエリを処理した時点でいくつであるかを区間和を取得するセグメントツリーで管理しておきます。
各クエリごとにその配列の x 番目の要素を確認し、-1 ならばクエリの番目を入れ、-1 でなければセグメントツリーから [配列に入っている番目, 現在の番目)
の和を取り出して、x 番目の答えに加算します。
クエリが終わった後に S に含まれている番目(配列に -1 以外が入っている番目)について、セグメントツリーから [配列に入っている番目, Q)
を取り出して加算すれば最終的な答えが得られます。
F - Non-overlapping Squares
重ならないようにどうやって効率よく選べばいいのかわからず...
まとめ
パフォが 1648 以上なら水色復帰だったのですが、4WA のせいで届かず。(1WA までなら届いていた模様)
むねんなりー。