改善のヒントは・・・？
前回の最後に、参加する男性を1人ずつ増やすという発想で、DPの実装に成功しました。
しかしながら、まだ実行時間が長すぎるので、さらなる工夫が必要です。前回のコードを思い返すと、男性については、1 人ずつ増やすと言う簡易な（ の）ループになっていますが、それぞれの中で、「あらゆる女性の組み合わせ」という
のループをしていました。このループに時間がかかりそうなのは容易に想像ができます。
女性についても、いきなりフル参加してもらうのではなく、男性と同様に徐々に人数を増やすことはできないのでしょうか・・・？
ただ女性については、女性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せずにちゃんとパスしてくれます。やったー。
おまけ
という感じで、一見するとどこから手をつけてよいかわからない難問も、まずは、「しらみつぶし」を実装することで、そこから DP を組み立てるヒントが得られることがわかりました。
最後におまけとして、最後のコードをさらにもう一歩きれいにする方法を紹介します。
ここまでの流れでは、
# n = 2, 3, ..., N の場合 for n in range(2, N+1):
という n についてのループは、何人目までの男性に参加してもらうか、を表すものになっていました。しかしながら、このコードをあらためてみると、この n のループは、参加する女性の数を 1 人ずつ増やしていくというループと見ることもできます。
つまり、参加する女性の数 n を増やしながら、「n 人の女性が男性 1 〜男性 n と完全マッチする場合の数」を順番に計算していると考えることもできます。
コードには明示的には書かれていませんが、「n 人の女性はかならず先頭の n 人の男性とマッチする」という暗黙の前提条件を加えて問題を解いているというわけです。
で、ここまでは、単なる「コードの解釈の違い」であって、コードの中身は同じなのですが、男性を変化させるのではなくて、「女性を変化させながら DP のステップを進める」という発想で考えると、実は、女性の人数を増やしていくというステップではなくて、
・女性群 females を 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] すらも不要になるのです。
まぁ、これは言われないと気づかないですが、計算の対象物を今回の様にバイナリー表現で表す場合は、こういうバイナリー値のオーダーで処理する方法もある、ということを覚えておくとよいでしょう。
