KLab株式会社 採用情報

予選A-D EMLauncher 解説

まず、障害物が原点を取り囲まないような場合を考えます。

図1

障害物それぞれに関して、実軸との偏角が最も小さい障害物を最初に破壊することから考えていきます。

図2

上記の場合、偏角の小さい1つを破壊する際、それのみを破壊するのは最適ではありません。

同時に破壊できる障害物があれば、可能な限り同時に他の障害物も破壊すべきです。

最初の1つを破壊した後も同様のことがいえるので、端から順に貪欲に破壊していけば良いということになります。

図3


次に、障害物が全体を取り囲むような場合を考えます。

図4

取り囲まない場合と違い、どの障害物から破壊すれば最適な解を得られるか特定できないことが問題となります。

しかし、偏角の順でソートしてしまえば、最初に破壊する障害物を全通り試してO(N^2)で解を得ることが出来ます。入力のサイズNは2000以下なので、タイムリミットにも充分間に合います。

なお、タイトルになっているEMLauncherは、KLabが公開している同名のテストアプリ配信ツールから来ていました。