hotpepsiの練習帳

SRM 709

00:36

Div1 Easy (250) Xscoregame

問題

• 配列Aが与えられる
• Aの各要素Yを任意の順番で選ぶ
• Xの初期値を0としてX=(X+(X XOR Y))を計算する
• Xの最大値を求める

方針

• 何となく大きい順のほうが良さそう
• next_permutationで全部試すのは無理
• 適当に2分割してお茶を濁す
• Challenge Succeeded
• (終了後)
• 下位6ビットの結果が重要なので、そこだけ見てbit DP
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_709/Xscoregame.cpp

結果

x-- +3 150pt 102nd/339 rating 1637 -> 1683 (+46)

違いが出る部分だけでDPするのはなるほどという感じ。

https://togetter.com/li/1083628