AtCoder Grand Contest 045

※1問も解けていないので、解説的なものを期待しているなら、以下は全く読む価値ないです。
　どのようなことを考えてハマっていたかだけが書かれています。

コンテスト前のレート：1818
レート通りのパフォーマンスが得られる順位：427位

A - Xor Battle

問題
思いついた案は制約に収まらなそうなものばかりで何もできず。
20分ほどかけて解けなかったのでスキップ。

思考過程

1. ビットごとに見た場合、最後に当該ビットがになるのが、のよりも、のの方が後ろである場合はにできる。
2. ただ、ビットごとに独立ではないので、他のビットに引きずられるところをどう判定すれば？　→わからない
3. 後ろからのだけ見ていって作れる数の集合と、前からのだけ見ていって作れる数の集合を比較して、常にならばと判定できそう。　→集合に含まれる個数が最悪くらいになると思い、ボツとする

上記のと解説のが概ね同じものに見えるけど、何で計算量が問題ないのかは全然わからない。

B - 01 Unbalanced

問題
A問題をスキップした後の2時間をほとんどこれに費やしたが解けず。

思考過程

1. 最初から最後までとを交互に配置するのが最善で、その時の答えは。
2. 例３を見ると、後ろの方の"11?111"の部分が最悪でとなる模様。
3. 例３では、前半のが多いところはを主ににして、後半は逆になりそうだが、前半ににし過ぎたら後でが足りなくなるなんてこともありそうで、貪欲で簡単には決まらない気がする。
4. 答え決め打ち二分探索をして、特定値を超えないように操作できるかどうか判定することはできるか？　→答えを決め打たないよりはまだできる見込みありそう
5. だと、だと（ただし最小値は）するカウンターと逆のカウンターを用意し、それぞれの最大値を見たりしてみるが、で両方減らしてるのはさすがにおかしくてケースしか通らない。
6. を全部した場合と全部した場合を両方持ったりしてみるが、結局それをどう扱うのがいいのかよくわからない。根本的に考えを変えていくことにする。
7. を、をとみなして、で区切って以外の累積和を取ってみる。　例３だと、となる。間のの数もわかるようにしておく。
8. この数列を、を超える値が出ないように間ので調整していけないか？

ここまでで時間切れ。解説見ると最後の方針はかすってはいそうな気がする。
を一旦全部にしておいて、可能な限りに変えていくとか全然思いつかなかった。
　

C問題も一応少し考えたけど、文章化できるほどの思考過程がないので省略。

最終結果：0完、458位、パフォーマンス1337
レート変動：1818→1778

当時緑だった、2019/3/23のAGC032以来の0完でした。