結果

問題 No.161 制限ジャンケン
ユーザー maspymaspy
提出日時 2020-01-29 22:19:14
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 2,914 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 11,080 KB
実行使用メモリ 8,436 KB
最終ジャッジ日時 2023-10-14 07:45:53
合計ジャッジ時間 1,737 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
8,296 KB
testcase_01 AC 18 ms
8,284 KB
testcase_02 AC 18 ms
8,244 KB
testcase_03 AC 18 ms
8,308 KB
testcase_04 AC 18 ms
8,260 KB
testcase_05 AC 17 ms
8,264 KB
testcase_06 AC 18 ms
8,360 KB
testcase_07 AC 18 ms
8,420 KB
testcase_08 AC 18 ms
8,284 KB
testcase_09 AC 19 ms
8,304 KB
testcase_10 AC 18 ms
8,292 KB
testcase_11 AC 18 ms
8,436 KB
testcase_12 AC 18 ms
8,300 KB
testcase_13 AC 18 ms
8,268 KB
testcase_14 AC 18 ms
8,240 KB
testcase_15 AC 18 ms
8,380 KB
testcase_16 AC 18 ms
8,308 KB
testcase_17 AC 18 ms
8,232 KB
testcase_18 AC 18 ms
8,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappop, heappush

me = tuple(map(int,readline().split()))
S = read().rstrip().decode()

op = tuple(S.count(x) for x in 'GCP')

class MinCostFlow:
    """
    最小費用流。負辺がないと仮定して、BellmanFordを省略している。
    """
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink
        
    def add_edge(self, fr, to, cap, cost):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, cost, n2])
        self.G[to].append([fr, 0, -cost, n1])

    def min_cost(self, flow, negative_edge = False):
        if negative_edge:
            raise ValueError
        N = self.N; G = self.G; source = self.source; sink = self.sink
        INF = 10 ** 18
        prev_v = [0] * N; prev_e = [0] * N # 経路復元用
        H = [0] * N # potential
        mincost=0
        while flow:
            dist=[INF] * N
            dist[source]=0
            q = [source]
            mask = (1 << 20) - 1
            while q:
                x = heappop(q)
                dv = (x >> 20); v = x & mask
                if dist[v] < dv:
                    continue
                if v == sink:
                    break
                for i,(w,cap,cost,rev) in enumerate(G[v]):
                    dw = dist[v] + cost + H[v] - H[w]
                    if (not cap) or (dist[w] <= dw):
                        continue
                    dist[w] = dw
                    prev_v[w] = v; prev_e[w] = i
                    heappush(q, (dw << 20) + w)
            if dist[sink] == INF:
                raise Exception('No Flow Exists')
            # ポテンシャルの更新
            for v,d in enumerate(dist):
                H[v] += d
            # 流せる量を取得する
            d = flow; v = sink
            while v != source:
                pv = prev_v[v]; pe = prev_e[v]
                cap = G[pv][pe][1]
                if d > cap:
                    d = cap
                v = pv
            # 流す
            mincost += d * H[sink]
            flow -= d
            v = sink
            while v != source:
                pv = prev_v[v]; pe = prev_e[v]
                G[pv][pe][1] -= d
                rev = G[pv][pe][3]
                G[v][rev][1] += d
                v = pv
        return mincost

INF = 10 ** 9
graph = MinCostFlow(N=8, source=0, sink=7)
add = graph.add_edge
add(0,1,me[0],0)
add(0,2,me[1],0)
add(0,3,me[2],0)
add(4,7,op[0],0)
add(5,7,op[1],0)
add(6,7,op[2],0)
# あいこ
for n in [0,1,2]:
    add(n+1,n+4,INF,2)  # あいこ
    add(n+1,(n+1)%3 + 4,INF,0)  # かち
    add(n+1,(n+2)%3 + 4,INF,3)  # まけ

N = sum(me)
answer = 3 * N - graph.min_cost(flow=N)
print(answer)
0