解説
以下はわかりやすくするために とします。
考察
誰がどの順番で解くかは与えられています。 そこで、問題の順番を並び替え、人 が順に解くことを考えます。
愚直解法(TLE)
並び替え方を順列として全探索します。
全てを探索するには ほどかかります。
である時、 程度です。 程度であれば間に合いますが、この制約下では間に合いません。
AC解法
順列全探索では、明らかに最適でないケースも計算していたので、これを高速化します。
今まで誰がどの問題を解いたかの情報は不要です。
したがって、この問題は巡回セールスマン問題のようにbitDPで解くことができます。(ただし、最後にどの問題を解いたかなどの情報は不要です。)
今まで解いた問題の集合 において、それらの問題を解いたときの最短時間 とします。
問題を解く人は集合の定義より 番目の人であることがわかります。
(ただし、 である時は 番目です)
最初に と初期化し、配るDPで解く場合、
と更新することができます。
もらうDPでは
と更新すればよいです。
最終的な答えはどちらも です。
計算量は です。 よってこの問題を解くことができました。
ちょっとした話
この問題では実は解く順番は関係ありません。
なので、場合分けしていた部分を と置き換えることができ、実装をより簡単にすることもできます。
F問題について
F問題はこの問題と制約のみが異なるボーナス問題です。 (もちろんF問題でACを取れるコードではE問題でもACです。)
難易度は高いですが、ぜひ挑戦してみましょう！