ABC271C - Manga

解法1：二分探索

考え方

「$x$巻まで読むことができる」は，

• $x$巻以下で持っている本の種類の数
• (↑以外の本の数) // 2

の和が$x$以上であることと同値．

Editorial - KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271）

回答例

N = int(input())
A = list(map(int, input().split()))

ok = 0
ng = len(A) + 1

def f(x):
    need = set()
    for a in A:
        if a <= x:
            need.add(a)
    l = len(need)
    if l + (N - l) // 2 >= x:
        return True
    return False

while ng - ok > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)

内包表記を使うと，少し短く書ける．

need = set(a for a in A if a <= x)

積集合（集合の共通部分）を&で求めることもできる．

need = set(A) & set(range(1, x + 1))

解法2：消費する本の数に着目

考え方

賢い方法．消費量だけみれば良い．
Editorial - KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271）