ビット全探索
本記事は、筆者が学習していく中で、
「この考え、大事だな」と思ったものを記事にしたものです。
皆さんの学習の助けになれば幸いです。
本日のトピック
Atcoder C - Bowls and Dishesより
ふむふむ。どうやら全探索する必要がありそう。しかし全探索するとなると、for文の中にfor文を16回書くことになりそう・・・それだと【TLE】の可能性があるし、何よりコードが汚い。
どうしたことか？
解説を見よう
ということで、今回もうにさんの記事を参考にさせていただきました。
参考記事から引用
制約の人の数は K≤16 です。それぞれの人が Aiか Biのどちらか片方にボールを置きます。よって、ボールの置き方は最大で 2^16=65536 通りしかありません。よって、全部の置き方を 『bit全探索』 で試すことができます。
なるほど・・・おしゃっていることは理解できました！
がしかし、哀川はbit全探索がわかりません。
ということで今度はbit全探索について調べてみました。
bit全探索って
次の参考文献は、E869120さんの記事です！
（余談ですが、この方は高校生でありながら、レッドコーダーで、かつ競プロ典型90問の作成者でもあります）
記事を読んで、僕なりに解釈すると
要素が0 or １で選べる時、2進数で数を表せば、計算量が減る
ってことなのかと考えました。（間違っていたら教えて下さい！！）
考え方
bit全探索の計算量は、O(2**n)に対し、for文をネストさせた場合の計算量はO(n**n)なので、計算量が大幅に減らせるから。
記事を読んで、自分なりになんとなくですが、bit全探索について理解できました。次は「どーゆー時に使えばよいのか？」を考えていきましょう！
どーゆー時使うか考える。
bit全探索を使う場面について僕なりに考えてみた結果、「下記の条件の時使用するのではないか？」と考えました。
・要素が 0 or 1で表せる時
・Nの数が20までの時
・要素が 0 or 1で表せる時
bit探索のメリットして、2進数で表すことで、計算量を落とせるというメリットがあります。そのため逆に言うと、2進数で表せないものでは使用できないのではないかと考えました。実際今回の問題に関しても、E869120さんの記事で出題されている例題も要素を選ぶ(1)or選ばない(0)の2通りで表せる問題でした。
・Nの数が20までの時
Pythonは1secで処理できる計算量が約10^7までだと言われています。それよりも計算量が大きいとAtcoderの場合はTLEになってしまいます。
そのため、2^20＝1048576 までなら、bit全探索することが可能です。
最後に
最後までお読みいただき、誠にありがとうございます！！
Atcoderをやる上で、bit全探索はすごく大事な思考法になります。自分もまだまだ勉強途中なので、間違っているところがあったら、コメントお願いします！！