結果
問題 | No.1560 majority x majority |
ユーザー |
|
提出日時 | 2022-10-23 15:12:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,581 ms / 2,000 ms |
コード長 | 1,731 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 87,188 KB |
実行使用メモリ | 239,292 KB |
最終ジャッジ日時 | 2023-09-15 01:29:43 |
合計ジャッジ時間 | 12,907 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,097 ms
239,292 KB |
testcase_01 | AC | 1,190 ms
239,116 KB |
testcase_02 | AC | 70 ms
71,540 KB |
testcase_03 | AC | 928 ms
227,164 KB |
testcase_04 | AC | 507 ms
210,480 KB |
testcase_05 | AC | 1,581 ms
210,352 KB |
testcase_06 | AC | 192 ms
87,444 KB |
testcase_07 | AC | 138 ms
81,224 KB |
testcase_08 | AC | 565 ms
143,068 KB |
testcase_09 | AC | 382 ms
104,536 KB |
testcase_10 | AC | 90 ms
76,852 KB |
testcase_11 | AC | 145 ms
81,268 KB |
testcase_12 | AC | 108 ms
78,812 KB |
testcase_13 | AC | 147 ms
82,196 KB |
testcase_14 | AC | 109 ms
78,876 KB |
testcase_15 | AC | 249 ms
96,320 KB |
testcase_16 | AC | 105 ms
78,156 KB |
testcase_17 | AC | 872 ms
142,928 KB |
testcase_18 | AC | 254 ms
90,640 KB |
testcase_19 | AC | 87 ms
76,884 KB |
testcase_20 | AC | 106 ms
78,024 KB |
testcase_21 | AC | 106 ms
78,432 KB |
testcase_22 | AC | 398 ms
103,648 KB |
testcase_23 | AC | 92 ms
76,844 KB |
testcase_24 | AC | 100 ms
77,396 KB |
testcase_25 | AC | 369 ms
100,500 KB |
testcase_26 | AC | 72 ms
71,328 KB |
testcase_27 | AC | 72 ms
71,360 KB |
testcase_28 | AC | 73 ms
71,160 KB |
testcase_29 | AC | 74 ms
71,472 KB |
testcase_30 | AC | 89 ms
76,608 KB |
ソースコード
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 = [[False] * N for i in range(1 << M)] vote_cnt = [0] * (1 << M) for status in range(1 << M): # statusで1が立っているbitに対して一つでも0になっている議員は除外 for i in range(N): if status & vote[i] == status: # 全て投票している survive[status][i] = True vote_cnt[status] += 1 # 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][i]がTrueであるiに対して、survive[next_status][i]がTrueのものが過半数を超えるか v = 0 limit = (vote_cnt[status] + 1) // 2 for i in range(N): if survive[status][i] and survive[next_status][i]: v += 1 if v >= limit: dp[next_status] += dp[status] break elif (N - 1 - i) + v < limit: # 残り全員投票しても無理なら終了 break print(dp[-1])