AtCoder Beginner Contest (ABC) 190 PythonでC問題解いてみた

前回の続きです。

前回

mery-kirokudayo.hateblo.jp

AtCoder Beginner Contest (ABC) 190のC問題やっていきます。

言語はPython、提出はPyPyです。

目次

C問題　チャレンジ編

問題文

C - Bowls and Dishes

お皿がN枚あり、人間がK人います。
各人間が皿C、Dのどちらかに球を起きます。
条件は最大で何個満たされるでしょうか。
という問題ですね。

全体的に条件が軽い（数字の上限が低い）ので、全探索行けるかなぁ・・・と。

人間がお皿に球を置くパターンを全探索しても2^Kなので、問題なさそうです。
※ 1 <= K <= 16 なので、最大でも2¹⁶なのでTLEにならない。

というわけで方針を。
1. 全探索する。
2. 各パターンで、どのお皿に球が乗っているかを確認。
3. そのパターンで満たす条件をチェック。
4. 条件を満たしたらansを増やす。

というわけで、全探索してみよう！！と書いたのがこちらのコード。

n,m = map(int,input().split())
joken = []
for i in range(m):
    a,b = map(int,input().split())
    joken.append([a,b])
k = int(input())
oku = []
for i in range(k):
    c,d = map(int,input().split())
    oku.append([c,d])
ans = 0

はい。そうです。全探索の方法がわかりませんでした。

全探索しようとすると詰まったんですよね・・・。

樹形図でサンプル1を書くとこんな感じになります。

1 --------- 1 ------2
    |              L----3  
    |
    L------ 3--------2
                   L----3


2 --------- 1 ------2
    |              L----3  
    |
    L------ 3--------2
                   L----3

これをどうやって全探索すればいいんだろう・・・。って感じです。

C問題　解決編

はい、というわけで解決編です。

皆さんはこんな言葉をご存知でしょうか。

bit全探索

はい、そうです。
ビットでフラグ管理することで全探索することができるのです。

実際のイメージだと、こんな感じ。

例： サンプル1の場合

3人全員が皿Cを選ぶ場合。 （樹形図１，１，２） 000

2人が皿C、1人が皿Dを選ぶ場合。 （樹形図１，１，３） 001

のように、任意のある人iが皿Cを選ぶ時、i番目のビットが0になるようにすると、全探索できるのである。

毎回、二進数で1を足すことで、重複無く全てのパターンをチェックできるのです。

方針は全く変わらず、
1. 全探索する。
2. 各パターンで、どのお皿に球が乗っているかを確認。
3. そのパターンで満たす条件をチェック。
4. 条件を満たしたらansを増やす。
ということで書きました。

というわけで書いたコードがこちら。

n,m = map(int,input().split())
joken = []
for i in range(m):
    a,b = map(int,input().split())
    joken.append([a,b])
k = int(input())
oku = []
for i in range(k):
    c,d = map(int,input().split())
    oku.append([c,d])

ans = 0

# bit全探索開始
for i in range(2 ** k):
    dish = [0] * n  # お皿を初期化
    # 人数分のbitをチェック
    for j in range(k):
        if (i >> j) & 1:
            dish[oku[j][1]-1] += 1
        else:
            dish[oku[j][0]-1] += 1
    sum_i = 0  # 条件を満たす数
    # 満たす条件数をチェック
    for l in range(m):
        if dish[joken[l][0]-1] > 0 and dish[joken[l][1]-1] > 0:
            sum_i += 1
    # 最大値を答えるので、答えを更新
    if ans < sum_i:
        ans = sum_i
else:
    print(ans)

というわけでコードの解説していきます。

前半部分はいろいろ入力を受け付けたり、変数を定義しているだけです。

後半部分のループからです。

rangeが2^kになっているのは、各人間が皿に置くパターンがCかDかの二択で、その選択がK人分あるので、全パターンは2^kとなるから。
※わかりずらかったら樹形図を見てね。上にあるよ。

次、bitチェックする部分ですね。

# 人数分のbitをチェック
for j in range(k):
    if (i >> j) & 1:
        dish[oku[j][1]-1] += 1
    else:
        dish[oku[j][0]-1] += 1

rangeがｋなのは人数分のループを回すから。

続いて、if文の中。
サンプル1を例にします。

i = 0 の時、  
 dish = [0,0,0,0]  
 j = 0 の時、  
  i & 1   = 0 よってFalse # i = 000(2進数) 
  dish[oku[0][0]-1] += 1   
  # １人目がCを選択したということ(iの右から１番目が０)。  
  #皿１（１人目のC選択）に１追加 dish = [1,0,0,0]  
 j = 1の時、
  i >> 1 & 1 = 0 よってFalse # i = 000(２進数)  
 # ０００を右に1ビットずらす。０００→００「０」（「」がなくなる）
 # 右に１ビットずらして空いたとこ（左）には0を追加。「０」００(「」が追加) 
 # これと、&1をとることで、右からj番目の数が0か1かを判別できる。  
  dish[oku[1][0]-1] += 1  
 # 2人目がCを選択したということ（iの右から2番目が0）
 # 皿１（２人目のC選択）に１追加 dish = [2,0,0,0]

:
:
:

というように、iを二進数に直して、右からa番目が1なら、人間a人目が皿Dに置く。0なら、Cに置くという処理を行っている。

サンプル１のi = 0でｊのループが終わったときは

dish = [2,1,0,0]

これは、樹形図でいう、

1 --------- 1 ------2
　　 |　　　L----3
　　|
　　L------ 3--------2
　　　　　　　L----3

太字の選択に該当する。

次、条件チェックの箇所について。

# 満たす条件数をチェック
for l in range(m):
    if dish[joken[l][0]-1] > 0 and dish[joken[l][1]-1] > 0:
        sum_i += 1

各条件を全探索していく。

条件iが満たされる条件は以下の通り。
1. 条件iのAの皿に球がある
2. 条件iのBの皿に球がある
3. 条件1,2を共に満たす

これをコードに直したのが

if dish[joken[l][0]-1] > 0 and dish[joken[l][1]-1] > 0:

このコードの

dish[joken[l][0]-1] > 0

が条件１に該当する。

dish[joken[l][1]-1] > 0

が条件２に該当する。

これらをandで繋ぐことで、条件３が達成される。

そしてif文が通る＝条件を全て満たした場合、
sum_iに1を追加する。（条件１個満たしたよね。）

そして、条件を全探索した後、現時点でのansとsum_iを比較して、大きい方をansに更新する。
※これをやることで、ansが最大値のまま、維持される。

最後にansを表示して終わりです。

むずい！！！

ここでプラスアルファで、bit全探索の注意点。

計算量がバカでかくなるので注意しましょう。

youtubeで、「不可思議の数え方」と検索してみてください。

↓コピー用

不可思議の数え方

nが１つ大きくなるだけで計算時間が膨大になっていくのがわかると思います。

調べていくうちにこういう小話が増えていくのがアルゴリズムの面白いところですよね。

それでは。