SRM 709 DIV1 Easy: Xscoregame

|A|<=15で順列で最小とあり、ビットDPっぽい。しかし、

X+(X^Y) の後半xorパートが怪しい。

の値が大きければ良いというわけでもない。

そこでA[i]<=50に注目する。A[i]<=50<64=2^6である。つまりA[i]の下位6ビット以外はすべて0。それに対してXの値は当然1であったほうが良い。つまり、下位6ビット以外に関しては、大きければ大きい方がいい。よって普通にXの最大値がわかれば十分。他方、下位6ビットに関してはYとのxorで影響を受けるので、ありうるすべての値について最大値を計算する。したがって以下のようなDPを計算する。

dp[used][lower_bits]

:= Aのうち使用したものがused、下位6ビットがlower_bitsであるときのXの最大値

WA

dp[used]:=Xの最大値

をやらかした。

証明しようと試みなかったし、直感的に正しいわけでもないのに、あまり考えずに提出してしまった。

これがExamplesで落ちないのは厳しい。

思いつき方

ビットDPっぽい。

A[i]<=50

=> 下位6ビットを見る