指定の長さのシートを余りが最小になるように指定の範囲の長さに分割する

例のSNSで、こんな投稿を見つけた。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">ココナラのExcelツール作成で、長さxのシートを250m～200mの組み合わせでカットして、一番余りが少なくなる組み合わせパターンを求めるツールを作成してほしいとのご依頼。<br>1つのカットがなるべく最大（250m）になるものを優先して欲しいとのこと。<br><br>例）x = 1,820 のとき「250*4 + 220*1 + 200…</p>&mdash; りゅうりゅう@VBAer × ココナラPRO認定 (@blacklist_ryu) <a href="https://twitter.com/blacklist_ryu/status/1754112508951150900?ref_src=twsrc%5Etfw">February 4, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script> 

補足情報も合わせると、以下の条件のようである。

* 長さ x [m] のシートを、200～250m (1m刻み) ずつに分割する
* 余りを最小にする
* 余りが最小になる組合せの中で、長さが上限のものをなるべく多くする

さらに、以下の入出力例が提示されている。

|入力 (x)|出力|
|---|---|
|1,820 m|250 m × 4、220 m × 1、200 m × 3 (余り 0 m)|
|1,200 m|250 m × 4、200 m × 1 (余り 0 m)|
|600 m|200 m × 3 (余り 0 m)|
|512 m|250 m × 2 (余り 12 m)|

Excel でやるのは難しそうなので、普通のプログラミングの問題として考えてみた。
その結果、きちんとした証明はできていないが、以下のように考えるとよさそうだと思った。

1. まず、最大の長さのパーツを、合計が x 以上になる最小の数用意する
2. 長さの合計が x を超える分、貪欲に長さを縮めていく
   * 長さが上限のパーツを多くするためには、長さを縮めるパーツをなるべく少なくしたい。そのため、不足分をなるべく少ないパーツでカバーするため、パーツ1個で処理する分をなるべく多くする
3. 全てのパーツを縮めても合計を x にできなかった場合は、パーツを1個減らし、全てのパーツの長さを上限に設定する
   * この時点で「合計を x にできなかった」というのは、合計が x を超えているということであり、このままでは制約を満たせない
   * パーツは最初に合計が x 以上になる最小の数用意したので、1個減らすと合計の長さは必ず x を下回る
   * そのため、余りを最小にするには、合計の長さをなるべく大きくする。すなわち、パーツの長さを上限に設定する

この方針に基づいて、Python3 で実装してみた。

```py
import sys

x = int(sys.stdin.readline().rstrip())

minLength = 200
maxLength = 250

minToMax = maxLength - minLength

numMax = (x + maxLength - 1) // maxLength
short = maxLength * numMax - x
nonMax = []
while short > 0 and numMax > 0:
    if minToMax < short:
        nonMax.append(minLength)
        short -= minToMax
    else:
        nonMax.append(maxLength - short)
        short = 0
    numMax -= 1

if short > 0:
    numMax = x // maxLength
    nonMax = []

print("input: %dm" % x)
print()

for l in nonMax:
    print("%dm" % l)

if numMax > 1:
    print("%dm x %d" % (maxLength, numMax))
elif numMax == 1:
    print("%dm" % maxLength)

print ()
print("%dm left" % (x - maxLength * numMax - sum(nonMax)))
```

```text:入力例
1820
```

```text:出力例
input: 1820m

200m
200m
200m
220m
250m x 4

0m left
```

この方法でも解を求めることはできるが、パーツを1個ずつ縮めていくため、効率が悪い。
パーツを縮めるとき、最後以外に縮めるパーツは全て下限まで縮めるので、この処理をまとめることができる。
この改良を行ったのが以下のプログラムである。

```py
import sys

x = int(sys.stdin.readline().rstrip())

minLength = 200
maxLength = 250

minToMax = maxLength - minLength

numMax = (x + maxLength - 1) // maxLength
nonMinMax = None
short = maxLength * numMax - x

numMin = min(short // minToMax, numMax)
numMax -= numMin
short -= minToMax * numMin

if numMax > 0 and short > 0:
    numMax -= 1
    nonMinMax = maxLength - min(short, minToMax)
    short -= maxLength - nonMinMax

if short > 0:
    numMax = x // maxLength
    numMin = 0
    nonMinMax = None

print("input: %dm" % x)
print()

if numMin > 1:
    print("%dm x %d" % (minLength, numMin))
elif numMin == 1:
    print("%dm" % minLength)

if nonMinMax is not None:
    print("%dm" % nonMinMax)

if numMax > 1:
    print("%dm x %d" % (maxLength, numMax))
elif numMax == 1:
    print("%dm" % maxLength)

print ()
print("%dm left" % (x - maxLength * numMax - minLength * numMin - (0 if nonMinMax is None else nonMinMax)))
```

```text:入力例
1820
```

```text:出力例
input: 1820m

200m x 3
220m
250m x 4

0m left
```

この実装であれば、ループを使っておらず、表計算でも求めることができそうである。
この移植は読者への宿題とする。