AtCoder Regular Contest 127

　AB二完でレートを落とす。

　コンテスト終盤、Eのサンプルが合い、舞い上がって提出したときREが二個返ってきて、焦りに焦ってしまった（指が震え、汗がたくさん）。そのせいで結局通せず。

　こういう時間ギリギリのやつは、最終的にはACできていたことが多いのに、今回は失敗してしまった。まあ、最初二問で時間かかってしまったのもまずいんだけど……。

コンテストへのリンク

コンテスト後のツイート

C - Binary Strings

　解説AC。

　大体、Xが全体の半分以上か以下かで、最初の文字が分かりそうだなー、とは思う。

　その解法であっているのだけど、詰めるのはなかなか大変。

　特に、Xが2進法で与えられるということを活用する部分は難しい。

　実装にも苦労した。

　解説通りに実装したつもりだったが、X=0になったかどうかの判定の仕方が分からず困ってしまった。

　立っているbitの個数を持つという方法に気付きどうにかAC。

D - Sum of Min of Xor

　解説AC。

　なかなか解説が理解できず苦労したが分かってしまえば単純だった。

　xorの問題だし、制約を見ても、桁ごとに考えるのが良さそう。

　最上位の桁について、ABそれぞれのbitが立っている/立っていないの四通りで場合分けできる。それを00、01、10、11の四つで表すことにする。たとえば、Aでビットが立っていて、Bで立っていない場合10で表す。

　この四通りの、何と何でxorを取るかで場合分けして考える。

　この桁で決着がつかないのは、00^00、00^11、11^11、01^01、01^10、10^10のとき。このときは、一つ下の桁を見る再帰を使いたい。このままだと再帰できないようだが、公式解説のように、S=00+11、T=01+10とすると、S内、T内で再帰することができる。

　それ以外、この桁で決着がついた場合は、一番下の桁からこの桁まで、それぞれの桁についてbitが立っているものの個数を調べておけばよい。

　たとえば、01^11ならAの方がBより小さいので、（01のもののうちk桁でAのbitが立っているものの個数）*（01のもののうちk桁でAのbitが立っていないものの個数）+（01のもののうちk桁でAのbitが立っていないものの個数）*（01のもののうちk桁でAのbitが立っているものの個数）に1<<kをかけたもののを加えれば良い。

　個人的には、この、「ある桁で決着がついた場合の処理」では全部の桁を見るというのが分かりづらかった。確かに、そうしても計算量は間に合うのだけど、他では再帰で一桁ずつ見ていくのにこっちでは下の全桁を見て処理するというのは分かりにくい気がする。