abc178f

NISHIO Hirokazu [Translate]
ABC178F
F - Contrast

from ABC178
ABC178F
リアルタイム
最も余ってる数から使っていけばいいだろ、と実装
24 WA
方針がダメだったのか後で確認
公式解説
範囲が重ならないようにずらすことで解が得られる
時を置いて考えたこと
一つ構築せよ問題
たくさんある解の中から構築しやすいものを見つけることが必要
貪欲法の証明パターン
「解があるならこの形の解がある」
まず一番出現回数が多い数に注目する
A: 出現回数CがNを超えてたら明らかに不可能
B: ちょうどNの時、重ならないように入れるしかない
この時、残りのマスの並びはどうであっても関係ない
C: それ以外の場合、N-Cマスを被らないように並べれば良い
N個出現する数がない限り配置できる
「出現頻度最大の数を選ぶ」の条件から、そのようなものはないことがわかる
実装
20分で実装、25分で手元バグ修正、提出して20WA
うーん、どういうパターンを見落としてるのだろう？
→for文なのにポインタをインクリメントした時にcontinue
ランダムテストでおかしな出力を見つけ、修正して53分で提出、6WA
ジャッジ結果から情報を得る
pythonassert Counter(BS) == Counter(ret)
return ret
6WA
pythonassert all(AS[i] != ret[i] for i in range(N))
む？6WA??
pythonassert len(ret) == N
むむ？これも6WA？
あ、そうか、
pythonassert 1 == 2
print("No")
16RE
つまり本当はNoを返すべきでないのに返してるケースがある
pythonif b_count[b] == 0:
    assert 1 == 2
    return
6RE
つまりこれが間違い
→AC
pythondef solve(N, AS, BS):
    from collections import Counter
    a_count = Counter(AS)
    b_count = Counter(BS)

    max_occur = 0
    when_max = None
    for i in range(N + 10):
        t = a_count[i] + b_count[i]
        if t > N:
            return
        if t > max_occur:
            max_occur = t
            when_max = i

    ret = []
    del a_count[when_max]
    del b_count[when_max]
    a_keys = list(a_count.keys())
    b_keys = list(b_count.keys())
    a_pointer = 0
    b_pointer = 0
    a_len = len(a_keys)
    b_len = len(b_keys)
    for _i in range(N - max_occur):
        a = a_keys[a_pointer]
        if a == when_max:
            a_pointer = (a_pointer + 1) % a_len
            a = a_keys[a_pointer]
        c = a_count[a]
        if c == 0:
            del a_count[a]
            a_pointer = (a_pointer + 1) % a_len
            a = a_keys[a_pointer]

        b = b_keys[b_pointer]
        while a == b or b == when_max or b_count[b] == 0:
            b_pointer = (b_pointer + 1) % b_len
            b = b_keys[b_pointer]

        ret.append((a, b))
        a_count[a] -= 1
        b_count[b] -= 1

    for b in b_count:
        for _i in range(b_count[b]):
            ret.append((when_max, b))
    for a in a_count:
        for _i in range(a_count[a]):
            ret.append((a, when_max))

    ret.sort()
    ret = [b for a, b in ret]
    return ret
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:25:26 PM[Edit]
Related Pages
