めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

O - Matching の解説(その2)

何の話かと言うと

enakai00.hatenablog.com

こちらの記事の続きです。

改善のヒントは・・・?

前回の最後に、参加する男性を1人ずつ増やすという発想で、DPの実装に成功しました。

しかしながら、まだ実行時間が長すぎるので、さらなる工夫が必要です。前回のコードを思い返すと、男性については、1 人ずつ増やすと言う簡易な(O(N) の)ループになっていますが、それぞれの中で、「あらゆる女性の組み合わせ」という O(2^N) のループをしていました。このループに時間がかかりそうなのは容易に想像ができます。

女性についても、いきなりフル参加してもらうのではなく、男性と同様に徐々に人数を増やすことはできないのでしょうか・・・?

ただ女性については、女性1だけの場合、女性1と女性2の場合・・・、というように、順番に追加するという方法ではうまく行きません。男性1だけのケースを考える際に、女性についても、女性1だけと限定したら、男性1と他の女性(たとえば女性2)がマッチするというケースがカウントできません。

あるいは、男性1のケースについて、「女性1だけの場合、女性1と女性2の場合、・・・」というように N 通りの女性の組み合わせに限定してもだめです。次のステップ(n=2 のケース)で、男性2が女性1 にマッチした場合、n=1 のケースには、「女性1が居ない場合」が含まれていないと困ることになります。

うーん。やはり、女性群はあらゆる組み合わせの事前計算が必要なのか・・・・?

と、PCに向かって悩んでいても仕方がないので、こういう時は、お風呂にはいってゆっくりしながら、頭を整理しなおします。

すると・・・気付くんですね!

n = 1 のケースは、「女性が1人だけの場合」(つまり、女性1だけ、女性2だけ・・・)を網羅すればOKです。

そして、その次の n = 2 のケースでは、「女性が2人だけの場合」に限定してこれを網羅します。

こうすると、n = 2 のケースが、全部で2人の女性から、男性2にマッチする女性を選べば、残りの女性はもれなく1人になりますので、n = 1 のケースで計算した結果が確実に使えます。n = 3, 4, ... についても同様です。一般に、dp[n][females] を計算する際は、n 人の女性を含む場合に females に限定できます。

こうすると、ステップを進むごとに女性の数が増えていき、最終的に、n = N において、全ての男性と全ての女性をマッチするケースになって、確かに問題の答えが得られます。いやー、よくできていますねー。

というわけでさっそく実装してみましょう。

import sys

def main(f):
  mod = 10**9 + 7
  N = int(f.readline())
  T = [None]
  for i in range(N):
    T.append([None] + list(map(int, f.readline().split())))

  bitcnt = [0] * 2**N     # バイナリー表現で何人の人を含むかを事前計算
  group = [[] for _ in range(N+1)] # group[n] : n 人含む females の値のリスト
  for i in range(2**N):
    bitcnt[i] = bitcnt[i >> 1] + i % 2
    group[bitcnt[i]].append(i)

  dp = [[0] * 2**N for _ in range(N+1)]

  # n = 1 の場合
  for females in group[1]:
    for f in range(1, N+1): # 男性 1 とマッチする女性を探す
      if females & 1<<(f-1) and T[1][f] == 1: # 女性 f がグループにいてマッチ可能
        dp[1][females] = 1

  # n = 2, 3, ..., N の場合
  for n in range(2, N+1):
    for females in group[n]:
      for f in range(1, N+1): # 男性 n とマッチする女性を探す
        if females & 1<<(f-1) and T[n][f] == 1: # 女性 f がグループにいてマッチ可能
          dp[n][females] += dp[n-1][females ^ 1<<(f-1)] # 女性 f を除いて、残りを n 未満の男性とマッチする場合の数
          dp[n][females] %= mod

  print(dp[N][2**N-1])

main(sys.stdin)

ここでは、「n 人の女性を含む females の一覧」を事前に計算して、リスト group[n] にまとめてあります。このコードは、TLEせずにちゃんとパスしてくれます。やったー。

atcoder.jp

おまけ

という感じで、一見するとどこから手をつけてよいかわからない難問も、まずは、「しらみつぶし」を実装することで、そこから DP を組み立てるヒントが得られることがわかりました。

最後におまけとして、最後のコードをさらにもう一歩きれいにする方法を紹介します。

ここまでの流れでは、

  # n = 2, 3, ..., N の場合
  for n in range(2, N+1):

という n についてのループは、何人目までの男性に参加してもらうか、を表すものになっていました。しかしながら、このコードをあらためてみると、この n のループは、参加する女性の数を 1 人ずつ増やしていくというループと見ることもできます。

つまり、参加する女性の数 n を増やしながら、「n 人の女性が男性 1 〜男性 n と完全マッチする場合の数」を順番に計算していると考えることもできます。

コードには明示的には書かれていませんが、「n 人の女性はかならず先頭の n 人の男性とマッチする」という暗黙の前提条件を加えて問題を解いているというわけです。

で、ここまでは、単なる「コードの解釈の違い」であって、コードの中身は同じなのですが、男性を変化させるのではなくて、「女性を変化させながら DP のステップを進める」という発想で考えると、実は、女性の人数を増やしていくというステップではなくて、

・女性群 females を 1 から 2^N-1 まで数値順に変化させる

というステップでも計算がうまく成立することがわかるのです。

なんじゃそれ・・・

と思うかもしれませんが、まずは、実際のコードを見てください。

import sys

def main(f):
  mod = 10**9 + 7
  N = int(f.readline())
  T = [None]
  for i in range(N):
    T.append([None] + list(map(int, f.readline().split())))

  dp = [0] * 2**N
  bitcnt = [0] * 2**N
  for i in range(2**N):
    bitcnt[i] = bitcnt[i >> 1] + i % 2
    
  dp[0] = 1
  for females in range(2**N):
    i = bitcnt[females]
    # i 人目の男性がどの女性とペアになるかで場合分け
    for f in range(1, N+1):
      if females & 1<<(f-1) and T[i][f]:
        dp[females] += dp[females ^ 1<<(f-1)]
        dp[females] %= mod

  print(dp[2**N-1])

main(sys.stdin)

これ、よーく落ち着いて考えるとわかるのですが、females を数値順に増やしていった場合、ある与えられた females に対して、特定の女性を取り除く、すなわち、どこかのビットを0にするすると、残った females の値は必ず小さくなるので、対応する値はすでに計算済みになっているのです。この特性を利用することで、

dp[females] += dp[females ^ 1<<(f-1)] # 右辺の値は必ず計算済みになっている

という更新がうまくいくのです。また、このやり方の場合、現在考えている女性の数(もしくは、男性の数)をトラッキングする必要もないので、dp[n][females] の1つめのインデックス [n] すらも不要になるのです。

まぁ、これは言われないと気づかないですが、計算の対象物を今回の様にバイナリー表現で表す場合は、こういうバイナリー値のオーダーで処理する方法もある、ということを覚えておくとよいでしょう。