きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 105:C - Base -2 Number

問題

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 してしまった.

f:id:babcs2035:20180825141656p:plain

gist.github.com

*1:2^16)log(2^16