ABC376 C - Prepare Another Box

はじめに

10/19開催のABC376のC問題の復習です。

問題文

$1$から$N$までの番号が付けられた$N$個のおもちゃと、$1$から$N−1$までの番号が付けられた$N−1$個の箱があります。
おもちゃ$i (1≤i≤N)$の大きさは$A_i$、箱$i (1≤i≤N−1)$の大きさは$B_i$です。

すべてのおもちゃを別々の箱にしまいたいと考えている高橋君は、今から以下の操作を順に行うことにしました。

1. 任意の正整数$x$を選んで、大きさ$x$の箱を$1$つ購入する。
2. $N$個のおもちゃそれぞれを、（元々あった箱と新しく購入した箱を合わせた）$N$個の箱のいずれかに入れる。 ただし、各おもちゃはそのおもちゃの大きさ以上の大きさを持つ箱にしか入れることはできず、また$1$つの箱に$2$つ以上のおもちゃを入れることもできない。

高橋君は、操作$1$で十分な大きさの箱を購入することで操作$2$が実行できるようにしたいですが、大きな箱ほど値段が高いため、可能な限り小さな箱を購入したいです。

高橋君が操作$2$を実行できるような$x$の値が存在するか判定し、存在するならばその最小値を求めてください。

自分の考え方

おもちゃと箱を大きい順に並べて、$1$つずつ比較して、
箱の方が大きければ問題なく詰められるので次の比較へ行く。
おもちゃの方が大きければ1回目は新しい箱を購入する。2回目は-1を返す。
最後まで箱に詰めれば1回目に買った箱を返す。

ABC376_C

def solve_box_packing(N, A, B):
    A.sort(reverse=True)
    B.sort(reverse=True)
    B.append(0)

    new_box_size = 0
    j = 0

    for i in range(N):
        if A[i] > B[j]:
            # 2つ目の新しい箱が必要
            if new_box_size > 0:
                return -1
            new_box_size = A[i]
        else:
            j += 1

    return new_box_size

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

result = solve_box_packing(N, A, B)
print(result)

おわりに

おもちゃと箱の並べ方に気づけば実装はそこまで難しくないです。
とか言いながらB.append(0)でこっそりエラー回避していたり。
精進します！