roiti46's blog

主に競プロ問題の解説を載せてます

yukicoder No.200 カードファイト!

フローなんて知らないです。

問題はこちら

問題

AさんはA枚のカードからなる手札B、CさんはC枚のカードからなる手札Dを持っている。各カードには数字が1つ書かれている。
2人は、1ターンごとに場に手持ちのカードを1枚出して数字が大きい方を勝ちとするゲームをNターン行う。ゲームの途中で手札が無くなったら場に出ている自分のカードをすべて回収してゲームを続行する。
Aさんの勝ち数が最大になるように2人が話し合いながらカードを出すとしたとき、Aさんの勝ち数がいくらになるかを答えよ。

解法

貪欲法で解ける。
Aさんが手持ちの最大のカードを出してもCさんに勝てないときは、Aさんは手持ちで最小のカードを出し、Cさんは手持ちの最大のカードを出す。
Aさんが勝てるときは、CさんはAさんの出すカードよりも小さな手持ちのカードのうちから最大のカードを出していく。こうするとAさんは勝ちの数を最大化(Cさんは負けの数を最大化)することができ、答えが得られる。

import bisect
N = int(raw_input())
A = int(raw_input())
B = sorted(map(int, raw_input().split()))
C = int(raw_input())
D = sorted(map(int, raw_input().split()))

ans = 0
b = B[:]
d = D[:]
for i in xrange(N):
    if i % A == 0: b = B[:]
    if i % C == 0: d = D[:]
    if max(b) <= min(d):
        b.pop(0)
        d.pop()
        continue
    for j in xrange(len(b)):
        pos = bisect.bisect_left(d, b[j])
        if pos > 0:
            b.pop(j)
            d.pop(pos - 1)
            break
    ans += 1
print ans

まとめ

想定解はフローらしいが、自分はフロー流せない勢なので貪欲法しか思いつかなかった。あとでフローを流しておこう。

広告を非表示にする