結果
| 問題 | No.1560 majority x majority |
| ユーザー |
 tobusakana
|
| 提出日時 | 2022-10-23 15:07:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 1,466 bytes |
| コンパイル時間 | 178 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 1,178,344 KB |
| 最終ジャッジ日時 | 2024-07-02 07:17:15 |
| 合計ジャッジ時間 | 6,877 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
ソースコード
import sys
readline = sys.stdin.readline
N,M = map(int,readline().split())
S = [list(map(int,readline().split())) for i in range(N)]
vote = [None] * N
for i in range(N):
val = 0
rate = 1
for j in range(len(S[i])):
if S[i][j] == 1:
val += rate
rate <<= 1
vote[i] = val
# vote[i] = 人iが賛成の議案の集合
# 全ての人について、各議案に賛成かを調べることで、
# survive[s] = 全ての議決集合sに対して賛成の人の集合をあらかじめ求めることが出来る。
survive = [set() for i in range(1 << M)]
for status in range(1 << M):
# statusで1が立っているbitに対して一つでも0になっている議員は除外
for i in range(N):
if status & vote[i] == status: # 全て投票している
survive[status].add(i)
# dp[s] = 議決集合sになる場合の数
dp = [0] * (1 << M)
dp[0] = 1
for status in range(1 << M):
for target in range(M): # 次に可決したい議案
if (status >> target) & 1: # 可決済み
continue
next_status = status | (1 << target)
# statusで残っている人 survive[status] の過半数が、survive[next_status]に残っていればOK
# survive[status] & survive[next_status] の大きさがsurvive[status]の半数以上であればOK
limit = (len(survive[status]) + 1) // 2
if len(survive[status] & survive[next_status]) >= limit:
dp[next_status] += dp[status]
print(dp[-1])