リンク
問題 https://nikkei2019-qual.contest.atcoder.jp/
解説 https://img.atcoder.jp/nikkei2019-qual/editorial.pdf
C - Different Strokes
プレイヤは両者ともそれぞれ何らかの規則で料理にランク付けをして、それが高い順に選んでいくということはわかる。どういうスコア付けなのだろうか? 直接スコア関数を思いつくのは少し難しいので、一回比較関数を考えてみる。
料理 $i$ は高橋君が得る幸福度が $A_i$ 、青木さんが得る幸福度が $B_i$ だとする。今料理 $i$ と料理 $j$ の二つを比較して、どちらを取るべきか? まず高橋君の立場で考えると、料理 $i$ を取ると、次に青木さんに料理 $j$ を取られるし、逆の時は逆になることから、 $A_i + B_j$ と $A_j + B_i$ のうち大きいほうを取りたい、ということが分かる。正、負、ゼロのどれかを返すcompare関数風に書くと、 $$ (A_i + B_j) - (A_j + B_i) $$ で比較して降順にソートすればよいということが分かる。
同様に考えると、青木さんの比較関数は $ (B_i + A_j) - (B_j + A_i) $ となり、同じく降順にソートすればよいということが分かる。この二つの比較関数でソートしておいて、先頭から交互に取っていく、ただしすでに取られている場合は当然取れないのでその次の料理を取っていく、というような実装方針で行けそうだ。しかし、重複の検査があるのでちょっと面倒だ。うまくやらないとTLEするだろう。
ここでよく考えてみると、この二つの関数はどちらも同じものである。つまり項の順番を入れ替えると、 $$ (A_i + B_i) - (A_j + B_j) $$ となる。何ということはない、二人とも $ A_i + B_i $ の大きい順に料理を選ぶという単純な操作をしていたのである。不思議だねえ。
料理 $i$ は高橋君が得る幸福度が $A_i$ 、青木さんが得る幸福度が $B_i$ だとする。今料理 $i$ と料理 $j$ の二つを比較して、どちらを取るべきか? まず高橋君の立場で考えると、料理 $i$ を取ると、次に青木さんに料理 $j$ を取られるし、逆の時は逆になることから、 $A_i + B_j$ と $A_j + B_i$ のうち大きいほうを取りたい、ということが分かる。正、負、ゼロのどれかを返すcompare関数風に書くと、 $$ (A_i + B_j) - (A_j + B_i) $$ で比較して降順にソートすればよいということが分かる。
同様に考えると、青木さんの比較関数は $ (B_i + A_j) - (B_j + A_i) $ となり、同じく降順にソートすればよいということが分かる。この二つの比較関数でソートしておいて、先頭から交互に取っていく、ただしすでに取られている場合は当然取れないのでその次の料理を取っていく、というような実装方針で行けそうだ。しかし、重複の検査があるのでちょっと面倒だ。うまくやらないとTLEするだろう。
ここでよく考えてみると、この二つの関数はどちらも同じものである。つまり項の順番を入れ替えると、 $$ (A_i + B_i) - (A_j + B_j) $$ となる。何ということはない、二人とも $ A_i + B_i $ の大きい順に料理を選ぶという単純な操作をしていたのである。不思議だねえ。
