解説


以下はわかりやすくするために とします。

考察


誰がどの順番で解くかは与えられています。 そこで、問題の順番を並び替え、人 が順に解くことを考えます。

愚直解法(TLE)


並び替え方を順列として全探索します。

全てを探索するには ほどかかります。

である時、 程度です。 程度であれば間に合いますが、この制約下では間に合いません。

AC解法


順列全探索では、明らかに最適でないケースも計算していたので、これを高速化します。

今まで誰がどの問題を解いたかの情報は不要です。

したがって、この問題は巡回セールスマン問題のようにbitDPで解くことができます。(ただし、最後にどの問題を解いたかなどの情報は不要です。)

今まで解いた問題の集合 において、それらの問題を解いたときの最短時間 とします。

問題を解く人は集合の定義より 番目の人であることがわかります。

(ただし、 である時は 番目です)

最初に と初期化し、配るDPで解く場合、

と更新することができます。

もらうDPでは

と更新すればよいです。

最終的な答えはどちらも です。

計算量は です。 よってこの問題を解くことができました。

ちょっとした話


この問題では実は解く順番は関係ありません。
なので、場合分けしていた部分を と置き換えることができ、実装をより簡単にすることもできます。

F問題について


F問題はこの問題と制約のみが異なるボーナス問題です。 (もちろんF問題でACを取れるコードではE問題でもACです。)

難易度は高いですが、ぜひ挑戦してみましょう!