ABC 123 D - Cake 123

• 問題
• AC

$XY$通りの$A_i + B_j$を降順に並べた数列を$(\alpha_i)_{i \in [XY]}$とするとき、$XYZ$通りの$\alpha_i+ C_j$を大きいほうから$K$個出力すれば良いことになるが、後者については$\alpha_1, ..., \alpha_{K}$と$C_1, ..., C_Z$の組み合わせだけチェックすれば十分である。つまり、$A_i + B_j \ (i \in [X], j \in [Y])$を降順にソートして$(\alpha_i)$を得てから$\alpha_i + C_j \ (i \in [K], j \in [Z])$を降順にソートすれば答えになる。計算量は${\mathcal O} (XY \log (XY) + KZ \log (KZ))$。

もっと速い方法がありそうだと思ったが、コンテスト中には思いつけなかったので不全感が残った。解説にある優先度付きキューを使った${\mathcal O}(K \log K)$の方法はわかりやすかった。二分探索する方法については（それで計算量が大丈夫とすぐに判断できないあたりも含めて）もう少し考える時間が欲しい感じ。