ABC105 - C

C - Base -2 Number

問題ページ

なんかこれむずかったので自分の解法を書いとく

基本的には正の数と負の数で分けて全列挙

A : {1, 4, 16, 64, 256, ...}
B : {-2, -8, -32, -128, -512, ...}

みたいな集合に対してビット全探索で部分集合の和を全列挙する (N は 32bit に収まるのでだいたい 2¹⁶ くらいのオーダーで済む)

全列挙した結果をそれぞれ SA, SB とすると，SA の任意の要素 e に対して，SB に (N - e) が含まれるか判定する．これは unordered_set なりを使えば安心．

足して N になるような e ∈ SA, N - e ∈ SB が見つかったら，あとはそれを適当にコンバートして出力しておわり．

B が A を -2 倍したものであることを利用すると少し簡単に書ける

Submission #2991068 - AtCoder Beginner Contest 105

スマートな解法が全然思いつかなくて正直解けないかと思って焦った