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
まとめ
想定解はフローらしいが、自分はフロー流せない勢なので貪欲法しか思いつかなかった。あとでフローを流しておこう。