ABC312 C問題の考え方
C - Invisible Hand の考え方を書きました。
問題の概要
N 人の売り手がいます。それぞれ A1, A2, … AN 円以上なら売ると言っています。
- A[1] 🙋 < 150円以上なら売るよ
- A[2] 🙋 < 160円以上なら売るよ
- …
- A[N] 🙋 < 152円以上なら売るよ
M 人の買い手がいます。それぞれ B1, B2, … BM 円以下なら買うと言っています。
- B[1] 🙋♂️ < 160円以下なら買うよ
- B[2] 🙋♂️ < 150円以下なら買うよ
- …
- B[M] 🙋♂️ < 155円以下なら買うよ
このとき、売り手の人数 >= 買い手の人数 を満たす金額の最小値を求めます。
業務でもありそうな要件ですね（妥当な価格を自動決定する、など）。
問題としてはシンプルですが、ACにはちょっと工夫が必要な楽しい問題だったので、考え方を書きました。
考え方
今回は非常に細かく書いています。適宜読み飛ばしてください。
まずは答えの状況を整理する
答えの状況を想像してみましょう。
「150円で売買する人～」と呼びかけた際、
- 売り手: 🙎 🙋 🙎 🙋 🙋 （合計3人）
- 買い手: 🙋♂️ 🙎♂️ 🙋♂️ 🙎♂️ 🙋♂️ （合計3人）
となるならば、 売り手の人数 >= 買い手の人数 を満たします。
さらに、150円未満のすべての金額において
- 売り手: 🙎 🙋 🙎 🙎 🙎 （合計1人）
- 買い手: 🙋♂️ 🙎♂️ 🙋♂️ 🙋♂️ 🙋♂️ （合計4人）
のように 売り手の人数 < 買い手の人数 ならば、”150円” という金額は「売り手の人数 >= 買い手の人数 を満たす金額の最小値」であり、これが答えとなります。
極端な金額についても考える
答えの状況はわかりました。しかし、答えとなる金額を一発で求めるのは難しそうです。
次は、極端な金額、つまり “0円” と “∞円” の場合について考えてみましょう。
「0円で売買する人～」と呼びかけると、
- 売り手: 🙎 🙎 🙎 🙎 🙎 （合計0人）
- 買い手: 🙋♂️ 🙋♂️ 🙋♂️ 🙋♂️ 🙋♂️ （合計5人）
売り手は当然、タダでは譲ってくれません。（厳密には、制約 1 ≤ A[i] によってこれが保証されます。）
買い手は無料で入手できるため、全員が手を挙げます。（厳密には、制約 1 ≤ B[i] によってこれが保証されます。）
「∞円で売買する人～」と呼びかけると、
- 売り手: 🙋 🙋 🙋 🙋 🙋 （合計5人）
- 買い手: 🙎♂️ 🙎♂️ 🙎♂️ 🙎♂️ 🙎♂️ （合計0人）
売り手は全員が手を挙げます。∞円ほしい。（厳密には、制約 A[i] ≤ 10^9 によってこれが保証されます。）
買い手は0人です。（厳密には、制約 B[i] ≤ 10^9 によってこれが保証されます。）
オークションのように金額を釣り上げていくと、売り手は0人からN人（全員）まで徐々に増えていき、買い手はM人から0人（全員）まで徐々に減っていきます。明らかに、この途中に 売り手の人数 < 買い手の人数 から 売り手の人数 >= 買い手の人数 に変わる瞬間が存在し、その瞬間の金額が答えとなります。
この様子をイメージしつつ、実装を考えていきましょう。
単純な実装とその問題点
上記の考え方をコードで表現すると、次のようになります。
for price in range(0, 10**10):
# 売り手の人数を数える
num_seller = 0
for seller_i in range(0, N):
if A[seller_i] >= price:
num_seller += 1
# 買い手の人数を数える
num_buyer = 0
for buyer_i in range(0, M):
if B[buyer_i] <= price:
num_buyer += 1
# 売り手の人数 >= 買い手の人数 となったら、そのときの金額を出力して終了
if num_seller >= num_buyer:
print(price)
break
正しい答えを出力することはできますが、この実装には計算量の問題があります。
ここでも極端な値を考えてみます。大きい値が答えになる場合として、答え = 10^9 のケースを考えます。
この場合、外側のforループは、10^9回繰り返されます。
さらに、そのループの内部で全ての売り手と買い手に対するforループがあります。内側のループは最大で Nmax + Mmax = 4*10^5 回繰り返されます。
つまり、最もループ数の多い（処理に時間のかかる）ケースでは、 10^9 * 4*10^5 = 4*10^14 回ものループが発生します。これでは、”制限時間2秒”に間に合いません。
処理の無駄を省き効率化する
ここからは、処理の無駄を省き、計算量を減らす方法を考えていきます。
方針は様々ありますが、この記事では先程のオークション風のイメージを活かして改善していきます。
答えの候補を絞りこむ
先程の実装では、0円から10^9円までの全ての金額を候補として考え、それぞれについて売り手と買い手の人数を数えていました。
“明らかに答えとならない金額”を除外できれば高速になるでしょう。
仮に売り手も買い手も基準価格が 10000円～11000円 の間だったとしましょう。
売り手は 0円～10000円まで、0人のままです。
買い手は 0円～10000円まで、全員挙手のままです。
これなら、オークションを0円から始める必要はなく、10000円…“動き”のある最初の価格から開始しても良さそうです。
次に、基準価格が 10000円～11000円の間 と 30000円～31000円 の間 の二箇所に集中していて、ここ以外では全く動きがないとしましょう。
このとき、20000円付近では売り手も買い手も人数が一切変動しません。答えの候補は人数が変動する瞬間でした。20000円付近はスキップしてしまってよい、ということになります。
一般化すると、買い手・売り手どちらも人数が変動しない金額は全てスキップして良い、ということになります。
具体的には、
売り手の人数変動は、売り手が手を挙げる瞬間に発生します。「a円以上で売る」なら、a円にて人数が +1 されます。 買い手の人数変動は、買い手が手を下げる瞬間に発生します。「b円以下で買う」なら、b円ではなく (b+1)円にて人数が -1 されます。 （ミスしやすいポイント）
イベントとして管理する
オークションの金額を上げる度に「A1さん、どうしますか？」「A2さん、どうしますか？」「」… と聞いていくのは非効率的です。
ここではイベントとして捉え、楽かつ効率的に処理できるようにします。
例えば、売り手 A1 は 150円以上で売るとします。
これをオークションのイメージでイベントとして表現すると、次のようになります。
- 条件: 価格が150円に到達したとき
- 内容: 売り手が1人増える
買い手についても同様です。買い手 B1 は150円以下で買うという場合、
- 条件: 価格が151円に到達したとき
- 内容: 買い手が1人減る
となります。
このイベント達を時系列順にシミュレーションすれば、売り手・買い手の人数の変動を効率的に管理できます。
[
{
"price": 150,
"type": "seller",
"diff": 1
},
{
"price": 151,
"type": "buyer",
"diff": -1
},
...
]
実装
配列A, Bからイベント達を作り、それらを時系列順にソートします。
イベントを順に見ながら売り手・買い手の人数変動をシミュレーションし、条件を満たした瞬間の金額を答えとして出力します。
events = []
for a in A:
events.append((a, 1, 0))
for b in B:
events.append((b+1, 0, -1))
events.sort()
#
seller = 0
buyer = M
for event in events:
price, seller_diff, buyer_diff = event
seller += seller_diff
buyer += buyer_diff
if seller >= buyer:
print(price)
return
解答例
- Python 3.8.2 (570 ms)