2019年4月6日土曜日

ABC 123 D - Cake 123

ABC 123 D - Cake 123

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

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