bitシフトを使うと良いと思います。 メモ化とかDPとか色んな方法があります。 自分はギリギリこの問題を正解して3完(650点)、5300位/10000位くらいでした。 ## 解説 a >> bはaをbだけ右にビットシフト。1001(2) = 9(10) を1だけ右にビットシフトすると100(2) = 4(10) となる。操作としては2で割って切り捨てるのと一緒。 a << bはビットシフトの方向が左。操作としては数を2^b倍するのと同じ。 これは、bitを使った動的計画法?メモ化?です。 dpは、可変配列で1 << N、つまり2^Nの要素数で初期化しています。初期化したときすべての要素はfalseになっています。 dpの添字は、どういう組み合わせで薬品が調合されているか、つまり状態iを表し dpの真偽値は、その状態に到達できるか？を示します。 最初のrep(マクロ使ってるのですこし変わっているがforループと一緒)では、0、つまり空っぽの瓶状態から2^N - 1、 までのすべての組み合わせをためそうとしています。 !dp[mask]は、現在のmaskが到達不可能ならば、それ以降を計算する必要性がないので、スキップしちゃおうという処理です。わりとここがDPの肝でもある。 内側のrepは、まだ調合していない薬品を見つけて、それが調合できるのかどうか？を試しています。 0番目の薬品からN番目の薬品までをforループで回して !((mask >> i) & 1)をしています。これはmaskに対してi番目の薬品がmaskに入っているかどうかを調べるために、 maskのbitをi桁ずらして、AND演算をしています。 たとえばmaskが1011のとき、3番の薬品が使われているかしりたいときは3桁ずらして、10にしちゃいます。そこで1、桁を揃えれば01とANDすると2桁目は無視されるので実質一番右の桁しか見ないことになります。 真偽値は内部的には0と1といったように、これでmaskに含まれているのかを判断します。 mask | (1 << i)ここは 2^i、つまりi桁目だけ1、それ以外0の2進数を生成してmaskとOR演算で結合させて次の薬品混ぜ状態の候補にしています。 それが、S、つまり危険薬品データベースに存在していないならdpの到達可能か？にtrueを代入しているということです。 それを繰り返しています。
