Hatena::Grouptopcoder

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

 | 

2009-03-12

Single Round Match 436 @ TopCoder 11:09 Single Round Match 436 @ TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 436 @ TopCoder - nodchipのTopCoder日記 Single Round Match 436 @ TopCoder - nodchipのTopCoder日記 のブックマークコメント

Single Round Match 436 @ TopCoderの参加記録です

Easy 250 BestView

(0,0)-(0,heights[0])、(1,0)-(1,heights[1])、(2,0)-(2,heights[2])という線分が与えられる。各線分の上端から他の線分を見ようとしたとき、最も多くの線分を見られる場合の線分の数を求めよ。

250にしては面倒な幾何問題だと感じました。各線分の左側と右側について、それぞれ線分の上端への傾きを更新しながら新たに見えてくる線分を調べていきました。

ソースは後ほど。

Midium 500 DoNotTurn

2次元ダンジョンが与えられる。左上のマスから右下のマスに到達するまでに90度進行方向を変える最小回数を求めよ。

[x座標][y座標][向き]を状態とした探索であることは明白です。とりあえず幅優先探索で書ました。最大ケースを確認してsubmit。

ソースは後ほど。

Hard 1000 CircularShifts

配列AとBについて、AをrotateしたものとBの内積を考える。内積の値が最も大きくなるときの値を求めよ。

N=60000という中途半端な数字なのには訳があります。とりあえずO(N^2)でやろうとすると、60000^2>10^8よりTLE確定・・・のはずでした。

自分の解法はFFTを使用したものでした。フーリエ変換の

(g*h)(t) = g(t)h(N-t) \Leftrightarrow G(f)H(f)

という公式を使い、gをAを2個繋げた配列、hをBをreverseした配列と置き、それぞれをFFTでフーリエ変換した後、掛け合わせ、逆フーリエ変換を行い、最大値を調べて終わりです。

ソースは後ほど。

撃墜フェーズ

1000をsubmitしてしまったことで動揺し、まったく集中できませんでした。

結果

o o o 1120.33 10位

1000が通ってしまってしまいました。偏った知識が刺さりました。奇跡です。SRMでは初めて1000を通すことができました。10位とか意味が分かりません。

総評

1000は解き方が主に3通りあり、FFTを使う方法、カラツバ法を使う方法、インラインアセンブラ(!?)でSIMDを使った高速化との事です。Psyho氏のインラインアセンブラは神です。

ところで500はダイクストラのはずなのに、なぜ幅優先探索で通ってしまったのでしょうか・・・?

レーティングは2075->2241となり、レッドコーダーとなりました。自分のような若輩者がレッドコーダーになんかなって良い筈がありません。次回確実に落ちると思います。

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