[#1654]部分数列の和

❓ Question

📖 Before Start

この友達も探索で解決できるでしょう!そんな安易な考え.
最近はブルートフォスの問題を多く解いているので、何でも徹底的に探ろうという考えが生まれました.
今回の問題が存在するすべての状況の数を探索する結論を得,以下の設計を開始した.

✒️ Design Algorithm

今回の問題もきっと順番探索だと思いますが….あ.うん.
それぞれの長さの長い線があって、それらを一定の長さに切ったとき、何本の長い線が現れますか?
最終的に短くするとより多くの数の網線が現れ,長さと数をチェックし,探索を行った.
以下は筆者が問題を解く前に作成したアルゴリズム設計である.
K本のローカルネットワーク線を切断するには,N本のローカルネットワーク線を形成する.数量はN個以上に達することができる.
現在、K本のローカルエリアネットワークがありますが、長さはそれぞれ異なりますので、カットする必要があります.

の最初の行において、K, Nは、スペースを基準として連続的に入力される.

以降、K개의 랜선에 대한 길이はK個ずつ入力される.

文字を任意に長さを設定した後、接線ごとに現れる数を求めます.

で切断されたローカルエリアネットワークの数をすべて加算した値がN以上であるかどうかを求めます.

は、その中から最も長いハウジングを抽出して求める.

💻 Making Own Code

❌ Wrong Code

import sys

k, n = map(int, sys.stdin.readline().split())
data = [int(sys.stdin.readline()) for _ in range(k)]
max_length = 1

for length in range(1, min(data)+1):
    count = 0
    for line in data:
        count += line // length
    if count >= n:
        if length > max_length:
            max_length = length
    else:
        break
        
print(max_length)

しかし、このコードはタイムアウトを続け、壮絶な酸化を行った.PyPy3に提出されても、上のコードはタイムアウトし続け、戻ってくると残ります.
しかし、順番に値を検索しない場合、いったいどのようにして値を検出するのでしょうか.
こうして半日うろうろしてやっと結論が出たのは,バイナリ検索を用いて問題を解く方法である.

✅ Correct Code

import sys

k, n = map(int, sys.stdin.readline().split())
data = [int(sys.stdin.readline()) for _ in range(k)]
min_len, max_len = 1, max(data)

while min_len <= max_len:
    mid_len, count = (min_len + max_len) // 2, 0
    for line in data:
        count += line
    if count >= n:
        min_len = mid_len + 1
    else:
        max_len = mid_len - 1

print(max_len)

バイナリ探索の概念は初めて知ったが,時間の複雑さが本当に大幅に減少したことは否定できない.
上記の順序探索は,時間複雑度O(n)と比較して,バイナリ探索はO(logN)である.
これは,中間値に基づいてナビゲーション領域の半分を徐々に縮小する方法である.これはあまりにも人をだますのではないでしょうか.
皆さんも筆者の場合のように、間違いなく問題をよく解いてください.