Aggressive Cows
納屋には一直線上に厩舎が並んでおり、stalls[i] は厩舎 i の位置です。位置はすべて異なり、特定の順序にはなっていません。k 頭の牛をそれぞれ異なる k 個の厩舎に入れる必要があります。牛は近くに立つと争うため、最も近い2頭の牛の間隔をできるだけ広くしたいと考えています。
任意の2頭の牛の間の距離のうち、最小の距離として可能な最大値を返してください。
関数
- stallsinteger-array
- 異なる停止位置を、順序は問わず
- kinteger
- 配置する牛の数
- 戻り値integer
- 2頭の牛の間の距離の最小値として可能な最大値
制約
2 ≤ stalls.length ≤ 50000 ≤ stalls[i] ≤ 109-
stalls内のすべての位置は互いに異なります。 2 ≤ k ≤ stalls.length
例
- 入力
- stalls = [10, 1, 7, 4, 15]k = 3
- 出力
- 6
- 説明
- 1、7、15にいる牛同士の間隔は、それぞれ6と8です。間隔を7にすると失敗します。1の次の牛は10に置かれ、17以上の場所には牛小屋がありません。
- 入力
- stalls = [9, 3, 20, 5]k = 4
- 出力
- 2
- 説明
- 牛が4頭で牛舎が4つなら、すべての牛舎に1頭ずつ牛が入ります。牛舎を順に並べると3、5、9、20で、最も近い隣同士の3と5の間隔は2です。
- 入力
- stalls = [14, 2, 30, 22, 8]k = 2
- 出力
- 28
- 説明
- 2頭の牛は、列の両端にいるのが最適です。牛舎は2から30まで並んでいるので、牛同士は28離れています。
発展問題
屋台が円形に並んでいて、順番の最後の屋台も最初の屋台の隣にある場合、何が変わりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最適な答えはひとまず脇に置いておきましょう。間隔
gを与えられたとき、k頭の牛を配置して、どの2頭も少なくともg離れているかどうかを判定できますか？牛を左から順に配置し、各牛を前の牛から少なくとも
g離れた最初の牛舎に置きます。ある間隔で配置できるなら、それより小さい間隔でもすべて配置できます。厩舎の範囲を
k-1で割った値と1の間でgを二分探索します。貪欲法で少なくともk頭の牛を配置できる最大の間隔を維持します。
解説
間隔を決めて、次のように考えます。k 頭の牛を、どの2頭も少なくともその間隔だけ離して配置できるでしょうか？ ソート済みの牛舎を貪欲に1回走査すれば答えがわかります。間隔を広げていくと、答えは「はい」から「いいえ」へと一度だけ切り替わるため、二分探索で最後の「はい」を見つけられます。
並べ替えてから、各ギャップを順番に試す
正しいが、最大のテストでは終わらない
考え方
位置をソートします。最も近い2頭の牛は必ず隣り合うため、隣り合う牛のすべてのペアが少なくとも g 離れていれば、間隔 g は条件を満たします。
間隔を確かめるには、最も左の牛舎に牛を置き、その後は最後に置いた牛から少なくとも g 離れた牛舎ごとに牛を置きます。この貪欲な配置は、どの配置よりも多くの牛を置けます。条件を満たす配置を左から並べて比べると、貪欲法で置いた i 頭目の牛は、その配置の i 頭目の牛より右に来ることはありません。そのため、貪欲法では次の牛を遅くとも同じ位置までに置けます。
間隔1は必ず条件を満たすので、g = 2, 3, ... と試し、置ける牛が k 頭未満になる最初の間隔で止めます。最初の例では、間隔6なら3頭置けますが、間隔7では2頭しか置けないため、答えは6です。
牛が2頭で、牛舎が0と 10^9 にある場合、5000個の牛舎を約 10^9 回走査することになり、5 × 10^12 ステップかかります。
アルゴリズム
- 位置をソートします。
- 間隔
gのチェックを記述します。1頭目の牛をpos[0]に置き、その後、pos[i] - last ≥ gとなる各牛舎に牛を置き、牛の数を数えます。 gap = 1から始めます。gap + 1のチェックで少なくともk頭の牛を配置できる間は、gapに 1 を加えます。gapを返します。
def cowsPlaced(pos, gap):
count, last = 1, pos[0] # the first cow takes the leftmost stall
for p in pos[1:]:
if p - last >= gap:
count += 1
last = p
return count
def aggressiveCows(stalls, k):
pos = sorted(stalls)
gap = 1 # positions are distinct, so a gap of 1 always fits every cow
while cowsPlaced(pos, gap + 1) >= k:
gap += 1
return gapギャップに対する二分探索
考え方
すべての間隔が少なくとも g+1 である配置は、すべての間隔が少なくとも g でもあるため、判定結果は yes, ..., yes, no, ..., no と並びます。二分探索で最後の yes を見つけます。
lo = 1 から探索します。これは常に条件を満たします。hi は間隔の全長を k-1 で割り、小数点以下を切り捨てた値です。k 頭の牛は間隔の中に k-1 個の隙間を作るため、最小の間隔がこれより大きくなることはありません。条件を満たす場合は lo = mid とするため、mid は切り上げる必要があります。切り捨てると、lo = 5、hi = 6 の状態が永遠に繰り返されます。
最初の例では間隔の全長は 14 で、k = 3 なので、hi = 7 です。間隔 4 は条件を満たし、間隔 6 も条件を満たしますが、間隔 7 は条件を満たしません。範囲は 6 に収束します。
幅が 10^9 までの範囲は、5000 個の牛舎を約 30 回判定することで収束し、およそ 150,000 ステップです。
アルゴリズム
- 位置をソートします。
lo = 1とhi = (pos[n-1] - pos[0]) / (k-1)を設定し、小数点以下を切り捨てます。lo < hiの間、mid = lo + (hi - lo + 1) / 2を計算します。midでの貪欲法によるチェックで少なくともk頭の牛を配置できる場合は、lo = midを設定します。そうでない場合は、hi = mid - 1を設定します。loを返します。
def cowsPlaced(pos, gap):
count, last = 1, pos[0] # the first cow takes the leftmost stall
for p in pos[1:]:
if p - last >= gap:
count += 1
last = p
return count
def aggressiveCows(stalls, k):
pos = sorted(stalls)
lo = 1 # positions are distinct, so a gap of 1 always works
hi = (pos[-1] - pos[0]) // (k - 1) # k-1 gaps share the whole span
while lo < hi:
mid = lo + (hi - lo + 1) // 2 # round up so lo = mid always moves
if cowsPlaced(pos, mid) >= k:
lo = mid # mid fits, so the answer is mid or larger
else:
hi = mid - 1 # mid does not fit, so the answer is smaller
return lo
落とし穴と境界ケース
- ソートを省略する。ソートされていない
[10, 1, 7, 4, 15]でギャップが6の場合、チェックは10から始まり、それより後に6以上離れた牛舎が見つからないため、牛は1頭と報告されます。 - パス中に
lo = midを設定するのに、midを切り捨てる。hi = lo + 1になると範囲が縮まらなくなり、ループが終わりません。 - 牛の数がちょうど
k頭かどうかを判定する。ギャップが1のとき、最初の例では牛を5頭配置でき、3頭より多くてもギャップは有効です。count ≥ kを判定してください。 - 牛の数を0から始める。一番左の牛舎にいる牛も数えるため、数は1から始めます。
よくある質問3
アグレッシブ・カウズの時間計算量はどのくらいですか？
ソートには O(n log n)、二分探索には O(n log D) がかかります。ここで D は、厩舎の範囲を k-1 で割った値です。ソート済みのコピーを除けば、メモリ使用量は O(1) です。
なぜ最初の牛はいつも一番左の牛舎に入るのですか？
どのような配置でもよいので、その左端の牛を左端の牛舎に移動させます。その牛はほかの牛から遠ざかるだけなので、距離が縮まることはなく、最適な配置の中には左端の牛舎を使うものがあります。
答えに対する二分探索をどう見分けますか？
問題では、あることが可能となる最大値または最小値を求めます。最適な値を見つけるよりも、ある1つの値を確認するほうがずっと簡単で、値が大きくなるにつれて答えが変わるのは一度だけです。ここで値は間隔で、確認方法は貪欲な配置です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def aggressiveCows(stalls, k):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
stalls = [10, 1, 7, 4, 15] k = 3
期待される出力
6