指定の長さのシートを余りが最小になるように指定の範囲の長さに分割する #競技プログラミング

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

ココナラのExcelツール作成で、長さxのシートを250m～200mの組み合わせでカットして、一番余りが少なくなる組み合わせパターンを求めるツールを作成してほしいとのご依頼。
1つのカットがなるべく最大（250m）になるものを優先して欲しいとのこと。

例）x = 1,820 のとき「250*4 + 220*1 + 200…
— りゅうりゅう@VBAer × ココナラPRO認定 (@blacklist_ryu) February 4, 2024

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

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

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

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

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)))

入力例

出力例

input: 1820m

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

0m left

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

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)))

入力例

出力例

input: 1820m

200m x 3
220m
250m x 4

0m left

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