水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

Tenka1 Programmer Contest:D - IntegerotS

問題

atcoder.jp

解法

K を2進数表記したとき,「0 ~ 2^(k - 1) の位が 1,2^k の位が 0,2^(k + 1) ~ 2^30 の位は K のそれぞれの位と同じ」数を考える.この数を OR で超えない中で整数を出来るだけ選べばよいので,各 k についてそれぞれの数の中の価値の総和の最大値が求まるので,それらの最大値の中の最大値を答えにすればよい.O(N * (logK)^2).

解答

atcoder.jp

f:id:babcs2035:20181227174746p:plain