JOI2014 予選 F - 財宝

• 問題
• AC

ある財宝の取り方について、Annaの取った財宝の市場価値の総和を$x_A$、Brunoのそれを$x_B$とし、貴重度の総和も同様に$y_A, y_B$とする。$x_A$と$x_B$の差を一定以内におさめつつ、$y_A$と$y_B$の差を最大化する問題である。

総当たりすると間に合わないので、財宝の集合$S$を半分にわけて$S_1$と$S_2$とする。$S$からの財宝の取り方は$3^{|S|}$通りあるので、財宝の取り方全体の集合を$3^S$のように書くことにする。

ある取り方$t \in 3^{S_1}$について、二人の取り分の市場価値の差(Anna - Bruno)を$\Delta x$とし、貴重度の差を$\Delta y$とする。この時、$S_2$からの財宝のある取り方が有効であるのは、その市場価値の差が$[-D -\Delta x, D - \Delta x]$に入っている場合であり、その条件下で貴重度の差は大きければ大きいほどよい。したがって、$3^{S_2}$を市場価値の差の昇順でソートしておけば、区間$[-D -\Delta x, D - \Delta x]$に関して貴重度の差の最大値を求める問題になる。これは平衡二分木で処理できるし、スライド最大値でもできる。ソートが律速で計算量は${\mathcal O}(3^{N/2}N)$。

---

$3^{15} \simeq 1.4 \times 10^7$のソートが想定解の問題を初めて見た……