天下一 2017-D問題
天下一プログラミングコンテストの2017-D問題の解説記事です。公式の解説放送はこちら。
与えられた数の中からbit演算ORでK以下になるように選び、選んだ数の価値の総和が最大になるようにします。「bit演算ORでK以下になる」を理解するために小さな数で試してみます。
8, 4, 2, 1はビットが表してる数です。?は0でも1でもどっちでもいい場所です。例えば、K=4の場合、同じ条件の数でbit演算ORをしても4は超えません。ただし、違う条件の数でbit演算をするとKを超える可能性が出てきます。
例えば100と011の場合。100は条件1を満たす数ですが、011は条件2を満たす数です。この二つでbit演算ORをすると111となり、K=4を超えます。K=8の場合も同様です。つまり、「bit演算ORでK以下になる」数は
- K
- 1のあるビットを0に変え、そこから右側はなんでもOK
- ORされる数同士が、同じ条件を満たさなくてはならない
だとわかります。これを確かめるために、もう少し大きな数でも確認します。
一見、この条件で問題なさそうですが、罠があります。K=12で、1001と0011を考えます。1001は条件2を満たす数で、0011は条件3を満たす数です。先ほどの3つの制約だと、この二つのbit演算ORは12以下にならないはずですが、実際は12以下になります。
この矛盾は条件2が間違ってるため起こります。条件2の8のビットが1である必要はありません。つまり、0でもいいのです。これらを踏まえると、正しい条件の表はこうなります。
これで、1であるビットの左右を調べたので結論に進めます。
「bit演算ORでK以下になる」数は
- K
- 1のあるビットを0に変え、そこから右側はなんでもOK。そこから左で1が現れるビットはなんでもOK
- ORされる数同士が、同じ条件を満たさなくてはならない
上の表に書いてあるような条件をループで回し、それぞれの条件に当てはまる数の価値を足していき、最大値をキープすればACします。コードはこんな感じです。
コメントがないコードはこちらで確認できます。3重ループで汚いのですが、計算量はO(32×N×32)でO(N)で求まります。