#998656 (PyPy3) No.3275 Minesweeper on Graph

提出ソース
結果

問題	No.3275 Minesweeper on Graph
ユーザー	Arleen
提出日時	2024-07-31 14:04:25
言語	PyPy3 (7.3.15)
結果	AC
実行時間	249 ms / 2,000 ms
コード長	15,815 bytes
コンパイル時間	327 ms
コンパイル使用メモリ	82,468 KB
実行使用メモリ	78,392 KB
最終ジャッジ日時	2024-07-31 14:04:35
合計ジャッジ時間	9,623 ms
ジャッジサーバーID （参考情報）	judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 40
権限があれば一括ダウンロードができます
ソースコード

raw source code
import sys
import itertools
#import more_itertools
import time
import heapq
from math import radians, sin, cos, tan, sqrt, comb, pow
from math import log, log2, log10, exp
#from sortedcontainers import SortedSet, SortedDict, SortedList
from collections import deque
from operator import mul
from functools import reduce, cmp_to_key
from random import randint, randrange
from bisect import bisect_left, bisect_right

def input():
    return sys.stdin.readline().replace('\n','')
#sys.setrecursionlimit(1000000)
md1 = 998244353
md2 = 10 ** 9 + 7
inf = 2 ** 31 + 1
primeset = set()
primelist = []

# 入力ツール
# 1行の入力を整数のリストとして受け取る
def intlist():
    return list(map(int, input().split()))

# 1行から複数個の整数を受け取る
def getints():
    return tuple(map(int, input().split()))

# n行の入力を文字列のリストとして受け取る
def strtable(n):
    lst = []
    for i in range(0, n):
        lst.append(input())
    return lst

# n行の入力を整数のリストとして受け取る
def inttable(n):
    return list(map(int, strtable(n)))

# 整数のリストをn個受け取る
def intlisttable(n):
    lst = []
    for i in range(0, n):
        lst.append(intlist())
    return lst

# n個のクエリを先頭だけ整数、他を文字列のリストとして受け取る
def getquery(n):
    lst = []
    for i in range(0, n):
        query = list(input().split())
        qr = int(query[0])
        lst.append((qr, query[1:]))
    return lst

#==========
# 生成ツール
# H行W列のリスト生成
def twodimlist(h, w, init): # initの値で初期化
    lst1 = []
    for i in range(0, h):
        lst2 = []
        for j in range(0, w):
            lst2.append(init)
        lst1.append(lst2)
    return lst1

# # 素数テーブルをsetとして生成
# def genprimeset(n): # n以下の素数を列挙
    # global primeset
    # pt = SortedSet(primeset)
    # start = 2
    # if len(pt) != 0:
        # start = pt[-1]+1
    # for i in range(start, n+1):
        # pt.add(i)
    # idx = 0
    # while pt[idx] ** 2 <= pt[-1]:
        # now = pt[idx] * 2
        # while now <= pt[-1]:
            # pt.discard(now)
            # now += pt[idx]
        # idx += 1
    # return set(pt)

#==========
# 数え上げ
# 1次元数え上げ
def cntx(itr, x):
    cnt = 0
    for i in range(0, len(itr)):
        if itr[i] == x:
            cnt += 1
    return cnt

# 2次元数え上げ
def twodimcntx(itr, x):
    sm = 0
    for i in range(0, len(itr)):
        sm += cntx(itr[i], x)
    return sm

# 全要素数え上げ
def allcnt(itr):
    dct = {}
    for i in range(0, len(itr)):
        if itr[i] not in dct:
            dct[itr[i]] = 0
        dct[itr[i]] += 1
    return dct

# 2次元全要素数え上げ
def twodimallcnt(itr, x):
    dct = {}
    for i in range(0, len(itr)):
        for j in range(0, len(itr[i])):
            if itr[i][j] not in dct:
                dct[itr[i][j]] = 0
            dct[itr[i][j]] += 1
    return dct

#==========
# 計算ツール
# 最大公約数
def gcd(x, y):
    if x < y:
        return gcd(y, x)
    if x % y == 0:
        return y
    return gcd(y, x%y)

# 最小公倍数
def lcm(x, y):
    g = gcd(x, y)
    return (x*y) // g

# フィボナッチ数列(0-indexで、a_0 = 0, a_1 = 1, 第n項まで生成)
def genfib(n, m): # m == 0ならmodなし、m == 1ならmd1でmod, m == 2ならmd2でmod
    lst = [0, 1]
    if m == 0:
        for i in range(1, n):
            lst.append(lst[-2]+lst[-1])
    else:
        md = md1
        if m == 2:
            md = md2
        for i in range(1, n):
            lst.append((lst[-2]+lst[-1])%md)
    return lst

# 素数一覧の初期化
def primeinit(x):
    global primeset, primelist
    primeset = genprimeset(x)
    primelist = list(primeset)
    return

# 素数判定
def isitprime(x):
    if x < 2:
        return False
    global primeset, primelist
    if len(primeset) == 0:
        primeinit(int(sqrt(x))+10)
    elif primelist[-1] ** 2 < x:
        primeinit(int(sqrt(x))+10)
    if x in primeset:
        return True
    for i in range(0, len(primelist)):
        if x % primelist[i] == 0:
            return False
    return True

# 素因数分解
def factorize(x):
    global primeset, primelist
    if len(primeset) == 0:
        primeinit(int(sqrt(x))+10)
    elif primelist[-1] ** 2 < x:
        primeinit(int(sqrt(x))+10)
    dct = {}
    now = x
    for i in range(0, len(primelist)):
        if x < primelist[i] ** 2:
            break
        while now % primelist[i] == 0:
            if primelist[i] not in dct:
                dct[primelist[i]] = 0
            dct[primelist[i]] += 1
            now //= primelist[i]
    if now != 1:
        dct[now] = 1
    return dct

# Coprime判定
def coprime(x, y):
    return gcd(x, y) == 1

# 約数列挙
def divisor(x):
    s = set()
    for i in range(1, x+1):
        if x < i ** 2:
            break
        if x % i == 0:
            s.add(i)
            s.add(x//i)
    lst = sorted(list(s))
    return lst

# 約数数え上げ
def countdivisor(x):
    fact = factorize(x)
    key = list(fact.keys())
    cnt = 1
    for i in range(0, len(key)):
        cnt *= fact[key[i]] + 1
    return cnt

# 大文字->小文字変換
def uppertolower(c):
    if 'A' <= c and c <= 'Z':
        return chr(ord(c)+32)
    return c

# 小文字->大文字変換
def lowertoupper(c):
    if 'a' <= c and c <= 'z':
        return chr(ord(c)-32)
    return c

# 大文字小文字相互変換
def upperlower(c):
    newc = uppertolower(c)
    if c == newc:
        newc = lowertoupper(c)
    return newc

# 文字列の大->小変換
def uppertolowerstr(s):
    lst = []
    for i in range(0, len(s)):
        lst.append(uppertolower(s[i]))
    return ''.join(lst)

# 文字列の大->小変換
def lowertoupperstr(s):
    lst = []
    for i in range(0, len(s)):
        lst.append(lowertoupper(s[i]))
    return ''.join(lst)

# 文字列の大小相互変換
def upperlowerstr(s):
    lst = []
    for i in range(0, len(s)):
        lst.append(upperlower(s[i]))
    return ''.join(lst)

# x以上の要素の個数
def xormore(lst, x): # lstはソート済みにすること
    return len(lst) - bisect_left(lst, x)

# xより大きい要素の個数
def morethanx(lst, x): # lstはソート済みにすること
    return len(lst) - bisect_right(lst, x)

# x以下の要素の個数
def xorless(lst, x): # lstはソート済みにすること
    return bisect_right(lst, x)

# x未満の要素の個数
def lessthanx(lst, x): # lstはソート済みにすること
    return bisect_left(lst, x)

# 各桁の総和
def digitsum(x):
    nm = str(x)
    sm = 0
    for i in range(0, len(nm)):
        sm += int(nm[i])
    return sm

# bitカウント(64bitまで)
def popcount(x):
    now = x
    now = now - ((now >> 1) & 0x5555555555555555)
    now = (now & 0x3333333333333333) + ((now >> 2) & 0x3333333333333333)
    now = (now + (now >> 4)) & 0x0f0f0f0f0f0f0f0f
    n = 8
    for i in range(0, 3):
        now += (now >> n)
        n *= 2
    return now & 0x0000007f

# xの累乗リスト(0乗からn乗まで)
def powtable(x, n, m): # modなしの場合はm = 0に設定する
    md = m
    if m == 1: # m == 1ならmd1でmod
        md = md1
    elif m == 2: # m == 2ならmd2でmod
        md = md2
    
    lst = [1]
    for i in range(0, n):
        if md == 0:
            lst.append(lst[-1]*x)
        else:
            lst.append((lst[-1]*x)%md)
    return lst

# 繰り返し2乗法
powdct = {}
def initpow():
    global powdct
    powdct = {}
    powdct[0] = 1
    return

def repeatpow(x, y, m):
    global powdct
    
    md = m
    if m == 1:
        md = md1
    elif m == 2:
        md = md2
    
    if y in powdct:
        return powdct[y]
    a = 1
    if y % 2 == 1:
        a = x
    if m == 0:
        a = a*(repeatpow(x, y//2, m)**2)
    else:
        a = (a*(repeatpow(x, y//2, m)**2)) % md
    powdct[y] = a
    return a

def powit(x, y, m):
    global powdct
    initpow()
    if x == 0:
        return 0
    return repeatpow(x, y, m)

# ==========
# リスト操作
# 値の交換
def swap(lst, x, y):
    lst[x], lst[y] = lst[y], lst[x]

# 累積和(先頭を0にする)
def accum(itr):
    lst = [0]
    for i in range(0, len(itr)):
        lst.append(lst[-1]+itr[i])
    return lst

# itrをとりあえずリストに
def itrtolist(itr):
    lst = []
    for i in range(0, len(itr)):
        lst.append(itr[i])
    return lst

# 全ての順列
def permall(itr):
    lst = itrtolist(itr)
    return list(itertools.permutations(lst))

# itrの中身からn個を取り出す順列
def perm(itr, n):
    if len(itr) < n:
        return []
    lst = itrtolist(itr)
    return list(itertools.permutations(lst, n))

# itrの中身からn個を取り出す組合せ
def combi(itr, n):
    if len(itr) < n:
        return []
    lst = itrtolist(itr)
    return list(itertools.combinations(lst, n))

# 0-indexのリストを1-indexのdictに書き換え
def listtodict(lst):
    dct = {}
    for i in range(0, len(lst)):
        dct[i+1] = lst[i]
    return dct

# ==========
# グラフツール
# グラフの初期化
def defgraph(vlist):
    graph = {}
    for i in range(0, len(vlist)):
        graph[vlist[i]] = set()
    return graph

# 重み付きグラフの初期化
def defgraphw(vlist):
    graph = {}
    for i in range(0, len(vlist)):
        graph[vlist[i]] = {}
    return graph

# 無向グラフ生成
def undirgraph(vlist, elist): # 辺の形式は(u, v)
    graph = defgraph(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u].add(v)
        graph[v].add(u)
    return graph

# 重み付き無向グラフ生成
def undirgraphw(vlist, elist, wdict):
    graph = defgraphw(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u][v] = wdict[elist[i]]
        graph[v][u] = wdict[elist[i]]
    return graph

# 有向グラフ生成
def dirgraph(vlist, elist): # 辺の形式は(u, v)で、向きはu -> v
    graph = defgraph(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u].add(v)
    return graph

# 重み付き有向グラフ生成
def dirgraphw(vlist, elist, wdict):
    graph = defgraphw(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u][v] = wdict[elist[i]]
    return graph

# 重み無し最短ステップ
def shortest(vlist, elist, graph, st, gl):
    if st not in graph or gl not in graph:
        return -1
    yet = set(vlist)
    q = deque()
    q.append((st, 0))
    yet.discard(st)
    while len(q) != 0:
        now = q.popleft()
        v = now[0]
        s = now[1]
        if v == gl:
            return s
        lst = list(graph[v])
        for i in range(0, len(lst)):
            nxtv = lst[i]
            if nxtv in yet:
                yet.discard(nxtv)
                q.append((nxtv, s+1))
    return -1

# ダイクストラ
def dijkstra(vlist, elist, graph, st):
    cur = {}
    for i in range(0, len(vlist)):
        cur[vlist[i]] = inf
    cur[st] = 0
    dist = {}
    h = []
    heapq.heapify(h)
    heapq.heappush(h, (0, st))
    
    while len(h) != 0:
        now = heapq.heappop(h)
        d = now[0]
        v = now[1]
        if v in dist:
            continue
        dist[v] = d
        lst = list(graph[v].keys())
        for i in range(0, len(lst)):
            nxt = lst[i]
            if nxt not in dist:
                nxtd = dist[v] + graph[v][nxt]
                cur[nxt] = min(cur[nxt], nxtd)
                if cur[nxt] == nxtd:
                    heapq.heappush(h, (nxtd, nxt))
    return dist

# Union-Find生成
def genunionfind(vlist, elist): # 辺の形式は(u, v)
    graph = defgraph(vlist)
    root = {}
    vcnt = {}
    flag = False
    for i in range(0, len(vlist)):
        root[vlist[i]] = vlist[i]
        vcnt[vlist[i]] = 1
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        ur = root[u]
        vr = root[v]
        if ur == vr:
            flag = True
        else:
            H = ur
            L = vr
            if vcnt[ur] < vcnt[vr]:
                H = vr
                L = ur
            graph[H].add(L)
            vcnt[H] += vcnt[L]
            q = deque()
            q.append(L)
            while len(q) != 0:
                now = q.popleft()
                root[now] = H
                lst = list(graph[now])
                for j in range(0, len(lst)):
                    q.append(lst[j])
    return (graph, root, vcnt, flag) # (グラフ, 根, 頂点の数, ループ検出)の形式で返す

# ==========
# fenwick木
fenwick = []

# fenwickを初期化
def initfenwick(n, init):
    global fenwick
    fenwick = []
    for i in range(0, n+1):
        fenwick.append(init)
    return

# idx番目までの和を求める
def fwsum(idx):
    sm = 0
    now = idx
    while now > 0:
        sm += fenwick[now]
        now -= -now & now
    return sm

# idx番目の値にxを足す
def fwadd(idx, x):
    global fenwick
    now = idx
    while now < len(fenwick):
        fenwick[now] += x
        now += -now & now
    return

# 転倒数
def inversion(A):
    global fenwick
    initfenwick(len(A), 0)
    sm = 0
    for i in range(0, len(A)):
        sm += i - fwsum(A[i])
        fwadd(A[i], 1)
    return sm

# ==========
# ハッシュ
Mset = set()
Mlist = []

# Mの候補の素数を生成
def initM():
    global Mset, Mlist
    a = 10 ** 9
    for i in range(-10000, 10001):
        if isitprime(a+i):
            Mset.add(a+i)
    Mlist = list(Mset)
    return

# Bの累乗を生成
def genB(b, m, n):
    lst = [1]
    for i in range(0, n):
        lst.append((lst[-1]*b)%m)
    return lst

# ハッシュテーブル生成
def genH(b, m, s):
    lst = [0]
    for i in range(0, len(s)):
        a = ord(s[i]) - ord('a') + 1
        lst.append((b*lst[-1]+a)%m)
    return lst

# 部分文字列のハッシュ値を求める
def Hval(Hlist, Blist, M, L, R):
    return (Hlist[R] - Blist[R-L+1]*Hlist[L-1]) % M

# ハッシュを複数生成
def multihash(s):
    global Mset, Mlist
    if len(Mlist) == 0:
        initM()
    bm = {}
    for i in range(0, 5):
        b = randint(9900, 11000)
        m = Mlist[randrange(0, len(Mlist))]
        while (b, m) in bm:
            b = randint(9900, 11000)
            m = Mlist[randrange(0, len(Mlist))]
        Blist = genB(b, m, len(s))
        Hlist = genH(b, m, s)
        bm[(b, m)] = (Blist, Hlist)
    return bm

# 指定したb, mでハッシュ生成
def multihashconst(s, bmkey):
    h = {}
    for i in range(0, 5):
        b = bmkey[i][0]
        m = bmkey[i][1]
        Blist = genB(b, m, len(s))
        Hlist = genH(b, m, s)
        h[(b, m)] = (Blist, Hlist)
    return h

# ==========
# 【問題要約】
#
# ==========
# コードはここから書く
N, M = getints()
vlist = list(range(1, N+1))
A = intlist()
elist = []
for i in range(0, M):
    U, V = getints()
    elist.append((U, V))
graph = undirgraph(vlist, elist)
ans = []
for i in range(0, 2**N):
    mineexists = []
    now = i
    for j in range(0, N):
        mineexists.append(now % 2)
        now //= 2
    minecount = []
    for j in range(0, N):
        minecount.append(0)
    for j in range(0, N):
        v = vlist[j]
        lst = list(graph[v])
        for k in range(0, len(lst)):
            minecount[j] += mineexists[lst[k]-1]
    subflag = True
    for j in range(0, N):
        if minecount[j] != A[j]:
            subflag = False
    if subflag:
        ans.append(mineexists)
if len(ans) == 0:
    print('No')
else:
    print('Yes')
    chosen = randrange(0, len(ans))
    print(' '.join(map(str, ans[chosen])))
yukicoder

結果

ソースコード
