CodeChef February 2013 Challenge 本番 - antaの競技プログラミング練習日記

http://www.codechef.com/FEB13
初めてのChef long。結果は振るわなかったけれど、考えるのが面白かった。

Problems

BUY1GET1

数える

CLMBSTRS

LECARDS

各カードがどんな数値であっても、それを取るなら相対スコアが+1・取らないなら-1になることがわかる。
ここで相対スコアを正にするにはつまり半数より多いカードを取ればいい。
つまり求めたいのは(Σ(i = ceil(N/2)..N) { C(N, i) })。
これは普通に前計算してやればいい。

EFFPAINT

とりあえず左上から見てってできるだけ大きい黒の長方形をgreedyに作るということをしたら、まあまあの得点になった。
それより上は考えていない。

MBOARD

O(Q log N)を通した。
基本方針として、その行/列が最後に変更されたのはいつか？・それは0か1か？を全て持つようにする。
そして各質問クエリでは、「質問された行/列の最後に変更された時間」より後に、「その時の値」と違う値に変更された「質問が行なら列・列なら行」の数を数えられれば良い。
これには並行探索二分木をソートされた状態で用いた。
高速化のために、まだ何も変更されていない所(0)は普通にに持たないようにしたり、eraseを削除フラグのinsertにしたりした。

TRIQUERY

三角形の斜めの辺がうっとおしいので座標変換する。
(x, y)を(x, y+x)に変換すれば、三角形の斜めの辺が平行になる。

もし([l,r)の範囲の中で、b以上である点の数を数えよ)というクエリができるならば、下の図のようにしてTriangle-Queryに答えることが出来る。

一番右の、底辺が斜めの領域は座標変換をすれば平行になることに注意。
さて、その区間x以上クエリはどうすればいいか？
自分はこれにWaveletMatrixを用いた。座標は静的であるし、もってこいのデータ構造だ。
WaveletMatrixについてはこの記事を参照。今回はそのrank_allを改造して使った。

WPLAY

bitDP。
単語を「それぞれのアルファベットを何回使うか」でTrieで持ってやった。
時間は厳しい気もしたが、あっさり通った。

TESTERS

解けてない。
TRIQUERYの座標変換のように、距離に応じて0.5ずつ減らしてn以上の数クエリをダイナミックにやればいけるかなーとか考えてた。
でも木上のパスでそれをうまくやる方法がわからなかった。

QUERY

Centroid-Path-Decompositionした永続木の各ノードに永続セグメント木を持ってやった。
手元ではナイーブにやるコードと答えがあっているのに、WAして、結局最後まで通らなかった。
なにかコーナーケースがあるのか、チェック用コードが間違っているのか、それとも問題解釈間違ってるのか…

ROC

少し考えたけどあまり考えられなかった。

結果

Score: 6.482
Rank: 47

コード

テスト用コードが混じっていて非常に読みづらいです。
http://www.codechef.com/users/anta0のProblems Successfully SolvedのFEB13から見てください。

学びたてのWaveletMatrixが使えて嬉しかった。
こういうクエリとかデータ構造系は結構好きだ。