[全探索：ビット全探索]を抑える pythonで競プロ

Qiitaで紹介されていた初中級者が解くべき過去問精選 100 問をpython解いてみようという試みです。

第3弾として、[全探索：ビット全探索]の項の問題を解いていきます。

第10問 : 総当たり

問題文

長さ n の数列 A と整数 m に対して、A の要素の中のいくつかの要素を足しあわせて m が作れるかどうかを判定するプログラムを作成してください。A の各要素は１度だけ使うことができます。

数列 A が与えられたうえで、質問として q 個の m_i が与えれるので、それぞれについて “yes” または “no” と出力してください。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja

制約条件

• n≤20
• q≤200
• 1≤Aの要素≤2,000
• 1≤m_i≤2,000

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja

解答

説明

方針としては、与えられるm_iが2000以下と定められているので、先に2000以下の数どれなら作成可能かを各数において判定しておき、その後与えられたm_iが作成可能かを判定していく流れとしました。

2000以下かの判定方法は、まず0~2000までのリストを作り、0以外をFalseで埋めておきます。

その後、Aを一つずつ取り出して、Trueの数(確認済みのAで作成可能な数) + 取り出したAで作成可能な数 をTrueに置き換えていくことで、与えられる数(20) * 2000までの数(2001) = 4万程度のorder数で処理が完了する計算になります。

データの持ち方としては、長さ2001のlistを作成しデータとしては真偽値で持っています。そして、enumerateで取り出すことで(0~2000までの数, 真偽値)の形で出てきてくれます。

また、各Aを加えて作成可能な数を直ぐに元のlistに入れてしまうと、同一のAを複数回使用して埋めていってしまうため、各Aごとに別枠で同じlistを作り2000まで確認完了してから合体する形を取っています。

第11問 : Switches

問題文

on と off の状態を持つ N 個の スイッチと、M 個の電球があります。スイッチには 1 から N の、電球には1 から M の番号がついています。

電球 i は k_i​ 個のスイッチに繋がっており、スイッチ s__i1, s_i2, …, s_iki​​ のうち on になっているスイッチの個数を 2 で割った余りが p_i​ に等しい時に点灯します。

全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

https://atcoder.jp/contests/abc128/tasks/abc128_c

制約条件

• 1≤N,M≤10

• 1≤k_i​≤N

• 1≤s_ij​≤N

• s_ia​≠s_ib​(a≠b)

• p_i​ は 0 または 1

• 入力は全て整数である

https://atcoder.jp/contests/abc128/tasks/abc128_c

解答

説明

恐らく、これがPythonのbit全探索の基本形になるのかなと思います。

N個のTrue/Falseのlistは、itertools.productによって作成することが可能です。(本プログラムでは、計算に用い易いように1/0で作成しています。)

後は、作成した全パターンのlistから条件に合うデータを判定、カウントしていくだけです。

第12問 : 派閥

問題文

神からの財産と、母音を取り戻した高橋くんは、AtCoder国の腐敗した政治を正すため、国会議員となろうと決めました。
もともと人心掌握術とスピーチに定評があった高橋くんは、何の苦労をすることもなく当選しました。
しかし、議員になってからが本番です。国を正すためには、首相に任命される必要があります。

AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係 (x, y) が存在します。
人間関係 (x, y) とは、議員 x と議員 y が知り合いであることを意味します。
高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。
派閥に含まれるすべての議員は互いに知り合いでなければなりません。
高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。

https://atcoder.jp/contests/abc002/tasks/abc002_4

制約条件

1. 1 行目には、高橋くん以外の国会議員の数 N(1≦N≦12)と、人間関係の数 M (0≦M≦N(N-1)/2) が半角空白区切りで与えられる。

2. 2 行目から M+1 行目までの M 行で、人間関係が与えられる。
　　○ 各議員は 1 から N までの整数で番号がつけられている。
　　○ 2 行目を基準とした第 i(1≦i≦M) 行において、議員 x_i​ と議員 y_i​ は知り合いであることを意味する。
　　○ x_i​ と y_i​ はともに整数で、 1≦x_i​<y_i​≦N を満たす。
　　○ i≠j のとき、(x_i, y_i)≠(x_j, y_j)であることが保証されている。

https://atcoder.jp/contests/abc002/tasks/abc002_4

解答

説明

第11と同様に、itertools.productでの全探索になります。

今回は、「派閥に含まれるすべての議員」のパターンをO(2^N)で全探索の形を取っています。

派閥に含まれるすべての議員は互いに知り合いでなければなりません

の条件は以下の条件で読み変えました。

探索中の議員パターン（議員数をmとおく）において、議員パターンに含まれる人間関係が_mC₂個存在している。

後は、この条件を満たす最大議員数を取得して完了です。

第13問 : おせんべい

問題文

IOI 製菓では，創業以来の伝統の製法で煎餅（せんべい）を焼いている．この伝統の製法は，炭火で一定時間表側を焼き，表側が焼けると裏返して，炭火で一定時間裏側を焼くというものである．この伝統を守りつつ，煎餅を機械で焼いている．この機械は縦 R (1≦R≦10) 行，横 C (1≦C≦10000) 列の長方形状に煎餅を並べて焼く．通常は自動運転で，表側が焼けたら一斉に煎餅を裏返し裏側を焼く．

ある日，煎餅を焼いていると，煎餅を裏返す直前に地震が起こり何枚かの煎餅が裏返ってしまった．幸いなことに炭火の状態は適切なままであったが，これ以上表側を焼くと創業以来の伝統で定められている焼き時間を超えてしまい，煎餅の表側が焼けすぎて商品として出荷できなくなる．そこで，急いで機械をマニュアル操作に変更し，まだ裏返っていない煎餅だけを裏返そうとした．この機械は，横の行を何行か同時に裏返したり縦の列を何列か同時に裏返したりすることはできるが，残念なことに，煎餅を 1 枚ごと裏返すことはできない．

裏返すのに時間がかかると，地震で裏返らなかった煎餅の表側が焼けすぎて商品として出荷できなくなるので，横の何行かを同時に 1 回裏返し，引き続き，縦の何列かを同時に 1 回裏返して，表側を焼きすぎずに両面を焼くことのできる煎餅，つまり，「出荷できる煎餅」の枚数をなるべく多くすることにした．横の行を 1 行も裏返さない，あるいは，縦の列を 1 列も裏返さない場合も考えることにする．出荷できる煎餅の枚数の最大値を出力するプログラムを書きなさい．

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e

解答

説明

縦横全てを愚直に全探索した場合、現実的な時間で完了しないため、工夫が必要になります。

縦Rの上限が10と小さいので、縦Rのパターンを全探索としました。

横Cは、各縦Rのパターンにおいて、列毎に出荷可となる煎餅の数が大きくなる方を選択しています。

具体的な実装方法としては、以下の手順としています。

• 各Rのon/offパターンを生成する
• 生成したRパターンにおいて、各列で表となる数をカウントする(「現在の煎餅の表裏」と「行をひっくり返すか否か」の排他的論理和(XOR))
• 列ごとにカウントした数と(C-その数)の最大値を取ることで、列単位の最大枚数を取得
• Rパターン単位で最大値を合計していき、最終的に最も大きかった値を解とする

第14問 : Buildings are Colorful!

問題文

N 個の建物が左から右へと一直線上に並んでいます。左から i 番目の建物は色 i で塗られており、高さは現在 a_i​ です。 高橋君は市長である。彼はカラフルなものが好きなので、左から見たときに K 色以上の色の建物が見えるという条件を満たしてほしいと思いました。

現在の状況から、建物の高さを増やすことができます。しかし、高さを 1 増やすごとに 1 円かかります。また、高さを減らすことはできません。
そのとき、高橋君の目的を達成するために必要な金額を求めなさい。
ただし、「建物 i が見える」とは、建物jの高さ ≥ 建物iの高さ (j<i) となるような j が存在しないのと同じものとします。

https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

制約条件

• 1≤K≤N≤15

• 1≤a_i​≤10⁹

https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

解答

説明

先頭のビルから順番に、再帰で全探索していく方針としました。

再帰に渡す主な情報としては、今何列目か、前にあるビルの最大長、後何回見えないビルがあって良いかです。

再帰のパターンとしては下の3パターンになります。

• 探索中のビルが既に見える高さであれば、最大長を更新する
• 探索中のビルが見えない場合は、最大長+1のコストを支払い最大長を更新して次に行く
• 「探索中のビルが見えない」且「パスして良い回数が残っている」場合は、コストを支払わず、パスして良い回数を1つ減らして次に行く

後は、各階層ごとに最小コストを返すようにしてあげれば、最終的に全ての建物での最小コストが返る形となります。