こちらの問題を、ネットの情報を参考にしながら解いた。
ビット集合で区間DPのようなことをできるという発想が面白いし、何よりもビット集合Sの部分集合Tをfor (int T = S; T >= 0; T = (T - 1) & S) { ... }で重複なく不足なく列挙できるとは思わなかった。しかも、この列挙の仕方により計算量が改善され、普通の方法なら4Nとなるところを3Nに抑えられる。
確かに列挙の回数を数えてみると20億から4000万に減っている。ただ、20億のほうのコードを提出するとACしてしまった。条件式が(~S) & Tのようにビット演算だけから構成されているから速いのかな。とはいえ、まさか109が通るとは思わなかった。
EDPCは残り5問。どれも一筋縄ではいかなそう。T問題は諦めて答えを見たけど、それでもよくわかっていない。明日また考える。
