E - Set Meal Editorial
by
Dispersion
別解
簡単のため、価格 \(a, b\) は降順にソートされているものとします。
\(l := \lceil{\sqrt{L+1} \rceil}\) とすると、最も価格の高い定食は
- 主菜の価格が \(a_1, a_2, \ldots, a_l\) のいずれか
- 副菜の価格が \(b_1, b_2, \ldots, b_l\) のいずれか
のどちらかを必ず満たします(両方の条件を満たさない任意の定食に対し、それ以上に高価な組み合わせが \(L+1\) 個以上存在するため)。
したがって、\((a_1, a_2, \ldots, a_l) \times (b_1, b_2, \ldots, b_M)\) または \((a_1, a_2, \ldots, a_N) \times (b_1, b_2, \ldots, b_l)\) という組み合わせを全探索すればよいです。
計算量は \(O((N+M) \sqrt{L} + (N+M)\log{(N+M)})\) 時間です。
さらに工夫することで \(O(L \log{L} + (N+M)\log{(N+M)})\) 時間の解法になります。
再び、価格 \(a, b\) は降順にソートされているものとします。また、インデックス \(i, j\) は 1-based とします。
自身以上に高価な組み合わせが \(L+1\) 個より多く存在する場合、その組み合わせは最も価格の高い定食になりえません。 したがって、\(i \times j \leq L+1\) を満たす \((a_i, b_j)\) の組だけ調べれば十分です。
このとき、ソートを除いた計算量は \(O(L \log{L})\) 時間になります。
posted:
last update: