解説

以下はわかりやすくするために $N=2X$ とします。

考察

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

愚直解法(TLE)

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

全てを探索するには $O(N *N!)$ ほどかかります。

$X=8$ である時、$N\times N! \simeq 3.34\times10^{14}$ 程度です。$X\leq5$ 程度であれば間に合いますが、この制約下では間に合いません。

AC解法

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

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

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

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

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

(ただし、$|S|+1>X$ である時は $N-|S|$ 番目です)

最初に $dp[i]=\infty,\space dp[0]=0$ と初期化し、配るDPで解く場合、

$dp[S\cup\{u\}]=\min\limits_{u\notin S}(dp[S]+A_{\min(|S|+1,\space N-|S|),u},\space dp[S\cup\{u\}])$

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

もらうDPでは

$dp[S]=\min\limits_{u\in S}(dp[S\setminus\{u\}]+A_{\min(|S|,\space N-|S|-1),\space u})$

と更新すればよいです。

最終的な答えはどちらも $dp[2^N-1]$ です。

計算量は $O(N\space 2^N)$ です。 よってこの問題を解くことができました。

ちょっとした話

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

F問題について

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

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