search
LoginSignup
7

More than 1 year has passed since last update.

posted at

updated at

【AtCoder】ビット全探索〜問題まとめましたっ!〜

C問題でちらほら出てきてたbit全探索とかいうのをやっつけようと思って、解いたついでにまとめてみたよ!

お勉強

先走って備忘録

一応、自分が何回も確認したものを載せておくよ!「わかってるけど忘れた」時に参考にしてね!

sample.py
# i が、スイッチのオンオフや、ものを買うかどうか、を管理するよ。
# (1 << n) まで、つまり、 0 から 2^n -1 まで動くよ。
for i in range(1 << n):
    # 適当な操作


    # i を利用して、x番目のスイッチがオンかどうかチェックするよ!
    # & 1 の部分は、i >> x の1の位だけを見たいから。
    if ((i >> x) & 1):


基礎の確認

もしビット演算に不安があれば、先にこれを見て確認した方が良き!
Python ビット演算 超入門

C++の人は、AtCoder公式がいいのかな?
AC - 3.05.ビット演算

本番

ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜
↑のページの、次の箇所↓だけは 理解しないと or 使えないと、どうしようもないから、要チェック!日本語との対応がめちゃめちゃわかりやすい!何やっているか分からなくて、それが嫌だったら基本を確認し直しだぁ🔥🔥
5. ビット演算は集合演算

基礎演習

ABC014 B - 価格の合計
全探索の前に、一つだけでできるか確認するのにちょうどいい問題があったよ!!

問題演習

Bit全探索って、ABCだと毎回C問題なのね!これらを解かずしてここまで来れたの、運が良かったとしか言えないかも🤣

ABC128 C - Switches

私はABC147の問題を最初に解いちゃったけど、これが一番簡単らしい!!
そんな簡単じゃないけどね??🤔

ABC147 C - HonestOrUnkind2

一行ずつ、YouTubeでsnuke先生と辿りたければこちら!
AtCoder Beginner Contest 147
1 << nってするところを、2^nを意識しすぎたせいで2 << nにして、かなり時間溶かしてしんどかった〜笑
snuke先生、問題の入力に合わせてるのか!なるほど、確かに分かりやすい。

ABC045 C - たくさんの数式

これ結構沼っちゃって、チェック用に次の出力もしてみたよ!
動作確認用 : サンプルコード
毎回足してるものと、一周するたびに今の答えを出力して確認するみたいなの、デバッグにいいよね😎✨
きょ...共有のために、わざとこのまま提出したんだからっ!!

ABC167 C - Skill Up

サンプルで気づいたけど、初期値を2*(10**6)にして、条件満たすのがなかったときに-1にし忘れちゃってた🤣
でも、上のをクリアしてたら、すんなり解けるようになってた!嬉しい!!

C - Shopping Street

問題文読むのが非常〜〜〜に大変!!!Cにしてはちょっと嫌だなぁって問題だと思う😭
もう水色に上がる3週間前のつもりの時期でも、30分くらいかかった😭

おしまい

ここまで解いた皆さん、お疲れ様でした〜〜〜🎉🎉

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
7