ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

POJ NO.3686 The Windy's

POJ プログラミング競技プログラミング

お題箱より。蟻本に載っている問題です。

3686 -- The Windy's

※ライブラリをC++98に対応させる気になれなかったのでACコードはありません。蟻本に載っているのでそちらを…

問題概要

$M$ 個のおもちゃ工場があり、 $N$ 個のおもちゃの注文を受けた。おもちゃ $i$ を工場 $j$ で製造すると $Z_{ij}$ の時間がかかる。1つの工場は、1つのおもちゃを製造し始めると終わるまで別のおもちゃの製造を始められない。

時刻 $0$ に全ての工場が同時に利用可能になったとして、おもちゃ $i$ の製造が完了した時刻を $T_{i}$ としたときの、 $T_{1}, ..., T_{N}$ の平均の最小値を求めよ。

制約

$1 \le N, M \le 50$
$1 \le Z_{ij} \le 100000$

解法

要求されているのは製造完了時刻 $T_{1}, ..., T_{N}$ の平均ですが、合計を最小化することを考え、答えとしては合計を $N$ で割って出力すれば良いです。以降、 $N$ 個のおもちゃの製造完了時刻の合計を「合計コスト」と呼びます。

ある1つの工場 $j$ で作るおもちゃの集合とその順番を決めたとします。製造の途中に休みを入れることは損でしかないので、ある1つのおもちゃの製造完了時刻は、自身を含むそれまでに製造したおもちゃの所要時間合計と等しいです。具体的にその工場で作るおもちゃが $k$ 個であり、それらの所要時間を製造順に $z_{1}, ..., z_{k}$ とすると、製造完了時刻の合計は

$z_{1} + (z_{1}+z_{2}) + (z_{1}+z_{2}+z_{3}) + \cdots + (z_{1} + \cdots + z_{k})$

となりますが、これはまとめ方を変えると

$kz_{1} + (k-1)z_{2} + (k-2)z_{3} + \cdots + z_{k}$

と書くことができます。

これはつまり、その工場で作るおもちゃの所要時間が、後に作るものから順番に $1$ 倍、 $2$ 倍、 $3$ 倍…という重み付きで合計コストに加算されるということです。

このことから1つの工場 $j$ を、以下のように1枠につきおもちゃ1つの製造枠に分けることができます。

工場 $j$ で最後から $1$ 番目に作る枠。おもちゃ $i$ を割り当てると $Z_{ij}$ の $1$ 倍が合計コストに加算される。
工場 $j$ で最後から $2$ 番目に作る枠。おもちゃ $i$ を割り当てると $Z_{ij}$ の $2$ 倍が合計コストに加算される。
…
工場 $j$ で最後から $N$ 番目に作る枠。おもちゃ $i$ を割り当てると $Z_{ij}$ の $N$ 倍が合計コストに加算される。

これを全ての工場について考えると、結局 $NM$ 個の枠に $N$ 個のおもちゃを最大1つずつ割り当てて合計コストを最小化するという問題になります。これは以下のようなグラフで最小費用流問題として解くことができます。

f:id:betrue12:20200910194510p:plain