(o_o)

ブログ。

再帰を使わない Segment Tree

蟻本には再帰で書かれた Segment Tree が載っているが,うまく書けば再帰を使わず書くこともできる.

再帰あり

gist9219b197f2a177931e54627003b51c6f

再帰なし

gistfe04fcefcc5581d60da6150a621d549e


それぞれの方法で長さ 200000 でランダムな 1000000 クエリに対して RMQ を書き,実行時間を比較した.
(GNU C++ 5.1.0 で -O2 最適化オプションを付けた)
それぞれの 1 クエリあたりの時間は以下のようになった.

実行時間 (ns)
再帰あり 179
再帰なし 74

再帰なしだとかなり速く,定数倍の重さは Fenwick Tree の高々倍程度のようだ.

ICPC WF 2017 の大学選抜について

運営が翌年のWFの選抜方法を明らかにしたみたい.たぶんこんな感じ

・([順位] - 1) / [大会に割り当てられているスコア] が小さい順にKチーム選ぶ

例えば,Asia PP subregion の今年のスコア (Daejeon:1.9, Hanoi:1.3, Jakarta:1.3, Phuket:0.9, Singapore:1, Taipei:0.8, Tsukuba:1.7) を元に計算してみると,Regionでの上位 20 チームは以下のようになる.

Daejeon 1位 (0.00000)
Hanoi 1位 (0.00000)
Jakarta 1位 (0.00000)
Phuket 1位 (0.00000)
Singapore 1位 (0.00000)
Taipei 1位 (0.00000)
Tsukuba 1位 (0.00000)
Daejeon 2位 (0.52632)
Tsukuba 2位 (0.58824)
Hanoi 2位 (0.76923)
Jakarta 2位 (0.76923)
Singapore 2位 (1.00000)
Daejeon 3位 (1.05263)
Phuket 2位 (1.11111)
Tsukuba 3位 (1.17647)
Taipei 2位 (1.25000)
Hanoi 3位 (1.53846)
Jakarta 3位 (1.53846)
Daejeon 4位 (1.57895)
Tsukuba 4位 (1.76471)

今年 PP subregion に割り当てられたスロットは11大学.実際は同一の大学が複数の大会で入賞することが多いから17~8位くらいまで選抜されるかもしれない(特に U Tokyo や National Taiwan U は各地で入賞しそう...)
来年は PP subregion にメダル枠がないため,日本の大学は厳しい戦いを強いられそうだ.

AOJ2154 海岸線の浸食

線分アレンジメントして列挙するだけ.
O(N^4 * T) (Tはテストケース数) だが,幾何なので間に合う.
ジャッジケースをビジュアライザに入れた結果はこんな感じ
http://mars.kmc.gr.jp/~asi1024/shore_erosion/

続きを読む

AOJ2258 全自動円形掃除機™

全自動円形掃除機™ をACしたのはもう1年近く前だけど,いまさら解説記事を書きます.
いろんな実装方法はあるけど,自分の実装はこんな感じ.

多角形の各線分からR内側に平行移動した線分を列挙する
各頂点からの半径 R の円周を列挙する
これらの線分や円周の交点で線分や円を区切ってアレンジメントする
これらの線分や円弧から,多角形の外壁からの距離が R のものを列挙する
(線分や円弧からランダムに一点選び,多角形の各辺との距離の最小値をとればよい)
列挙した線分や円弧をつないで閉曲線にする
この閉曲線を境界とする閉領域の中からルンバ™の中心点を内部に含むものを選ぶ.
(この領域がルンバ™が到達可能な領域である.)
この閉曲線の各線分,円弧について,以下を行う
1. 線分を R だけ外側にずらす
2. 円弧は円と円弧の端を結ぶ 2 線分に変換する
3. こうしてできた新たな多角形について,内角が180度を超える角の外側を円弧で埋める
こうして生成した域がルンバ™が到達可能な領域である.

ジャッジ入力をビジュアライザにかけた結果は以下の通り.
赤い線分&円で囲まれてるのが求めたいやつ.
http://mars.kmc.gr.jp/~asi1024/roomba/problem
http://mars.kmc.gr.jp/~asi1024/roomba/answer
全体的にジャッジ入力が弱い.そもそも軸に平行な多角形しかない.
軸に平行な多角形しか入力にないことは入力の制約に書かれているらしいです.
だったらもっと簡単に解けそう・・・

ソースコードは省略