ALDS1_4_D: Allocation

この問題はやや難しいチャレンジ問題です。

出た
思考★★☆、実装★★☆だから水たまりの問題より少し実装が難しいということか

ぱっと見難しい最適化の問題かと思ったけど、ベルトコンベアーとトラックという
制限がついてるからなんとかなるのかな

• 荷物は出てきた順に積まなければならない
• いったん荷物を積んで出発したトラックにあとで荷物を載せ直すことはできない

てことでしょう
といってもいいアイデアがあるわけではない

まず心配なのは出てきた順に常にめいっぱい積めばいいかどうか
あとになってあそこであえて次のトラックに積んでおけば・・・みたいなことが
あるようだと面倒

・・・これはたぶん大丈夫だな
目いっぱいでいこう

で次は
nもkも100000まであるから計算量
なんどもやり直すわけにはいかない気がするけど・・・

Pは少なくとも一番重い荷物よりは大きいし、
少なくとも荷物の総重量÷トラックの台数よりも大きいとは言える
でもあとはやってみないとわからない気がするな・・・
一発でわかるようなやり方があるだろうか・・・

そんなやりかたは思いつかないので
Pを増やしながら試してみよう

from math import floor
from sys import stdin

def allocate(n, k, w, P):
    n_truck = 1
    load = 0
    for wt in w:
        if load + wt > P:
            n_truck += 1
            if n_truck > k:
                return False
            load = 0
        load += wt
    return True

def main():
    n, k = [int(x) for x in stdin.readline().split()]
    w = [int(x) for x in stdin]
    P = max(max(w), floor(sum(w) / k))

    while not allocate(n, k, w, P):
            P += 1
    print(P)

main()

予想どおりTLE

うーんなんだろうなあ
検索アルゴリズム入ってないし
使うとしたら二分探索だろうなあ・・・

あ、Pを二分探索すればいいのか
そういうことか？

Pの最大は何に取ればいいかな？
絶対確実に詰めるPは？
総重量そのものを使ったら贅沢すぎるかな？

まずやってみよう
修正はmain()だけ

def main():
    n, k = [int(x) for x in stdin.readline().split()]
    w = [int(x) for x in stdin]
    min_P = max(max(w), floor(sum(w) / k))
    max_P = sum(w)

    while min_P < max_P:
        mid_P = (min_P + max_P) // 2
        if allocate(n, k, w, mid_P):
            max_P = mid_P
        else:
            min_P = mid_P + 1

    print(min_P)

あっさりAC
二分探索すげー

解説は想定通り
けど二分探索で1足したりするところが細かく違う
この間やった二分探索と同じ書き方にしたんだけど
ケースバイケースなのかなあ？

そしてソース
最小と最大が0と100000*100000ってそこまでお大尽だったか
毎回半分になるんだから誤差の範囲？

手頃なところで試してみたところ
上のソースでは21回、0と100000*100000で34回
誤差と言えば誤差かな