技術室奥プログラミングコンテスト#6 Day1E - And Xor Or

再帰がハマってキレイに書ける問題は楽しいです。

Rustはスライスで自然に範囲を狭めていくような再帰が書けるのが嬉しいですね。

解法

AND,XOR,ORはそれぞれ&, ^, |で書くことにする。

数式のAND,XOR,ORの部分がなんか怪しいので、とりあえずを当てはめて真理値表を作ってみる。
すると、実はこれが ^ に等しいということがわかる。

足し算の部分は上手いこと変換できそうにないので、この式をもとに最大化の方針を考える。
定石として、こういうのはビットごとに考えると良く、また上位ビットほど結果に与える影響は強いから、上のビットをいい感じにしたい。

ともに1ビットしかないとして結果を観察すると、

^
^
^
^

となっている。まとめれば、の組み合わせのときは得だが、それ以外のときは得も損もしない。
さらに言えば、以外では、ビットがなのかなのかを無視してよい。

したがって、以下のような方針で解ける。

1. の最大値のMSBを調べる。これと同じビットが立っている要素の集合をとする。
2. の要素数が2以上の場合は、の間で組み合わせるのが最適なので、MSBをクリアしてとして同じ問題を解く。
3. そうでない場合は、MSBは結果に影響を及ぼさないので、クリアしたうえで再帰的にについて問題を解く。

計算量について考察すると、各ビットの検査は最大値を求めて要素を抜き出すだけなのでで完了できることがわかり、再帰はの最大要素のビット数に左右されるので、結果的にはとなる。

実装例は以下。
Submission #50103292 - 技術室奥プログラミングコンテスト#6 Day1

ちなみに、無駄にもう1つlogを付けてよければ、以下のようにもう少しスッキリした実装にもできる。 そして、なぜかこっちのほうが速いorz
Submission #50101708 - 技術室奥プログラミングコンテスト#6 Day1

Fastestにあと1msecと迫る速さだし、単純なルーチンなので非再帰化してみようと思って手を出したのが以下。
Submission #50101811 - 技術室奥プログラミングコンテスト#6 Day1

あと1msecがなかなか縮まらない…