Zenn
🔍

[鉄則A12] Printer

2024/05/02に公開
Ruby
AtCoder
競プロ
二分探索
tech

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_l

二分探索の応用問題。

問題を要約する

  • 印刷速度の異なるプリンタが N 台ある
  • K 枚目のチラシが印刷されるのは何秒後か？

問題を理解する

たとえば2つのプリンタがあったとき、

1 2
1秒で印刷できるプリンタ ○ ○
2秒で印刷できるプリンタ ○

3枚目が印刷できるのは 2 秒後になる。

例1を使った解き方

1 秒後から 8 秒後の表を作る。

1 2 3 4 5 6 7 8
P1 ○ ○ ○ ○ ○ ○ ○ ○
P2 ○ ○ ○ ○
P3 ○ ○
P4 ○ ○

求めたいのは 10 枚目である。目視で数えると 6 秒後が答えになる。どうやったらその 6 が求まるのだろうか？

まず L, R から中央の M を求めて M 秒以下の範囲の○を数える。10 と比べて足りなければ L を寄せる。寄せることで L, R の中央 M が右に移動し M 秒以下の範囲が広がる。多ければ逆に R を寄せる。

以上を L と R が同じになるまで繰り返すと、

L R M 枚数合計 次の動作
1 8 4 8 足りないので L を寄せる L = M + 1
5 8 6 12 多いので R を寄せる R = M
5 6 5 9 足りないので L を寄せる
6 6 6 12 L == R なので終わる

となり 10 枚目のチラシが印刷されるのは L (または R) の 6 秒後とわかる。

最初の R の値をどう決めるか？

制約に 1 <= A[i] <= 10**9 と書いてある。これは、いちばんぼろいプリンタでも 10**9 秒後には印刷できるということ。

1 2 3 ... ... ... ... 10**9
いちばんぼろいプリンタ ○

したがって R = 10**9 から始めるのでいい。

単純な実装 (TLE)

N, K = gets.split.collect(&:to_i)  # => [4, 10]
A = gets.split.collect(&:to_i)     # => [1, 2, 3, 4]
ans = (1..).find do |sec|
  sum = A.sum { |e| sec / e }      # => 1, 3, 5, 8, 9, 12
  sum >= K                         # => false, false, false, false, false, true
end
p ans                              # => 6

1, 2, 3 秒後と増やしつつ毎回調べる方法では TLE になる。

解説の模範解答風 (AC)

131 ms
N, K = gets.split.collect(&:to_i)  # => [4, 10]
A = gets.split.collect(&:to_i)     # => [1, 2, 3, 4]
l = 1
r = 10**9                          # => 1000000000
until l == r
  m = (l + r) / 2                  # => 500000000, 250000000, 125000000, 62500000, 31250000, 15625000, 7812500, 3906250, 1953125, 976563, 488282, 244141, 122071, 61036, 30518, 15259, 7630, 3815, 1908, 954, 477, 239, 120, 60, 30, 15, 8, 4, 6, 5
  sum = A.sum { |e| m / e }        # => 1041666666, 520833333, 260416666, 130208333, 65104166, 32552083, 16276041, 8138020, 4069009, 2034505, 1017253, 508626, 254313, 127158, 63578, 31788, 15895, 7946, 3975, 1987, 993, 496, 250, 125, 62, 30, 16, 8, 12, 9
  if sum >= K
    # 多いので R を寄せて狭める (←R)
    r = m                          # => 500000000, 250000000, 125000000, 62500000, 31250000, 15625000, 7812500, 3906250, 1953125, 976563, 488282, 244141, 122071, 61036, 30518, 15259, 7630, 3815, 1908, 954, 477, 239, 120, 60, 30, 15, 8, 6
  else
    # 足りないので L を寄せて広げる (L→)
    l = m + 1                      # => 5, 6
  end
  [l, r]                           # => [1, 500000000], [1, 250000000], [1, 125000000], [1, 62500000], [1, 31250000], [1, 15625000], [1, 7812500], [1, 3906250], [1, 1953125], [1, 976563], [1, 488282], [1, 244141], [1, 122071], [1, 61036], [1, 30518], [1, 15259], [1, 7630], [1, 3815], [1, 1908], [1, 954], [1, 477], [1, 239], [1, 120], [1, 60], [1, 30], [1, 15], [1, 8], [5, 8], [5, 6], [6, 6]
end
p l                                # => 6

10**9 の大きさであっても 30 回のループで求まる。

リファクタリング後 (AC)

126 ms
N, K = gets.split.collect(&:to_i)                      # => [4, 10]
A = gets.split.collect(&:to_i)                         # => [1, 2, 3, 4]
p (1..10**9).bsearch { |m| A.sum { |e| m / e } >= K }  # => 6

対象の配列がない場合は Array#bsearch_index のかわりに Range#bsearch を使う。

参考

Discussion