TopCoder SRM 624

2014-06-13 | [Competitive programming]

250

ソートして，累積和を取ると，ソートされた列上である範囲のビルたちの高さを揃えるためのコストは O(1) で決定できる． よって，O(N^2) で解ける．

450

「各辺の長さが非負の無向グラフで，頂点 1 から N までの最短経路の数を求めよ」というよくありそうな問題．

多分，長さ 0 の辺に気をつけてやるだけ

1000

適当に前処理をしておくと，LCA が O(1) で求められるので，木上の 2 点間の距離も O(1) で求められる．

また，青い点を固定したとき，すべての点に対するクエリの答えは，次のようにして O(N) で求められる．

  1. 各点に対して，その点を根とする部分木に含まれる青い点の数を計算する．これは木 DP で O(N) で求められる．
  2. 根に対する答えは，簡単に O(N) で計算できる．
  3. a -> b と辺を下った時の b での答えは，a での答えに (青い点の総数 - 2 * (b を根とする部分木に含まれる青い点の数)) * (辺の長さ) を加える事で求められる． 1 回あたり O(1) なので，全点に対して O(N) で求められる．

以上を用いて，平方分割を行う． 青い点を「登録」「未登録」の 2 種類に分ける． 未登録の青い点については，クエリごとにすべて直接試すことによって答えを求める． 登録された青い点については，各点に対して「すべての登録された青い点までの距離の和」が計算されているようにすると，答えは参照するだけで求められる． ここで，未登録の点の数がある閾値を超えたら，それらの点も登録し，全点クエリの答えを改めて計算するようにする．

閾値を適切に設定することで，O((N + Q) √N) 程度になり，AC が得られる．

結果

1 人くらい Mid で「長さ 0 が出てきたら無限通り」ということをやる人がいるだろうと思ったら本当にいて，落として +50

Mid 落ちた (>_<)

oxo +50 745.96 10 位

rating: 2995 -> 3047