Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2012-12-28

YUHA presents C83 新刊 『競技プログラミング The Boss Rush!!!』 予告コンテスト 18:02 YUHA presents C83 新刊 『競技プログラミング The Boss Rush!!!』 予告コンテスト - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - YUHA presents C83 新刊 『競技プログラミング The Boss Rush!!!』 予告コンテスト - nodchipのTopCoder日記 YUHA presents C83 新刊 『競技プログラミング The Boss Rush!!!』 予告コンテスト - nodchipのTopCoder日記 のブックマークコメント

2012年12月28日に開催した「YUHA presents C83 新刊 『競技プログラミング The Boss Rush!!!』 予告コンテスト」の部分点の解説です。満点の解説はコミックマーケット83 3日目 12月31日(月) 東地区“Y”ブロック-02b で頒布予定です。

A. Revenge of Voronoi - ボロノイの逆襲

50点は全探索で取れます。深さ優先探索で母点の候補を配置していき、実際に離散ボロノイ図を生成して入力と一致するかどうかを試します。最悪ケースはN個の文字がそれぞれNマス専有する場合で、時間計算量は深さ優先探索O(N^N)ボロノイ図の生成にO(N^3)かかり、合わせてO(N^{N+3})となります。これはN=8の場合にすら計算量が足りていないように見えます。しかし、実際には比較的速く解にたどり着くため、制限時間に間に合います。

別解として乱択で取ることもできるようです。正解する確率は(解の数)/8^8ですので、運が良いと通せるようです。

100点は全探索+枝刈りで取れます。文字の若い順に探索していき、仮決定した文字の領域が他の文字に上書きされてしまったら枝を刈る等の追加で取れます。50点のソースコードに少し書き足すだけです。

B. Sun and Moon - 秘密結社太陽と月の団

175点と200点は問題のモデル化ができれば取れます。モデル化については同人誌で解説いたします。25点分はあるテクニックを知っているかどうかの差で、そこそこ多くの競技プログラマーが知っているテクニックだと思います。

C. Dendrogram - 樹形図

50点はN!通り試すだけで取れます。あるleafの並びを作り、下から順に併合クエリを調べ、併合する垂直線分の間に関係のない集合が混ざっていないかどうかを調べます。この処理を行う際、Union-Findを使うと若干楽になると思います。

D. Psychic Accelerator - とある超能力の物体加速器

50点は線分が1本しかありません。半分の距離まで最大加速し、もう半分は最大減速です。問題文で与えられている式を使うと解けます。

125点はコーナーが一つだけあります。こちらの解き方は同人誌をご覧ください。

E. Camera Control - カメラ・コントロール

125点はメンバーを角度でバケツソートし、ボーカルパートを併合することで求められます。この際、数直線上の範囲の併合問題に落とすこともできますが、時間の範囲が0<=T<=1000で整数しかありませんので、booleanのフラグ配列を使用して併合することもできます。後者のほうが実装が簡単だと思います。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20121228
 |