akmhmgc · akmhmgc · Oct 2, 2025 · oda · Oct 2, 2025 · tokuhirat
diff --git a/1011/step1.md b/1011/step1.md
@@ -0,0 +1,59 @@
+# step1 何も見ずに解く
+まず左から荷物を分類していって、すべてのパターンを計算することを思いついたが指数関数時間かかるので他の方法にする。
+絶対一発で荷物の範囲を決めることはできないので何回も調査することになる。
+求めたいのは、指定された日数で荷物を全て移動できる最小の最大積載量になる。
+この範囲は、weightsの最大値とwights全ての合計の間にあり、下限は1で上限が500 * 5 * 10^4 = 2.5 * 10^7になる。
+下限から愚直に+1して最小値を求めるのは効率が悪いので二分探索を使う。
+ある最大積載量で指定された日数で荷物を運び切れるかはweightsの長さをLとすると時間計算量O(L)で計算できる。
+よって、全ての荷物の合計をWとすると、時間計算量はO(L * log(W))で、Lは最大で5 * 10^4、Wも最大でおおよそ2.5 * 10^7なので1秒以内に間に合う
+
+- 求めたいもの(target)
+  - 荷物を全て移動できる最小の最大積載量
+- 範囲
+  - left
+    - leftより左はtargetを満たさない（指定された日数で荷物を運びきれない）
+  - right
+    - rightより右はtargetを満たさない（targetより大きい）
+- 終了条件
+  - left == rightとなるとき
+- middleは以下で分類する
+  - middleがtargetより左にある
+    - leftより左はtargetを満たさないのでleft = middle + 1に更新できる
+  - middleがtargetあるいはtargetより右にある
+    - rightより右はtargetを満たさないのでright = middleに更新できる
+- middleの出し方
+  - 常に区間を1狭めるためにはmiddle = (left + right) / 2
+
+
+```ruby
+# @param {Integer[]} weights
+# @param {Integer} days
+# @return {Integer}
+def ship_within_days(weights, days)
+    return 0 if weights.size.zero?
+
+    can_ship_within_days = lambda do |max_load_capacity|
+        package = 0
+        day_count = 1
+        weights.each do |weight|
+            package += weight
+            next if package <= max_load_capacity
+            day_count += 1
+            return false if day_count > days
+            package = weight
+        end
+        true
+    end
+    left = weights.max
+    right = weights.sum
+    while left < right
+        middle = (left + right) / 2
+        if can_ship_within_days.call(middle)
+            right = middle
+        else
+            left = middle + 1
+        end
+    end
+    left
+end
+```
diff --git a/1011/step2.md b/1011/step2.md
@@ -0,0 +1,45 @@
+# step2 他の方の解答を見る
+https://github.com/Satorien/LeetCode/pull/44
+
+step1のコードはdaysが0以下の時にweighsの合計を出してしまっていたので、-1を返すことにする。
+
+```ruby
+# @param {Integer[]} weights
+# @param {Integer} days
+# @return {Integer}
+def ship_within_days(weights, days)
+    return 0 if weights.size.zero?
+    return -1 if days <= 0 # 運べない
+
+    can_ship_within_days = lambda do |max_load_capacity|
+        package = 0
+        day_count = 1
+        weights.each do |weight|
+            package += weight
+            next if package <= max_load_capacity
+            day_count += 1
+            return false if day_count > days
+            package = weight
+        end
+        true
+    end
+    left = weights.max
+    right = weights.sum
+    while left < right
+        middle = (left + right) / 2
+        if can_ship_within_days.call(middle)
+            right = middle
+        else
+            left = middle + 1
+        end
+    end
+    left
+end
+```
+
+https://github.com/ruby/ruby/blob/5257e1298c4dc4e854eaa0a9fe5e6dc5c1495c91/array.c#L3543
+Rubyの`Array#bsearch`はオーバーフロー回避のために
+```
+mid = low + ((high - low) / 2);
+```
+と計算していて面白かった。
diff --git a/1011/step3.md b/1011/step3.md
@@ -0,0 +1,34 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+def ship_within_days(weights, days)
+    return 0 if weights.size.zero?
+    return -1 if days <= 0 # 運べない
+
+    can_ship_within_days = lambda do |max_load_capacity|
+        package_weight = 0
+        day_count = 1
+        weights.each do |weight|
+            package_weight += weight
+            next if package_weight <= max_load_capacity
+
+            day_count += 1
+            return false if day_count > days
+            package_weight = weight
+        end
+        true
+    end
+
+    left = weights.max
+    right = weights.sum
+    while left < right
+        middle = (left + right) / 2
+        if can_ship_within_days.call(middle)
+            right = middle
+        else
+            left = middle + 1
+        end
+    end
+    left
+end
+```
diff --git a/1011/step4.md b/1011/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正