第14回日本情報オリンピック　予選６

2014年12月14日
情報オリンピック日本委員会

解説

単純な解法として，財宝の分配の仕方をすべて試すという方法が考えられる．各財宝について，「Anna が取る」「Bruno が取る」「2 人とも取らない」の 3 通りのいずれであるかを定めれば分配が決まる．しかし，分配の仕方は 3^N 通りとなるため，この方法は N が小さいデータに対してのみ短時間で答えを求めることができる (3³⁰ ≒ 2 × 10¹⁴ である)．

重要なアイデアは，全体の半分の財宝の分配の仕方 (最大 3¹⁵ 通り) をすべて試すことは比較的短時間で可能だということである．財宝全体をおよそ N/2 個ずつの 2 つの集合 S, T に分け，S, T それぞれの中での分配の仕方をすべて列挙する．ここで，各分配の仕方について，2 人が取る財宝の市場価値の合計の差と貴重度の合計の差のみを記録しておけばよいことに注意せよ．S の分配の仕方における市場価値の合計の差と貴重度の合計の差の組を (a₁, b₁), (a₂, b₂), ..., (a_P, b_P) とし (つまり，i 番目の分配の仕方では，Bruno が取る財宝の市場価値の合計から Anna のそれを引くと a_i で，Bruno が取る財宝の貴重度の合計から Anna のそれを引くと b_i である)，同様に，T の分配の仕方における市場価値の合計の差と貴重度の合計の差の組を (c₁, d₁), (c₂, d₂), ..., (c_Q, d_Q) とする．すると S の i 番目の分配の仕方と T の j 番目の分配の仕方を合わせたとき，市場価値の合計の差は a_i + c_j，貴重度の合計の差は b_i + d_j であるから，|a_i + c_j| ≦ D となるような (i, j) に対する b_i + d_j の最大値が本問の答えとなる．

D = 0 の場合，c_j = -a_i でなければならないので，i を 1 つ決めると c_j の値が定まる．よって，c_j の値から d_j としてありうる最大値への対応を (ハッシュテーブルなどを用いて) 管理しておく，といった方法で解くことができる．

一般の場合，c_j の値の範囲が指定されて d_j の最大値を求めることになる．そこでまず (a₁, b₁), (a₂, b₂), ..., (a_P, b_P) を a_i の昇順に，(c₁, d₁), (c₂, d₂), ..., (c_Q, d_Q) を c_j の昇順にソートしよう．i を 1 つ決めると，条件は |a_i + c_j| ≦ D すなわち -a_i - D ≦ c_j ≦ -a_i + D となる．これを満たす j は L(i) ≦ j ≦ R(i) のように書ける．ここで，L(1) ≧ L(2) ≧ ... ≧ L(P)，R(1) ≧ R(2) ≧ ... ≧ R(P) が成り立ち，範囲 L(i) ≦ j ≦ R(i) を左に伸ばして右から縮めると範囲 L(i + 1) ≦ j ≦ R(i + 1) が得られる．したがって，「値を 1 つ追加する」「値を 1 つ削除する」「最大値を答える」という操作を行えるデータ構造を用意すれば，i = 1, 2, ..., P の順に L(i) ≦ j ≦ R(i) の範囲での d_j の最大値を求めることができる．例えば，最大値の取得が可能な平衡二分木 (C++ の std::multiset など) を用いれば各操作を O(log Q) 時間で行える．その他，両端キューを利用することで各操作をならし O(1) 時間で行う解法もある．

P, Q が 3^N/2 程度のとき log P, log Q は O(N) なので，全体の時間計算量は O(3^N/2 N) となる．