これは、で機能する数学的な傾向の少ないソリューションですO(n)。
家（インデックス付けは0から始まります）を2つの互いに素なセットに分割しましょう：
F、「フロント」、人々がCCWを家まで歩くB、「戻る」、人々がCWを家まで歩く
pそして、プラントが建設される現在の位置を示す一軒家。
私は、画像に示されている例に基づいてイラストを作成しました。
慣例により、家の半分をに割り当てF、正確に1つ少ない家をに割り当てましょうB。
F6軒の家が含まれていますB5軒の家が含まれています
単純なモジュラー演算を使用すると、他の一般的な言語(p + offset) % 12とはまったく異なり、Pythonのモジュロ演算子の適切な実装のおかげで家に簡単にアクセスできます。
の位置を任意に選択すればp、水の消費量を簡単に判断できO(L)ます。
pのランタイムに到達するための別の位置に対して、これをもう一度やり直すことができますO(L^2)。
ただし、1つの位置だけシフトする場合、いくらか巧妙な観察を行うとp、新しい消費量を決定できます。住んでいる人の数（またはそれぞれ）によって、設定したときに消費量がどれだけ変化するかが決まります。（そしてそれ自体が変わるのでいくつかの修正）。私はこれを私の能力の限りを尽くしてここに描写しようとしました。O(1)FBFp' = p+1F
最終的に、合計実行時間はになりO(L)ます。
このアルゴリズムのプログラムは、投稿の最後にあります。
しかし、私たちはもっとうまくやることができます。セット間で家が変わらない限り、追加されるcsとsはゼロになります。wこれらのステップがいくつあるかを計算し、1つのステップで実行できます。
家は次の場合にセットを変更します：-家にいるとき-家の反対側にあるpときp
C次の図では、アルゴリズムがsとsを更新するための停止を視覚化していますW。強調表示されているのは、アルゴリズムを停止させる家です。
アルゴリズムは家から始まります（またはその反対です。理由は後で説明します）。この場合、それはたまたま家です。
C(B) = 3*1繰り返しますが、消費との両方がありC(F) = 2 * 1ます。p右に1つシフト4すると、に加算C(B)および減算1しC(F)ます。pもう一度シフトすると、まったく同じことが起こります。
同じ2組の家がそれぞれ近づいたり遠ざかったりする限り、Csの変化は一定です。
ここで、の定義をB少し変更します。これには、p！も含まれるようになります。（これは、アルゴリズムのこの最適化されたバージョンに関する上記の段落を変更しません）。
これは、次のステップに進むときに、繰り返し移動する家の重量を追加するためです。現在の位置にある家はp、右に移動すると離れていくのでW(B)、正しい加数です。
もう1つのケースは、家が離れなくなり、再び近づく場合です。その場合、 sは一方から他方に移動するCため、大幅に変化します。それは私たちが停止する必要があるもう一つのケースです。6*weightC
これがどのように、そしてなぜ機能するのかが明確になっていることを願っています。そこで、機能するアルゴリズムはここに残しておきます。不明な点がないかお尋ねください。
の上）：
import itertools
def hippo_island(houses, L):
return PlantBuilder(houses, L).solution
class PlantBuilder:
def __init__(self, houses, L):
self.L = L
self.houses = sorted(houses)
self.changes = sorted(
[((pos + L /2) % L, -transfer) for pos, transfer in self.houses] +
self.houses)
self.starting_position = min(self.changes)[0]
def is_front(pos_population):
pos = pos_population[0]
pos += L if pos < self.starting_position else 0
return self.starting_position < pos <= self.starting_position + L // 2
front_houses = filter(is_front, self.houses)
back_houses = list(itertools.ifilterfalse(is_front, self.houses))
self.front_count = len(houses) // 2
self.back_count = len(houses) - self.front_count - 1
(self.back_weight, self.back_consumption) = self._initialize_back(back_houses)
(self.front_weight, self.front_consumption) = self._initialize_front(front_houses)
self.solution = (0, self.back_weight + self.front_weight)
self.run()
def distance(self, i, j):
return min((i - j) % self.L, self.L - (i - j) % self.L)
def run(self):
for (position, weight) in self.consumptions():
self.update_solution(position, weight)
def consumptions(self):
last_position = self.starting_position
for position, transfer in self.changes[1:]:
distance = position - last_position
self.front_consumption -= distance * self.front_weight
self.front_consumption += distance * self.back_weight
self.back_weight += transfer
self.front_weight -= transfer
# We are opposite of a house, it will change from B to F
if transfer < 0:
self.front_consumption -= self.L/2 * transfer
self.front_consumption += self.L/2 * transfer
last_position = position
yield (position, self.back_consumption + self.front_consumption)
def update_solution(self, position, weight):
(best_position, best_weight) = self.solution
if weight > best_weight:
self.solution = (position, weight)
def _initialize_front(self, front_houses):
weight = 0
consumption = 0
for position, population in front_houses:
distance = self.distance(self.starting_position, position)
consumption += distance * population
weight += population
return (weight, consumption)
def _initialize_back(self, back_houses):
weight = back_houses[0][1]
consumption = 0
for position, population in back_houses[1:]:
distance = self.distance(self.starting_position, position)
consumption += distance * population
weight += population
return (weight, consumption)
O（L）
def hippo_island(houses):
return PlantBuilder(houses).solution
class PlantBuilder:
def __init__(self, houses):
self.houses = houses
self.front_count = len(houses) // 2
self.back_count = len(houses) - self.front_count - 1
(self.back_weight, self.back_consumption) = self.initialize_back()
(self.front_weight, self.front_consumption) = self.initialize_front()
self.solution = (0, self.back_weight + self.front_weight)
self.run()
def run(self):
for (position, weight) in self.consumptions():
self.update_solution(position, weight)
def consumptions(self):
for position in range(1, len(self.houses)):
self.remove_current_position_from_front(position)
self.add_house_furthest_from_back_to_front(position)
self.remove_furthest_house_from_back(position)
self.add_house_at_last_position_to_back(position)
yield (position, self.back_consumption + self.front_consumption)
def add_house_at_last_position_to_back(self, position):
self.back_weight += self.houses[position - 1]
self.back_consumption += self.back_weight
def remove_furthest_house_from_back(self, position):
house_position = position - self.back_count - 1
distance = self.back_count
self.back_weight -= self.houses[house_position]
self.back_consumption -= distance * self.houses[house_position]
def add_house_furthest_from_back_to_front(self, position):
house_position = position - self.back_count - 1
distance = self.front_count
self.front_weight += self.houses[house_position]
self.front_consumption += distance * self.houses[house_position]
def remove_current_position_from_front(self, position):
self.front_consumption -= self.front_weight
self.front_weight -= self.houses[position]
def update_solution(self, position, weight):
(best_position, best_weight) = self.solution
if weight > best_weight:
self.solution = (position, weight)
def initialize_front(self):
weight = 0
consumption = 0
for distance in range(1, self.front_count + 1):
consumption += distance * self.houses[distance]
weight += self.houses[distance]
return (weight, consumption)
def initialize_back(self):
weight = 0
consumption = 0
for distance in range(1, self.back_count + 1):
consumption += distance * self.houses[-distance]
weight += self.houses[-distance]
return (weight, consumption)
結果：
>>> hippo_island([0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2])
(7, 33)
