結果

問題 No.382 シャイな人たち (2)
ユーザー nagissnagiss
提出日時 2020-10-12 04:09:07
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 3,207 bytes
コンパイル時間 927 ms
コンパイル使用メモリ 10,860 KB
実行使用メモリ 12,944 KB
最終ジャッジ日時 2023-09-27 23:31:54
合計ジャッジ時間 19,881 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class MaxClique:
    # 最大クリーク
    # Bron–Kerbosch algorithm (O(1.4422^|V|)) の枝刈りをしたもの
    # 参考: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/2691674
    # 検証1: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/7620028
    # 検証2: https://judge.yosupo.jp/submission/12486
    def __init__(self, n):
        self.n = n
        self.E = [0] * n
        self.stk = [0] * n  # 最大クリークが入るスタック

    def __repr__(self):
        return "\n".join("{:0{}b}".format(e, self.n) for e in self.E)

    def add_edge(self, v, u):
        # assert v != u
        self.E[v] |= 1 << u
        self.E[u] |= 1 << v

    def invert(self):
        # 補グラフにする
        n, E = self.n, self.E
        mask = (1<<n) - 1  # 正の数にしないと popcount がバグる
        for i in range(n):
            E[i] = ~E[i] & (mask ^ 1<<i)  # 自己ループがあるとバグる

    def solve(self):
        n, E = self.n, self.E
        deg = [bin(v).count("1") for v in E]
        self.index = index = sorted(range(n), key=lambda x: deg[x], reverse=True)  # 頂点番号を次数の降順にソート
        self.E_sorted = E_sorted = []  # E を 次数の降順に並び替えたもの
        for v in index:
            E_sorted_ = 0
            E_v = E[v]
            for i, u in enumerate(index):
                if E_v >> u & 1:
                    E_sorted_ |= 1 << i
            E_sorted.append(E_sorted_)
        cand = (1 << n) - 1  # 候補の集合
        self.cans = 1  # 最大クリークを構成する集合  # 復元するときはこれを使う
        self.ans = 1
        self._dfs(0, cand)
        return self.ans

    def _dfs(self, elem_num, candi):
        if self.ans < elem_num:
            self.ans = elem_num
            cans_ = 0
            index = self.index
            for s in self.stk[:elem_num]:
                cans_ |= 1 << index[s]
            self.cans = cans_
        potential = elem_num + bin(candi).count("1")
        if potential <= self.ans:
            return
        E_sorted = self.E_sorted
        pivot = (candi & -candi).bit_length() - 1  # 候補から頂点をひとつ取り出す
        smaller_candi = candi & ~E_sorted[pivot]  # pivot と直接結ばれていない頂点の集合（自己ループの無いグラフなので pivot を含む）
        while smaller_candi and potential > self.ans:
            next = smaller_candi & -smaller_candi
            candi ^= next
            smaller_candi ^= next
            potential -= 1
            next = next.bit_length() - 1
            if next == pivot or smaller_candi & E_sorted[next]:
                self.stk[elem_num] = next
                self._dfs(elem_num + 1, candi & E_sorted[next])


def main():
    mod = 1000003
    S = int(input())
    S = S * 12345 % mod
    N = S % 120 + 2
    S = S * 12345 % mod
    P = S
    mc = MaxClique(N)
    for i in range(N):
        for j in range(i+1, N):
            S = S * 12345 % mod
            if S < P:
                mc.add_edge(i, j)
    ans = mc.solve() + 1
    print(ans)
    print(*[i+1 for i in range(N) if mc.cans>>i&1])

main()
0