Google Code Jam 2017 Round 1-C A

Dashboard - Round 1C 2017 - Google Code Jam

円柱型のパンケーキをN枚の中からK枚選択して、大きい順に重ねたとき底面を除いた表面積を最大化せよという問題。

まず側面を除いた面積は最大の半径を持つパンケーキの上面の面積に等しい。なので、パンケーキを側面の面積順でソートすると、大きい順にからK-1枚は常に選ぶ必要がある。残りの自由度はパンケーキ1枚なので、総当りする。

最初に選んだパンケーキK-1枚の中の最大の半径を取得しておき、総当たりのパンケーキの半径とmaxをとるとそれが上面の円の半径。この半径と、今見ているパンケーキの側面積と、元々選んだK-1枚の側面の面積が今見ているセットの総表面積になる。O(N)。