結果

問題 No.200 カードファイト！
コンテスト
ユーザー rpy3cpp
提出日時 2015-08-09 20:01:46
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 5,320 bytes
コンパイル時間 91 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-07-18 06:15:53
合計ジャッジ時間 2,302 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 2
other RE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import fractions
import itertools


def read_data():
    N = int(input())
    A = int(input())
    Bs = list(map(int, input().split()))
    C = int(input())
    Ds = list(map(int, input().split()))
    return N, A, Bs, C, Ds


def solve(N, A, Bs, C, Ds):
    '''
    A > C と仮定する。（そうでないときは、Bs, Ds の値の正負を反転すればよい。）
    Bs, Ds の最小公倍数で1ブロック分とする。これの繰り返しパターンの計算を避けるため、
    まずは、これを切り出す。
    残りの部分について、Bsの繰り返し回数 + Bsの余り、とDsの繰り返し回数_Dsの余り を処理する。
    Bsの余り部分は、Bsから大きいのを持ってくればよい。
    Dsの余り部分は、Dsから小さいのを持ってくればよい。
    Bs 1つ目について、Ds 何個か + Ds 先頭いくつか
    とする。先頭いくつかを選ぶパターンを全て総当たりする。
    Bs 2つ目について、Ds 残りいくつか+Ds何個か+Ds先頭いくつか
    とする。残りいくつかは、その前のステップで決まる。Ds先頭いくつかを先ほどと同じように総当たりする。
    '''
    Bs.sort(reverse=True)
    Ds.sort()
    minB = Bs[-1]
    maxD = Ds[-1]
    if minB > maxD: return N
    maxB = Bs[0]
    minD = Ds[0]
    if maxB <= minD: return 0
    lcm = A * C // fractions.gcd(A, C)
    blocks, residue = divmod(N, lcm)
    result = 0
    if blocks:
        result += blocks * dfs(lcm, A, Bs, C, Ds)
    if residue:
        result += dfs(residue, A, Bs, C, Ds)
    return result


def dfs(N, A, Bs, C, Ds):
    if A >= C:
        return dfsAC(N, A, Bs, C, Ds, [])
    else:
        return dfsCA(N, A, Bs, C, Ds, [])


def dfsCA(N, A, Bs, C, Ds, B_head):
    '''
        A < C , N <= lcm(A, C) は保証されているとする。
    '''
    if N == 0: return 0

    # 0 < N <= A < C, N <= len_head となるよう前処理
    if N < C:
        C = N
        Ds = Ds[:N]
    len_head = len(B_head)
    if N < len_head:
        len_head = N
        B_head = B_head[:]
        B_head.sort(reverse=True)
        B_head = B_head[:N]

    # C = len_head + n_body * A + len_tail と分解する。
    n_body, len_tail = divmod(C - len_head, A)
    Bs_head_body = B_head + Bs * n_body
    Bs_head_body.sort(reverse=True)    # B_tail とつなげた後にもsortするが、いちどやっておく。

    # 最後の1区画のときは、B_tail として、Bsの大きいのを与えて計算すればよい。
    if N == C:
        return count_win(Bs_head_body + Bs[:len_tail], Ds)

    # B_tail を総当たりで試す。
    record = 0
    for B_tail, B_new_head in generate_tails(Bs, A, len_tail):
        score = count_win(Bs_head_body + B_tail, Ds)
        score += dfsCA(N - A, A, Bs, C, Ds, B_new_head)
        if record < score: record = score
        if record == N: break   # 全勝なら探索打ち切り
    return record


def dfsAC(N, A, Bs, C, Ds, D_head):
    '''
        A >= C , N <= lcm(A, C) は保証されているとする。
    '''
    if N == 0: return 0

    # 0 < N <= C <= A, N <= len_head となるよう前処理
    if N < A:
        A = N
        Bs = Bs[:N]
    len_head = len(D_head)
    if N < len_head:
        len_head = N
        D_head = D_head[:]
        D_head.sort()
        D_head = D_head[:N]
    
    # A = len_head + n_body * C + len_tail と分解する。
    n_body, len_tail = divmod(A - len_head, C)
    Ds_head_body = D_head + Ds * n_body
    Ds_head_body.sort()    # D_tail とつなげた後にもsortするが、いちどやっておく。
    
    # 最後の1区画のときは、D_tail として、Ds の小さいのを与えて計算すればよい。
    if N == A:
        return count_win(Bs, Ds_head_body + Ds[:len_tail])
    
    # D_tail を総当たりで試す。
    record = 0
    for D_tail, D_new_head in generate_tails(Ds, C, len_tail):
        score = count_win(Bs, Ds_head_body + D_tail)
        score += dfsAC(N - A, A, Bs, C, Ds, D_new_head)
        if record < score: record = score
        if record == N: break   # 全勝なら探索打ち切り
    return record


def generate_tails(Ds, C, len_tail):
    '''長さ C のリスト Ds から、長さ len_tail のリストD_tail （とその残り）を列挙する。
    現状では、Ds の中に、同じ数字がある場合は、無駄な列挙が生じてしまう。
    '''
    for idxs_tail in itertools.combinations(range(C), len_tail):
        D_tail = [Ds[i] for i in idxs_tail]
        D_head = [d for i, d in enumerate(Ds) if i not in idxs_tail]
        yield D_tail, D_head


def count_win(Bs, Ds):
    '''
    Bs は降順、
    Ds は整列されているとは限らない。
    Bs と Ds のリストの長さは同じとなっている。
    Bs, Ds を適当に並び替えて、
    bi > di となる個数の最大値を返す。
    '''
    Ds.sort()
    Bs = Bs[:]
    Bs.sort(reverse=True)
    wins = 0
    for d in Ds:
        while Bs[-1] <= d:
            del Bs[-1]
            if not Bs:
                return wins
        wins += 1
        del Bs[-1]
        if not Bs:
            return wins
    return wins

if __name__ == '__main__':
    N, A, Bs, C, Ds = read_data()
    print(solve(N, A, Bs, C, Ds))
0