AtCoder × Engineer Guild オンサイトコンテスト ～集結！高レート人材～予選（AtCoder Beginner Contest 424）F,G問題メモ

import random
from operator import xor


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


def solve(n, q, lines):
    fwt = FenwickTreeInjectable(n + 1, int, xor)
    ans = []
    for a, b in lines:
        a -= 1
        b -= 1
        zob = fwt.sum(a) ^ fwt.sum(b)
        if zob == 0:
            ans.append('Yes')
            x = random.randrange(0, 1 << 62)
            fwt.add(a, x)
            fwt.add(b, x)
        else:
            ans.append('No')
    return ans


n, q = map(int, input().split())
lines = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, lines)
print('\n'.join(ans))

必要条件（割り当てが存在する→★が成り立つ）は、延べ人数が足りなくなるので明らか。

十分条件がわかりづらい。（★が成り立つ→割り当てが存在）

選択する曲数 $k$ に対して数学的帰納法を用いる。
改めて命題を明確にすると、以下を示したい。3行目を真と仮定した時に4行目が真と言えればよい。

混乱ポイントがいくつかある。落ち着いて区別する。

• シンプルな帰納法は「$i=k-1$ のとき A が成り立つなら、$i=k$ の時も成り立つ」だが、今回は「$i=k-1$ のとき『AならばB』が成り立つなら、$i=k$ の時も成り立つ」なので、仮定が2種類登場している。
• 帰納法で証明する命題の中にさらに「任意の $1 \le k' \le k$ に対して○○ならば～」という条件があるので、「今、$k$ 未満の場合について考えているのは、帰納法の部分なのか、命題中の条件の部分なのか」が混ざりやすい。

$k=1$ の時、★が成り立てば割り当ても存在することは明らか。
$l \ge 2$ の時、$k \lt l$ では成り立っていると仮定すると $k=l$ でも成り立つことを示す。

曲を $B_1$ と その他の $l-1$ 曲 $(B_2,...,B_l)$ に分ける。
$B_1$ を $A_i$ の大きい方から割り当てた後、残り $(B_2,...,B_l)$ について割り当て可能か考える。

  Ai
l_↑___ ○○                 l=4  B1=5
  ｜    ■■■                   ○: l より大きいので割り当て不可
  ｜    □□□■■□             □: 割り当てられていない
  ｜    □□□□□□□□□       ■: B1が割り当てられている
  ｜    □□□□□□□□□□
  ＋--------------------------> 各アイドル

■を除いた列（$B_1$ が割り当てられた $i$ のみ $1$ 減らした $A$）を $A'=(A'_1,...,A'_N)$ とする。
$k=l$ に付いて★が成り立っている前提で、この $A'$ に $(B_2,...,B_l)$ を割り当てる方法があればよい。

ここに、帰納法の「$k=l-1$ で命題が成り立つ」を適用できる。
以下の仮定部分が真と言えれば、結論部分が真であることを示せる。

• 任意の $1 \le l' \le l-1$ について $\displaystyle \sum_{i=1}^{N}\min(A'_i,l') \ge \sum_{j=2}^{l'+1}B_j$ なら、割り当てが存在

ある $l'$ に対し $B_1$ をどこまで割り当てたかで場合分けする。

$B_1$ を割り当てられたのが全て $A_i \ge l'+1$ なメンバーなら、 $A'$ において残り $l'$ 曲以上踊れるメンバーが確実に $B_1$ 人以上いて、不等式が成立する。

  ↑Ai  ○                     残る Bj は B1 以下なので、
  ｜    ○○○                 ☆だけで割り当て可能。
l'｜___ ●●●●●○
  ｜    ☆☆☆☆☆□□□□     不等式の左辺: ☆+□の個数
  ｜    ☆☆☆☆☆□□□□□         V|
  ＋-------------------------  不等式の右辺: ☆の個数以下

$A_i \lt l'+1$ のメンバーに割り当てられた時を考える。

  ↑Ai  ○
  ｜    ○○○
l'｜___ ●●●●●●
  ｜    □□□□□□■■□
  ｜    □□□□□□□□□□
  ＋----------------------------

この時、$\displaystyle \sum_{i=1}^{N}\min(A'_i,l') = \sum_{i=1}^{N}\min(A_i,l'+1)-B_1$ が成立する。

ところで、「$k=l$ について★が成り立つ」という前提から、以下は真としていい。

• $\displaystyle \sum_{i=1}^{N}\min(A_i,l'+1) \ge \sum_{j=1}^{l'+1}B_j$

これを式変形・代入すると、示したい不等式の形にできる。

• $\displaystyle \sum_{i=1}^{N}\min(A_i,l'+1)-B_1 \ge \sum_{j=2}^{l'+1}B_j$
• $\displaystyle \sum_{i=1}^{N}\min(A'_i,l') \ge \sum_{j=2}^{l'+1}B_j$

よって、$B_1$ を割り当てた後の $A'$ に $(B_2,...,B_l)$ を割り当てる方法があると示せる。

def solve(n, m, aaa, songs):
    songs.sort(reverse=True)
    idols = [0] * (m + 2)
    for a in aaa:
        idols[1] += 1
        idols[a + 1] -= 1
    for i in range(m + 1):
        idols[i + 1] += idols[i]
    for i in range(m):
        idols[i + 1] += idols[i]

    total = sum(aaa)
    dp = [[-1] * (total + 1) for _ in range(m + 1)]
    dp[0][0] = 0
    for i in range(m):
        b, c = songs[i]
        for j in range(i, -1, -1):
            singable = idols[j + 1]
            for k in range(singable - b, -1, -1):
                if dp[j][k] == -1:
                    continue
                dp[j + 1][k + b] = max(dp[j + 1][k + b], dp[j][k] + c)

    return max(max(row) for row in dp)


n, m = map(int, input().split())
aaa = list(map(int, input().split()))
songs = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, aaa, songs)
print(ans)