yukicoder contest 334

　A一完で終了。

コンテストへのリンク

No.1861 Required Number

　部分和問題なので（bitsetを使うかはともかく）DPするしかない。

　だが、必ず使う数の判定はどうしよう？　その数字を除いたDPをN回すれば求められるけど……で止まってしまった。

　方針は合っていて、「DPをN回やる」という部分の高速化を考えなくてはいけなかった。左右からDPをすれば、判定は一回O(K)でできるので間に合う。

　左右からDPを思いつかなかったのは良くない。

No.1863 Xor Sum 2...?

　一応自力AC。

　コンテスト中、Bが1になる区間で条件を満たすことはないと分かり、Aたちの和とXORが等しくなるとき（つまり、繰り上がりがないとき）は、尺取り法で調べることができる、というところまでは気付いた。

　あとは、その区間の中で、$B_i$が1になるものが奇数個ある区間の個数を求めるところ。

　これは累積和を使えばいけるのですね。

　Bの累積xorの変化を見てみると、その変化の仕方は二通りしかない。ので、二通り累積和を持っておけばいける。

No.1865 Make Cycle

　解説AC。

　二分探索するだけの問題なのに思い付けなかったのはまずい。