解説


と置き、E問題の解説を前提とします。

方針


この問題では少し考察をすると、解く順番は関係なく、誰がどの 問を解くかのみが重要とわかります。

ここで、誰がどの 問を解くかを効率的に求めることを考えます。

グラフとして考えると、人と問題がそれぞれ分かれた二部グラフです。そして、この問題は誰がどの問題を解くかをマッチングさせることで解くことができます。

より詳細には、 人の回答者と、 問の問題を完全マッチングしたときのコストを最小化する問題として言い換えることができます。

二部マッチングについてわからない方は下の記事を読むと良いと思います。

けんちょんさんのわかりやすい記事

具体的な解法


上記の方針より、 人の回答者と 問の問題をマッチングしたときのコストを最小化すればいいことがわかりました。

これは、最小費用流を用いることで求めることができます。

以下の解説ではACLに含まれる MinCostFlow を用いることを前提とします。

まず、いわゆる超頂点を用いてフローの始点と終点を定義します。(始点を , 終点を とします)

あらかじめ、 から人 に流量 コスト の辺を 本ずつ、問題 から に流量 コスト の辺を 本ずつ貼っておきます。

入力時は、人 が問題 を解くのに 秒かかるとして、人 から問題 に流量 コスト の辺を貼ります。

"ドン!"

上の図のような感じです。 ただし、 の時とは辺を貼らないか、 としておきます。 このように辺が貼られているとき、 から だけ流し、 までにかかるコストが全ての問題を解くまでの時間と等しいです。 まで の流量がありかつ総コストが 以下であれば、達成可能です。

計算量


さて、計算量を見積もります。Min Cost Flowの計算量は

を流量、 を追加した辺の本数として

ACLのMinCostFlowのページ より

とあります。

ここで、 であるので、

より

より、このアルゴリズムは十分高速に動作します。

よってこの問題を で解くことができました。

おまけ


聞いたところによるとハンガリアン法で解けるらしいですね。
調べてみるとまんまでした…
計算量は だそうです。
すごいね。