Hide-and-seek(かくれんぼ) - joi2010-day3 解説

筆者: qnighy

条件を満たす座標値を求める問題である。

O(WN)解法

この問題は複雑であるが、問題の要求から考えて、障害物をy座標の小さい順に処理するのが適切である。なお、実装を簡単にするには、y座標の次にx座標の小さい順に並べるとよいので、ここではそのように仮定する。

用意する配列は2つ、「ある攻撃力について、その答えが格納された配列W」と、「x座標について、その位置に現在ある障害物の個数が格納された配列Sである。」

それぞれの障害物について、その該当するS[x]の値を全てインクリメントする。その過程で、W[S[x]]を調べ、未初期化の場合W[S[x]]=(x,y)とおく。これを繰り返すことで目的の配列Wが得られる。

それぞれの障害物についてその幅に比例する時間のかかる処理を行っているので、合計O(WN)で解ける。これで30点が期待できる。

O(W+NlogW)解法

ここで、上記の配列Sについての処理を高速化したい。

そこで、Segment Treeの技法を使ってこれを高速化する。ここで必要とされるクエリは、合宿の過去の問題である「Starry Sky」で用いられたものと同じなので、JOI参加者の間では「Starry Sky Tree」と呼ぶことがある。

ここではその詳細は述べない(複数の実装方法が存在する)が、必要とされるクエリを纏めておこう。

• i番目の要素の値を返す。
• 区間[f,t)にある要素全てに値aを加算する。
• 最大の値をもつ要素のなかで最小のインデックスを返す。

これを実装することで、O(W+NlogW)で解くことができ、満点が期待できる。