Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

2013-02-17

[]0575 : Festivals in JOI Kingdom 19:50 はてなブックマーク - 0575 : Festivals in JOI Kingdom - TopCoderの学習のお時間


想定解法と違う方法で解いたのでメモ。


解説スライドで、Union-Findを使った計算量 O(MlogN+QNα(N)) の30点解法が紹介されているが、これを平方分割を使って O(MlogN+Q√Nα(N)) にする。


N個のノードを距離が遠い順にソートして、√N個まとめてUnionする。

まだ答えが出ていないクエリのうちで、この√N個のノードをUnionする前後で繋がるようになったものだけを、もう一度今度はノードを1つずつくっつけながらどのタイミングで繋がるかを調べる。


Javaで普通にコレクション使って書いたら、GCまわりでMLEになったりTLEになったりした。最初に配列でバッファを取って使い回すように書き換えたら通った。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=580287

2012-11-18

[]AOJメモ 20:10 はてなブックマーク - AOJメモ - TopCoderの学習のお時間


ICPC気分を感じるために昔のアジア地区予選の問題をAOJで解いていた。



難易度の割に正解者数が少ないのは、古すぎるのでみんなやってないからだろうか