LoginSignup
23
8

More than 1 year has passed since last update.

こわくないbit全探索4 実践編: AtCoderの問題を解いてみよう!【競プロ解説】

Last updated at Posted at 2021-11-15

競技プログラミング(AtCoder)初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。

この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。

記事リンク

1. 入門編 bit全探索ってなに? : bit全探索はどんなことをするアルゴリズムなのか解説します。 
2. 基本編1 簡単な例題でbit全探索をやってみよう! : 簡単な例題(部分和問題)で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう! : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう! : AtCoderのbit全探索を使う問題のヒントとコード(Python・C++)を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう! : 再帰関数を使ってbit全探索に似た問題を解きます。

質問先など

ご指摘・ご質問はツイッター・マシュマロ・Discordサーバーまでお気軽にどうぞ!

Twitter: u2dayo
マシュマロ: https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー(質問や記事の感想・リクエストなどどうぞ!) : https://discord.gg/jZ8pkPRRMT

よかったらLGTM拡散していただけると喜びます!

実践編 : AtCoderの問題を解いてみよう

bit全探索に慣れるために、AtCoderのbit全探索を使う問題 $6$ 題 を実際に解いてみましょう。

解答コードは以下の $3$ パターンを用意しました。

  • Python(productを使った実装)
  • Python( $2$ 進法を使った実装)
  • C++( $2$ 進法を使った実装)

できるだけ自力で解いて、bit全探索の実装に慣れることをおすすめします。もし詰まった場合は、簡単なヒントを載せてあるので、まずはそちらを見てください。

第1問

ABC190 C - Bowls and Dishes

基本的な問題ですが、少し問題文がややこしいので注意してください。

ヒント


ヒント

bit全探索するのは、人がどちらの皿にボールを置くかです。
どの皿にボールが何個載せられているか、カウントしましょう。(ボールの数は1個以上なら何個でも変わらないので、TrueかFalseで管理してもいいです)
判定部分は、問題文通りにforループで判定すれば良いです。

コード

Python(product): コード
Python($2$ 進法): コード
C++: コード

おまけコード

Pythonではproduct()関数に $i$ 人目が選ぶ皿の選択肢のタプルそのものを渡すことで、皿の選び方そのものを直接全列挙できるので、楽をできます。

Python(productおまけ): コード

第2問

ABC167 C - Skillup

やや実装は重いですが、基本的な問題です。

ヒント


ヒント

答えの初期値はINF(適当な巨大な整数)にしておきます。
判定部分は関数に分けたほうがコードがぐちゃぐちゃにならずに済みます。
判定関数では買った参考書の合計金額と、各アルゴリズムの理解度を管理します。
最後に、理解度の条件を満たしているなら合計金額を、満たしていないならINFを返します。
全パターン試して答えがINFならば、どうやっても達成不可能なので-1を出力すればいいです。

ACコード

Python(product): コード
Python($2$ 進法): コード
C++ : コード

第3問

ABC182 C - To 3

bit全探索以外の解法もあります。bit全探索は若干実装が重くなる代わりに、何も考えなくて良いので楽かもしれません。

ヒント

ヒント

Nを文字列で受け取ったほうが楽です。
使う桁、使わない桁をbit全探索して、使う桁を空の文字列に追加し、最後に文字列を整数に変換し、3の倍数か判定しましょう。
すべての桁を消してしまう場合の処理に気をつけてください。

ACコード

Python(product): コード
Python($2$ 進法): コード
C++ : コード

第4問

ABC128 C - Switch

問題文をよく読んで判定部分を書けば、それほど難しい問題ではないはずです。

ヒント

ヒント

電球iはスイッチxと繋がっている、という入力が与えられますが、スイッチxが電球iとつながっている、の形で持つほうが実装が楽です。

ACコード

Python(product): コード
Python($2$ 進法): コード
C++ : コード

第5問

ABC173 C - H and V

行と列の $2$ 通りの操作がありますが、これもbit全探索で解けます。

ヒント

ヒント

行と列、それぞれどれ塗るか管理するタプルや整数を、二重ループで別々に作ったほうがわかりやすいです。(計算量は変わりません)

ACコード

Python(product): コード
Python($2$ 進法): コード
C++ : コード

第6問

ABC197 C - ORXOR

やや難易度の高い問題ですが、ORやXORに惑わされなければ解けるはずです。

ヒント

ヒント

ORの演算子は|で、XORの演算子は^ です。ORやXORが何をやっているか知らなくても解けます。
N-1箇所、|^を入れる場所があると考えるとよいです。

ACコード

Python(product): コード
Python($2$ 進法): コード
C++ : コード

記事リンク(再掲)

1. 入門編 bit全探索ってなに? : bit全探索はどんなことをするアルゴリズムなのか解説します。 
2. 基本編1 簡単な例題でbit全探索をやってみよう! : 簡単な例題(部分和問題)で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう! : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう! : AtCoderのbit全探索を使う問題のヒントとコード(Python・C++)を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう! : 再帰関数を使ってbit全探索に似た問題を解きます。

23
8
0

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
  3. You can use dark theme
What you can do with signing up
23
8