結果

問題 No.200 カードファイト!
ユーザー rpy3cpprpy3cpp
提出日時 2015-08-10 02:11:11
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,338 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 11,296 KB
実行使用メモリ 10,360 KB
最終ジャッジ日時 2023-09-21 17:31:54
合計ジャッジ時間 3,427 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 31 ms
10,120 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
権限があれば一括ダウンロードができます

ソースコード

diff #

import fractions


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 compress(lstA, lstB):
    '''数値のリスト lstA, lstB を入力として、ai, bi の大小関係に基づく座標圧縮を行う。
    ai > bi が成り立つか否かに着目している。
    ex. lstA = [1,3,7,9,10]  ->[1]   [3]       [7,9,10]
        lstB = [2,3,5,6,11]  ->   [2]   [3,5,6]        [11]
    変換後は、以下のようになる。
    freqA = [1,1,3]
    freqB = [1,3,1]
    '''
    lstA.sort()
    lstB.sort()
    lsts = [lstA, lstB]
    lens = [len(lstA), len(lstB)]
    freqs = [[], []]
    idxs = [0, 0]
    flag = 1
    while True:
        count = 0
        flag = 1 - flag
        while ((flag == 1 and lsts[0][idxs[0]] > lsts[1][idxs[1]]) or 
               (flag == 0 and lsts[0][idxs[0]] <= lsts[1][idxs[1]])):
            idxs[flag] += 1
            count += 1
            if idxs[flag] == lens[flag]:
                freqs[flag].append(count)
                freqs[1-flag].append(lens[1-flag] - idxs[1-flag])
                if len(freqs[1]) < len(freqs[0]):
                    freqs[1].append(0)
                return tuple(freqs)
        freqs[flag].append(count)


def take_firstN(lst, n):
    '''数値を要素とするリスト lst の先頭から、合計が n になるまで、要素をとってくる。
       lst の合計が n に満たない場合は、例外を出す。
    ex. take_firstN([2,3,0,4,1], 7) = [2, 3, 0, 2, 0]
        take_firstN([2,3,0,4,1], 100) = [2, 3, 0, 4, 1]
    '''
    ret = [0] * len(lst)
    cum = 0
    for i, a in enumerate(lst):
        if cum + a >= n:
            ret[i] = n - cum
            return ret
        ret[i] = a
        cum += a
    raise RuntimeError('sum(lst)={} must not be smaller than n={}.'.format(sum(lst), n))

def take_lastN(lst, n):
    '''take_firstN() の逆。lstの後ろから、合計がnになるまで要素をとってくる。
    '''
    ret = [0] * len(lst)
    cum = 0
    i = len(lst)
    for a in lst[::-1]:
        i -= 1
        if cum + a >= n:
            ret[i] = n - cum
            return ret
        ret[i] = a
        cum += a
    raise RuntimeError('sum(lst)={} must not be smaller than n={}.'.format(sum(lst), n))

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


def dfs(N, nB, Bs, nD, Ds):
    '''A, C の大きさによって場合分け。本当は、1つにまとめたい。。
    '''
    if nB >= nD:
        return dfsAC(N, nB, Bs, nD, Ds, [0] * len(Bs))
    else:
        return dfsCA(N, nB, Bs, nD, Ds, [0] * len(Bs))
        

def dfsCA(N, nB, Bs, nD, Ds, B_head):
    ''' nB < nD , N <= lcm(nB, nD) は保証されているとする。
    '''
    if N < nD:
        nD = N
        Ds = take_firstN(Ds, N)
    len_head = sum(B_head)
    if N < len_head:
        len_head = N
        B_head = take_lastN(B_head, N)

    # nD = len_head + n_body * nB + len_tail と分解する。
    n_body, len_tail = divmod(nD - len_head, nB)
    Bs_head_body = [h + b * n_body for h, b in zip(B_head, Bs)]

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

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


def dfsAC(N, nB, Bs, nD, Ds, D_head):
    ''' nB >= nD , N <= lcm(nB, nD) は保証されているとする。
    '''
    if N < nB:
        nB = N
        Bs = take_lastN(Bs, N)
    len_head = sum(D_head)
    if N < len_head:
        len_head = N
        D_head = take_firstN(D_head, N)

    # nB = len_head + n_body * nD + len_tail と分解する。
    n_body, len_tail = divmod(nB - len_head, nD)
    Ds_head_body = [h + d * n_body for h, d in zip(D_head, Ds)]

    # 最後の1区画のとき
    if N == nB:
        D_tail = take_firstN(Ds, len_tail)
        Dss = [hb + t for hb, t in zip(Ds_head_body, D_tail)]
        return count_win(Bs, Dss)

    # 境界部分を総当たりで試す。
    record = 0
    for D_tail in generate_tails(Ds, nD, len_tail):
        D_new_head = [d - t for d, t in zip(Ds, D_tail)]
        Dss = [hb + t for hb, t in zip(Ds_head_body, D_tail)]
        score = count_win(Bs, Dss)
        score += dfsAC(N - nB, nB, Bs, nD, Ds, D_new_head)
        if record < score: record = score
        if record == N: break   # 全勝なら探索打ち切り
    return record


def generate_tails(freq, n, k):
    '''頻度を表す数値のリスト freq から、合計 k 個の要素を抽出したリスト を列挙する。
    '''
    if n == k:
        yield freq[:]
        return
    f = freq[-1]
    begin = max(f + k - n, 0)
    end = 1 + min(f, k)
    for i in range(begin, end):
        for lst in generate_tails(freq[:-1], n - f, k - i):
            yield lst + [i]


def count_win(f0, f1):
    '''ai > bj となる組み合わせを、最大何個作れるかを返す。
    f0, f1 は、インデックス位置の数が何個あるかを表した頻度のリスト。
    f0 = [1,2,3] => 元の数字のリスト [0,1,1,2,2,2]    
    f1 = [2,1,3] => 元の数字のリスト [0,0,1,2,2,2]
    '''
    count = 0
    stock = 0
    for a, b in zip(f0[1:], f1[:-1]):
        stock += b
        if a > stock:
            count += stock
            stock = 0
        else:
            count += a
            stock -= a
    return count


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