各 \(1 \leq i \leq N\) について、青木君の \(i\) 回目の手順の際にはカードが \(2(N-i)+1\) 枚あります。 その中で番号が中央値であるようなカードの番号は \(N-i+1\) 以上 \(N+i\) 以下です。 よって、各 \(1 \leq i \leq N\) について、青木君は番号が \(N-i+1\) 以上 \(N+i\) 以下のカードを必ず \(i\) 枚以上持っています。

逆に、各 \(1 \leq i \leq N\) について番号が \(N-i+1\) 以上 \(N+i\) 以下のカードを \(i\) 枚以上含むようなカードの集合はすべて、 最終的に青木君が持っているカードの集合となりえます。これは、\(N\) についての帰納法により証明できます。 よって、この条件を満たすカードの集合の価値として考えられる最小の値を求めればよいです。 これは、以下のアルゴリズムにより求まります。

• \(i = 1, \ldots, N\) の順に以下の操作を行い、\(N\) 枚のカードを選ぶ。これらの価値の総和が求める値である。
  • 番号が \(N-i+1\) 以上 \(N+i\) 以下のカードであってまだ選ばれていないもののうち、価値が最小のものを選ぶ。

このアルゴリズムは優先度付きキューなどを用いることで \(O(N\log N)\) の計算量で実現できます。