Apples(リンゴの出荷) - joi2011-day4 解説

筆者: qnighy

int程度の大きな数字について、その数字の挿入と、差が定数B内に収まるようなN個の数字の組のうち最大のものの取得および削除のクエリにオンラインで答える問題である。

O(D+MlogD)解法

リンゴの濃さをあらわす数字が10万程度に収まるとき、セグメントツリーを使用して解くことができる。

• 一回の出荷では必ずxが存在して[x,x+B]の区間内にある濃さのリンゴだけを出荷する。さらに言うと、このような区間のなかで最も大きいものを選び、その中にあるリンゴを最大の濃さのものから順番に出荷すればよい。(出力するときは濃さの昇順に並び替える。)
• そこで、それぞれのリンゴを[r,r+B]すなわち[r,r+B+1)に対応させる。すると、N個の区間が重なるところが、N個のリンゴを出荷できる地点に対応する。これは2010Hide_and_Seek、2009Starry_Skyでも出題されたのと同じSegmentTree (通称Starry Sky Tree)を使えばよい。
• 出荷したい濃さがわかったら、その中で一番濃いものを選ぶ必要がある。これは、「その区間内にあるリンゴの中で、最も濃さの小さいものの濃さ」を各区間に記憶させたセグメントツリーを用意して、上から調べることで対処できる。

以上により、O(D+MlogD)で解くことができ、30点を取ることができる。

O(M+MlogD)解法

セグメントツリーでカバーしたい範囲よりも、セグメントツリーに対するクエリのほうが圧倒的に少ないことに注目する。このとき、実際には区別しなくていい区間が大量に存在する可能性が高い。

そこで、必要に応じて木を拡張する方法を考える。通常このような手法を実現するときは、「平衡二分木」の手法が必要であり、特に自作のSegmentTreeの平衡化は大変な実装を伴うのであまり良くない。

ここでは、元々のSegmentTreeと同様の構造を保持しながら、クエリに関係のない節点は子を実体化しないことで計算量を節約することを考えよう。

すなわち、SegmentTreeは以下のような構造体で管理する。(配列のインデックスでもよい。)

使わない間はleft=right=NULLになっていて、この節点に対応する内にある座標を使用したいときにはじめてleftとrightを実体化する。

このようにすることで、計算量O(M+MlogD)となり、これを正しく実装すれば満点が期待できる。

ただしこのとき、メモリ制限および時間制限の両方がギリギリであるので、十分に注意すること。