はじめに この記事は、「bit列を用いたbit全探索」を前提知識としています。それ以外は基本的に記事中で説明するように心がけています。 もし不安がある場合は、この記事を読むと理解が進む可能性があります。 また、記事中のサンプルコードは基本的にC#で書かれていますが、できる限り平易な書き方を心がけています。 本記事で説明するテクニックで落ちる計算量は、現実的には高々$20$倍程度の改善にしかなりません。このオーダーだと定数倍レベルが大事になってくると感じているため、そこも意識した記事構成としています。ご了承ください。 突然ですが、bit全探索を用いて以下の問題を解いてみましょう。 問題 $A_1,A_2 \cdots A_N$という数列があります。この数列から数をいくつか選び、その総和が$M$に最も近くなるような選び方をします。そのときのMとの絶対値を求めて下さい。 【制約】 $1\leqq