問題概要
料理の材料が $n$ 種類あり，$i$ 番目の材料は $Q_i$ グラムある．
これから $2$ 種類の料理を作ることができる．料理 A は，$1$ 人前を作るのに材料 $i$ ($1 \leq i \leq n$) を $A_i$ グラム消費する．料理 B は，$1$ 人前作るのに材料 $i$ ($1 \leq i \leq n$) を $B_i$ グラム消費する．どちらの料理も，整数人前しか作れない．
今ある材料から，最大で合計何人前の料理を作ることができるか？
制約
- $1 \leq n \leq 10$
- $1 \leq Q_i \leq 10^6$
- $0 \leq A_i, B_i \leq 10^6$
- $\exists i, A_i > 0$
- $\exists i, B_i > 0$
解法
「基本は全探索」と言われる[誰によって？]ように，まずは全探索から考えてみます．本問において自由度がどこにあるかというと，それぞれの料理を何人前ずつ作るかという部分です．しかしながら，2 つの料理を何人前ずつ作るかの組合せを全て試そうとすると，入力によっては $\Theta( ( \max Q )^2 )$ 個の組合せを考慮する必要があって，これをすると TLE します．よって，より高速な方法を考える必要があります．
では，両方の料理の作る量を全て試すのを諦めて，片方の料理を作る量だけを試すことにするとどうでしょうか．この場合，最大でも $\Theta( \max Q )$ 通りのパターンを扱えればよいので，各パターンについての処理がそれなりに高速なら AC できます．
料理 A を作る量を全て試すことにして，料理 B についてはどうすればよいかを考えてみます．料理 A を $x$ 人前作るとすると，各材料 $i$ を $x A_i$ グラムずつ消費します．残る材料の量を表す列を $Q'$ とすると，各項は $$Q'_i = Q_i - x A_i$$ で求まります．ここで，$Q'$ に負の値が含まれていれば，無い材料を使ってしまっていることになるのでそのときの $x$ は不適です．以降，$Q_i \geq 0$ とします．
料理の総量を最大化したかった訳ですから，料理 B については残った材料 $Q'$ で作れる範囲で最大の量を作るのが最適となります．必要な各材料 $i$ ($B_i > 0$ な $i$) について考えると $\left\lfloor \frac { Q'_i } { B_i } \right\rfloor$ 人前分が残っていることになり，この最小値が料理 B を作れる量となります．あとは $x$ との和をとれば作れる料理の総量となり，可能な全ての $x$ について和の最大値をとれば答えが求まります．
計算量
この解法では，$x$ としてあり得る範囲は $0 \leq x \leq \max Q$ です．この範囲内の整数 $x$ について $Q$ なり $Q'$ なりを定数回舐め，各要素に軽い処理をするので，各 $x$ に対し $\Theta( n )$ 時間ずつかかります．よってトータルでは $\Theta( n \max Q )$ 時間となります．
コード
main = do getLine qs <- readInts as <- readInts bs <- readInts print $ maximum $ do i <- [ 0 .. maximum qs ] let qs' = zipWith (-) qs $ map ( i * ) as guard $ all ( 0 <= ) qs' let j = minimum $ map ( uncurry div ) $ filter ( ( /= 0 ) . snd ) $ zip qs' bs return $ i + j
