結果

問題 No.200 カードファイト！
ユーザー qwewe
提出日時 2025-05-14 13:22:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,014 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 53,848 KB
最終ジャッジ日時 2025-05-14 13:24:27
合計ジャッジ時間 2,465 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    N = int(input())
    A_count = int(input())
    B_full_orig = list(map(int, input().split()))
    C_count = int(input())
    D_full_orig = list(map(int, input().split()))

    # P_A: A's optimal permutation of their hand for one cycle.
    # To make A's overall N plays as strong as possible, A should use their
    # strongest cards more often if N is not a multiple of A_count.
    # So, P_A is B_full_orig sorted descending.
    P_A = sorted(B_full_orig, reverse=True)

    # P_C: C's optimal permutation of their hand for one cycle.
    # To make C's overall N plays as weak as possible (to help A win),
    # C should use their weakest cards more often.
    # So, P_C is D_full_orig sorted ascending.
    P_C = sorted(D_full_orig)

    # A_cards_for_N_matches: Multiset of N cards A will play over N matches.
    # A plays cards from P_A cyclically.
    A_cards_for_N_matches = []
    for i in range(N):
        A_cards_for_N_matches.append(P_A[i % A_count])
    
    # Sort A's N cards descending. A will try to win with its strongest cards first.
    A_cards_for_N_matches.sort(reverse=True)

    # C_cards_for_N_matches: Multiset of N cards C will play over N matches.
    # C plays cards from P_C cyclically.
    C_cards_for_N_matches = []
    for i in range(N):
        C_cards_for_N_matches.append(P_C[i % C_count])

    # Sort C's N cards ascending. This is the pool C draws from.
    # This list will be modified by removing cards.
    C_cards_pool = sorted(C_cards_for_N_matches)
    
    wins = 0
    
    # Iterate through A's cards, from strongest to weakest.
    for a_card in A_cards_for_N_matches:
        # C wants A to win with a_card. C must play a card c_card < a_card.
        # To maximize A's *total* wins, C should sacrifice its "best" (largest value)
        # card that a_card can still beat. This saves C's weaker cards for A's weaker cards.
        
        # Find the index `idx` for `a_card` if inserted into C_cards_pool (sorted asc).
        # `bisect_left(list, val)` returns an index `idx_insertion_point` such that:
        #  - all `list[j]` for `j < idx_insertion_point` have `list[j] < val`
        #  - all `list[j]` for `j >= idx_insertion_point` have `list[j] >= val`
        # So, cards in C_cards_pool at indices `0` to `idx_insertion_point - 1` are < a_card.
        idx_insertion_point = bisect.bisect_left(C_cards_pool, a_card)
        
        if idx_insertion_point > 0:
            # This means there is at least one card in C's pool that is < a_card.
            # C plays the card at C_cards_pool[idx_insertion_point - 1].
            # This is the largest card in C's pool that is strictly smaller than a_card.
            wins += 1
            C_cards_pool.pop(idx_insertion_point - 1)
        # If idx_insertion_point is 0, it means all cards in C's pool are >= a_card,
        # so a_card cannot win. This also handles the case where C_cards_pool is empty.
            
    print(wins)

if __name__ == '__main__':
    main()
0