皆様どうもこんにちは！ばるとーくです！
今回は問題「Made to order」を解説していきます！
問題
問題文
ばるとーく工務店では，オーダーメイドの机を製造している．
ある日，工務店にこのような依頼が入った．
$N$ 台の机を $D$ 日以内に納品してほしい．
親方曰く，机を $1$ 台製造するには，工程 $1$ → 工程 $2$ → 工程 $3$ をこの順に行う必要があるそうだ.
机 $i$ の製造には，工程 $1$，工程 $2$，工程 $3$ にそれぞれ $A_i, B_i, C_i$ 日を要する.
この工務店には，各工程を行うための専用の機械が $1$ 台あり，その機械は同時に $1$ 台の仕掛品(=製造途中の机)しか処理できない．
仕掛品たちは，製造することが決定次第ラインに乗せられるので，ある工程が完了した仕掛品は，次の工程の機械が空き次第すぐに作業を受ける.
そのため，各机をどのような順序で製造してもよいが，全工程が終わるまで作業を中断することはできない．
また，工程間で投入する順を入れ替えることはできない．例えば，工程 $1$ を先に開始させた仕掛品は工程 $2$ も先に開始させなければならない．なるべく最短日時で納品できるように製造順序を最適に選んだとき，すべての机を作業開始から $D$ 日以内に完成させることができるか判定せよ．
ただし，納品はすべての商品が完成するまでできず，かつ，すべての商品が完成した日に即時行われるものとする．制約
- $1 \leq N \leq 13$
- $1 \leq D \leq 5 \times 10^3$
- $1 \leq A_i, B_i, C_i \leq 100 \ (1 \le i \le N)$
- 入力値はすべて整数
解説
3機械フローショップのスケジューリング問題からの出題でございました！
（こういう問題競技プログラミングであんまり見ませんよねぇ～？）
競プロ典型ではないため，考察がうまくいかなかったり，実装にてこずった方が幾許かいらっしゃったかと思います．
そういった点や，難易度の落差が（前4問と比べて）大きかった点もあり，今回はサブタスク（部分点）制を採用しておりました．
各サブタスクによって，必要とされる解法が変わりますので，順に説明していきます．
サブタスク１
サブタスク $1$ では，すべての $(A, B, C)$ について，入力が以下の条件を満たしておりました．
$\min A_i \geq \max B_i \quad$ または $\quad \min C_i \geq \max B_i$
この場合は，Johnson法というアルゴリズムによって，以下のように解くことができます．
$(A_i + B_i,\ B_i + C_i)$ を考える．以降，前者を仮想機械 $X_i$，後者を仮想機械 $Y_i$ と呼ぶ．
配列 $Q$ を定義する．はじめ，$Q = \varnothing$ である．
まだ選ばれていないすべての $i$ について，$\min(X_i, Y_i)$ が最小値を取る $i$ を選ぶ．
もし $X_i$ が最小なら $Q$ の先頭につなぎ，そうでないなら $Q$ の末尾につなぐ．ただし，$X_i = Y_i$ の場合は $X_i$ が最小とみなす．
3 で該当する $i$ が複数ある場合は，以下のようにする．
$X_i$ が最小のとき：$Y_i$ がより小さいものを先に選ぶ（先頭からつなぐ）．
$Y_i$ が最小のとき：$X_i$ がより小さいものを先に選ぶ（末尾からつなぐ）．
3 ~ 5 を残りの $i$ について繰り返す．
はじめ $c_1 = c_2 = c_3 = 0$ とし，$i$ を $1$ から $N$ まで動かして次を計算する．
ここで $c_k$ は $k$ 番目の機械の作業終了日数を表す．
$c_1 \leftarrow c_1 + A_{Q_i}$
$c_2 \leftarrow \max(c_1, c_2) + B_{Q_i}$
$c_3 \leftarrow \max(c_2, c_3) + C_{Q_i}$
$c_3$ がすべての机を生産し終わるまでの日数となるので，これと $D$ を比較する．
計算量は $O(N \log N)$ です．
なお，Johnson法について，詳しくは，以下の記事で解説していますので，そちらをご覧ください．
サブタスク2
サブタスク $2$ では，サブタスク $1$ におけるような条件がないため，Johnson法や貪欲法では解けません．
なぜなら，例えば「機械 $1$ が最速でも，機械 $3$ が最遅で，全体でみるとそれ以外のどの機械よりも時間がかかる」のようなパターンが考えられるからです．
サブタスク $2$ を正解するなら，全探索を行うのが一番早いかと思います．
今回は「机を並べる順番」を考えるので，順列を考えましょう．
計算量は $O(N \cdot N!)$ で，この制約下では実行制限時間内に間に合わせることができます．
サブタスク3
サブタスク $3$ になると，全探索も実行制限時間内に間に合いません．
そこで，動的計画法(DP)を使って解くことになります．
ここで，「先に作り終えた机の集合」を $S$ とします．はじめ，$S = \varnothing$ です．
製造順を $1$ つ固定して机を $1$ 台ずつ末尾に足していくとき，各機械が作業を終える時刻を $c_1, c_2, c_3$ とすると，次の机 $i$ を足したときの更新は次のようになります．
$$c_1' = c_1 + A_i$$
$$c_2' = \max(c_2, c_1') + B_i$$
$$c_3' = \max(c_3, c_2') + C_i$$
$\max$ が入るのは，机が機械に届いても，その機械が前の机でまだ塞がっていれば待たされるからです．最後の机を足し終えた $c_3$ がメイクスパンです．
状態の持ち方の工夫
集合 $S$ が同じなら，その後の計算には $(c_2, c_3)$ のみが関係します．なぜなら，$c_1 = \sum_{i \in S} A_i$ は $S$ から一意に定まる（足し算なので順序に依らない）からです．
さらに，各時刻を 機械 $1$ の完了時刻 $c_1$ を基準にした「残り日数」 で持つと見通しが良くなります．
- $b = c_2 - c_1$ … 機械 $1$ が終わった時点で，機械 $2$ にあと何日分の仕事が残っているか
- $v = c_3 - c_1$ … 同じく，機械 $3$ の残り日数
こうすると，基準の $c_1 = \sum_{i \in S} A_i$ を状態から外し，最後にまとめて足す だけで済みます．これを使って，
$opt[S][b]$ ＝ 集合 $S$ をある順で流し，機械 $2$ の残りが $b$ のときの，機械 $3$ の残り $v$ の最小値
と定めます．はじめ $opt[\varnothing][0] = 0$ です．
連想配列（ハッシュマップ）で実装する場合はこれで十分ですが，配列で実装する場合は $opt$ すべてを初期化する必要がある点に注意です．
注意点ですが，機械 $3$（$v$）だけを最小化する $1$ 個の値を持つDPを書くと WAとなります．
機械 $3$ を最小にしても，それが最速とは限りません．$b$ が小さい状態と $v$ が小さい状態にはトレードオフがあり，どちらが最適かは次に足す机の $B_j, C_j$ に依存するためです．
そこで，$b$（機械 $2$ の残り）をキーにして，$b$ ごとに $v$ の最小値を保持します．
遷移
集合 $S$ の状態 $(b, v)$ に，次の机 $i \notin S$ を足します．機械 $1$ がさらに $A_i$ 日進む間に下流の残り日数が $A_i$ 減り，そこへ机 $i$ の分が積まれるので，新しい残り日数を $b', v'$ とすると
$$b' = \max(0, b - A_i) + B_i$$
$$v' = \max(b', v - A_i) + C_i$$
となります．これを $opt[S \cup \{i\}][b']$ に書き込みます．書き込みかたは実装方式で少し変わります．
- 配列実装：あらかじめ全エントリを $\infty$（十分大きな値）で初期化しておき，既存値との $\min$ で上書きします．
- ハッシュマップ実装：該当キーが未登録なら $v'$ をそのまま挿入し，登録済みなら既存値との $\min$ を取ります．
（$b'$ は「機械 $2$ の残り $b$ が $A_i$ 日で消化され，机 $i$ の工程 $2$ ぶん $B_i$ が積まれる」，$v'$ は「机 $i$ の工程 $3$ は，机 $i$ の工程 $2$ が終わる時刻と機械 $3$ が空く時刻の遅い方から始まり $C_i$ かかる」という意味です．）
全集合（$N$ 台すべてを表すビット）を $U$ とします．遷移し終えたら，$opt[U]$ の中で $v$ の最小値を取り，基準の $\sum_i A_i$ を足したものがメイクスパンの最小値です．
$$\min_{b} opt[U][b] + \sum_i A_i$$
これが $D$ 以下なら Yes，そうでなければ No です．
計算量
状態数は $2^N$ です．各状態 $opt[S]$ のサイズは，キー $b$ の種類数で抑えられます．$b = c_2 - c_1$ は $0$ 以上 $\sum_i B_i$ 以下の整数なので，相異なるキーは高々
$$|opt[S]| \le \sum_i B_i + 1 \quad (\le 100N + 1)$$
個です．遷移は各状態の各エントリについて机 $N$ 通りを試し，書き込みは 配列アクセス／ハッシュマップへの挿入いずれも $O(1)$（ソート不要）なので，全体で
$$O(N \cdot 2^N \cdot \sum_i B_i)$$
となり，実行時間内に間に合います．
ここで一点，「パレート最適点だけに絞らない」のがポイント です．$b$ をキーにして（支配される点も含めて）すべて持つからこそ，ソートなしのハッシュ挿入で上の計算量が 証明できます．もし $(c_2, c_3)$ のパレート最適点だけを取り出す実装にすると，縮約のためのソートで $\log$ が乗り，この計算量では（素直には）抑えられなくなります．
以上で解説を終わります．
想定解のコードをyukicoderの解説ページに置いておりますので，参考にしてください．
