AtCoder Beginner Contest 105:C - Base -2 Number
問題
整数 N を -2 進数に変換した結果を求める問題.
解法
2^(2k) (0 <= k <= 16) の位は +,2^(2k+1) の位は - になるので,それぞれ独立して考える(bit を1こ飛ばし).前者と後者で考えられる 10 進数表記を全列挙し,足して N になる組み合わせを探す.全体で計算量は O*1 になり間に合う.
想定解では,bit の下の桁から 2^k で割った余りに応じて決めていくという方法を取っていた.こちらの方が O(logN) になり効率がいい解き方だった.
解答
Submission #3067141 - AtCoder Beginner Contest 105
1 WA してしまった.
*1:2^16)log(2^16