Sengoku(戦国時代) - joi2010-day1 解説

筆者: qnighy

斜め向きに監視できる人が複数与えられたとき、監視できる場所の総面積を求める問題である。

O(L^2+LN)解法

最もシンプルなのは、L×Lの配列を用意し、全ての兵についてその監視可能な範囲についてマークをするという方法である。

配列の初期化にはO(L^2)かかり、兵の監視可能な範囲はそれぞれの兵についてO(L)なので、兵の監視可能な範囲のマークはO(LN)かかる。よって全体としてはO(L^2+LN)かかる。

この場合は、15点分しか取れないことになる。

O(N^2)解法

ここで、Lに依存しないアルゴリズムを考える必要がある。

そこで、重複ありで数えてから、重複の個数を引く、という手法を採用しよう。

それぞれの兵の監視範囲は右上向きの監視範囲と左上向きの監視範囲に分けて考えられる。

そこから、その交差する部分を引くことを考えよう。

右上向きの線と左上向きの線はそれぞれ纏めてソートしてユニークにする。これはO(NlogN)で行える。

それぞれ長さの和を求める。これはO(N)でできる。

交差部分はO(N^2)で数えられる。

よって全体としてはO(N^2)時間で計算できる。

これで40点分を取ることができる。

O(NlogN)解法

さて、ここでボトルネックになっているのは交差部分の検出である。

これは、それぞれの右上向きの線について、それと交差する左上向きの線の範囲を二部探索で求められることから、O(NlogN)で行えることがわかる。

よってこの方法ならば計算量は全体でO(NlogN)となり、この方法でなら満点が期待できる。