ABC312 C - Invisible Hand (Diff:727 茶)の解説 [AtCoder][Python]

8/2: 修正、図の追加を行いました。

問題へのリンク https://atcoder.jp/contests/abc312/tasks/abc312_c

問題概要

りんご市場に N 人の売り手と M 人の買い手がいる。
i 番目の売り手は、A[i]円以上でならりんごを売ってもよいと考えている。
i 番目の買い手は、B[i]円以下でならりんごを買ってもよいと考えている。

この時、次の条件を満たすような最小の整数Xを求めよ。

条件: りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。

問題要約

(配列Aに含まれるX以上の数の個数) ≧ (配列Bに含まれるX以下の数の個数)となる最小のXを求めよ。

制約

1 ≦ N, M ≦ 2×10⁵
1 ≦ A[i], B[i] ≦ 2×10⁹

解説

下図は、入力例1をグラフにしたものである。緑は売る人の人数、オレンジは買う人の人数を表している。重なったところは少し濃くなっている。

この図では、X(リンゴの値段)を0から増やしていくと、売り手(緑)の人数は0人から徐々に増えていき、買い手(オレンジ)の人数は4人から減っていくことが分かる。途中で逆に減ったり増えたりすることはない。そのため、0円から値段を高くしていって売り手の人数が買い手の人数を上回ったその瞬間の値段が条件を満たす最小のXである。入力例1では110円が(売り手の人数)>=(買い手の人数)となる瞬間である。

(売り手)≧(買い手)となる瞬間のみが分かればよいので、人数が増減するタイミング(A[i]とB[i])だけに注目する。まず、それを知るためにAとBの要素を入れる空のリストLを作る。そのリストに、AとBの要素を、元々AとBのどちらにあったか分かるようにした上で入れていく。この時、Bに含まれる要素には全て1を足す。

これは、0円から値段を上げていった時、買い手は値段がB[i]円の時はまだ買うことができ、(B[i]+1)円になると買えなくなるので、人数が切り替わるタイミングはB[i]+1の時だからだ。一方、売り手は値段がA[i]円になった時に買えるようになり、そのタイミングで人数が切り替わるから変更する必要はない。

そして、その新しいリストLを昇順(小さい順)にソートする。また、AとBのカウント用の変数 cnt_a ,cnt_bを用意し、cnt_a = 0, cnt_b = Mとする。

そして、新しいリストを左から見ていく。

もし、要素がAに入っていたものだったら、売る人が1人増えたのでcnt_a += 1
もし、要素がBに入っていたものだったら、買う人が1人減ったのでcnt_b -= 1
もし、cnt_a ≧ cnt_bになったならその時の要素が答え

例:入力例1

上の動作は入力例1では下表のようになり、初めて a_cnt ≧ b_cnt となる110が答えである。 ※Bの要素には1を足してある。「A or B」は要素がAとBどちらに含まれているかを指す。

i	始め	0	1	2	3	4	5	6
要素	-	81	90	101	110	120	121	10001
A or B	-	B	A	B	A	A	B	B
a_cnt	0	0	1	1	2	3	3	3
b_cnt	4	3	3	2	2	2	1	0

実際は3以降は行わないので、110を出力したらその場でbreakまたはexit()を使って終了する。

実装例(Python)

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

L = []
for i in range(N):
    L.append((A[i], 0)) # 0はAに入っていたことを表す
for i in range(M):
    L.append((B[i]+1, 1)) # 1はBに入っていたことを表す

L.sort() # Lを要素の大きさでソート
cnt_a,cnt_b = 0, M

#eは要素、gはどちらに含まれるか(0ならA,1ならB)
for e, g in L:
    # Aに含まれているのなら
    if g == 0:
        cnt_a += 1
    # Bに含まれているのなら
    else:
        cnt_b -= 1

    #cnt_aがcnt_b以上になったら
    if cnt_a >= cnt_b:
        print(e) # 要素を出力
        exit() # その場で終了

おまけ…問題名の由来

「Invisible Hand」=見えざる手。Adam Smithが『国富論』で用いた語。経済は各個人の利益追求に任せておいても「見えざる手」に導かれ社会全体の利益につながると説いた。

https://eow.alc.co.jp/search?q=invisible+hand#resultsList-sectionより

「需要曲線」と「供給曲線」をイメージさせられる問題だった。