コンテンツにスキップ

DOJ Beginner Contest 13 C - Measures

サイト
DOJ
コンテスト
DOJ Beginner Contest 13
問題
C - Measures

ある標準錘の重さを NN 個の都市で量った記録があります。ii 番目の都市の 11 ポンドは UiU_i グレインで、その都市は標準錘を AiA_i ポンド(11 ポンド未満は切り捨て)と記録しました。標準錘の実際の重さは、グレインで表すと正の整数です。残った記録がすべて正しくありうるように、除く記録の最小個数を求める問題です(1≤N≤2000001 \le N \le 200000、1≤Ui≤100001 \le U_i \le 10000、0≤Ai≤1000000 \le A_i \le 100000)。

標準錘の重さを WW グレインとすると、記録 ii が正しいのは ⌊W/Ui⌋=Ai\lfloor W / U_i \rfloor = A_i、つまり

UiAi≤W<Ui(Ai+1)U_i A_i \le W < U_i (A_i + 1)

のときです。さらに W≥1W \ge 1 なので、記録 ii が正しくなる WW は半開区間 [max⁡(UiAi,1),Ui(Ai+1))[\max(U_i A_i, 1), U_i (A_i + 1)) です。Ui=1,Ai=0U_i = 1, A_i = 0 のときはこの区間は空で、その記録は必ず除くことになります。

WW を固定すると、残せる記録は WW を含む区間の個数です。よって、NN 個の区間が最も多く重なっている点での重なりの数を cc とすると、答えは N−cN - c です。

区間の端点は 10910^9 程度まで大きくなるので、端点を座標圧縮してからいもす法で各点の重なりの数を求めます。重なりの数が変わるのは区間の左端だけなので、左端と右端の座標だけ見れば十分です。計算量は O(Nlog⁡N)O(N \log N) です。

W≥1W \ge 1 の条件を区間の左端に入れておくのが大事です。左端を UiAiU_i A_i のままにして、座標 00 での重なりの数を最大値の候補から除くだけだと、Ai=0A_i = 0 の記録の区間 [0,Ui)[0, U_i) が数えられなくなります。例えば N=1N = 1、(U1,A1)=(4,0)(U_1, A_1) = (4, 0) では、W=1W = 1 なら記録が正しいので答えは 00 ですが、座標 00 を除くと 11 になってしまいます。

Python
import bisect
N = int(input())
lr = []
comp = []
for i in range(N):
u, a = map(int, input().split())
l = max(u * a, 1)
lr.append((l, u * (a + 1)))
comp.append(l)
comp.append(u * (a + 1))
comp = sorted(set(comp))
imos = [0] * len(comp)
for l, r in lr:
imos[bisect.bisect_left(comp, l)] += 1
imos[bisect.bisect_left(comp, r)] -= 1
for i in range(1, len(imos)):
imos[i] += imos[i - 1]
print(N - max(imos))

comp が座標圧縮した端点の座標で、imos[i] は累積和をとったあと、点 comp[i] を含む区間の個数になります。空の区間は、同じ位置に +1+1 と −1-1 が入るので打ち消し合います。