![カンガルーを[a,b]とおき、カメラを[c,d]とおくと、
[c,d]と[a,b]に共通部分があればよいので、共通部
分がない時が、d<a or b<c であるので、共通部分
があるためには、a<=d かつc<=b であればよい。](https://image.slidesharecdn.com/kangaroo-140828210141-phpapp01/85/Kangaroos-8-320.jpg)
![カンガルーの集合をKとおき、カメラを[c,d]とおく。
このとき、先の考察より、Kに含まれるすべての
カンガルー[a,b]に対して、a<=d かつc<=b が成立
する。
よって、Kに含まれるカンガルーの始点の最大値
をA、Kに含まれるカンガルーの終点の最小値をB
とおくと、A<=d かつc<=B が成り立てばよい。](https://image.slidesharecdn.com/kangaroo-140828210141-phpapp01/85/Kangaroos-9-320.jpg)
![1以上N以下のある数Sを決めて、N匹のカンガ
ルーをサイズSごとのグループに分ける。
NがSの倍数でないときは最後に[0,0]カンガルーを
高々S個入れればよいので、NがSの倍数としても
よい。N=xSとおき、グループを
[1…S][S+1…2S]...[(x-1)S…xS]
とする。i個目(1<=i<x)のバケットを[iS...(i+1)S]と
呼ぶことにする。](https://image.slidesharecdn.com/kangaroo-140828210141-phpapp01/85/Kangaroos-12-320.jpg)
![まず、集合罢1について考える。
集合T1のある要素をカメラで撮るための条件を考
えると、ある要素(a,b)をカメラ[c,d]で撮ることが
できるとき、
a<=bより、
a<=c<=b<=d or a<=c<=d<=b or
c<=a<=b<=d or c<=a<=d<=b
であればよく、すなわち、[a,b]と[c,d]が共通部分
をもてばよい。](https://image.slidesharecdn.com/kangaroo-140828210141-phpapp01/85/Kangaroos-24-320.jpg)
![集合に現れる数を座標圧縮しておき、集合の要素
(a,b)について、初期状態が0で埋められた配列の要
素aから要素bまで1を足すと、各々のカメラ[c,d]が
ある要素と交差するかどうかの判定はその配列の
要素cから要素dまでのいずれかが1以上であるかど
うかで判定可能。
前半はimos法を使うことでO(M+N)、後半も累積
和を使うことで、前計算O(M+N)、クエリ(1)で対
応可能。
よって、この場合はO(M+N)で可能。](https://image.slidesharecdn.com/kangaroo-140828210141-phpapp01/85/Kangaroos-25-320.jpg)
![次に、集合T2について考える。
集合T2のある要素をカメラで撮るための条件を考
えると、ある要素(a,b)をカメラ[c,d]で撮ることが
できるとき、
a>bより、
c<=b<a<=d
であればよく、すなわち、[b,a]が[c,d]に含まれて
いればよい。](https://image.slidesharecdn.com/kangaroo-140828210141-phpapp01/85/Kangaroos-27-320.jpg)
![これは、座標圧縮して各々の座標に対して、
dp[t]:=(集合T2に含まれる要素で、終点の最
小値がt以上となるもののうちの、始
点の最大値の最小)
を計算する。これはDPを行うことでO(M+N)で計
算可能。
よって、これを用いることで、ある要素がカメラ
[c,d]に含まれるか判定をO(1)で可能。
よって、この場合もO(M+N)で可能。](https://image.slidesharecdn.com/kangaroo-140828210141-phpapp01/85/Kangaroos-28-320.jpg)
Kangaroos
- 3. 1…Nそれぞれに対して、時間aiから時間biの間に カンガルーが出現する。 また、M個のカメラがあり、それぞれ時間ciから時 間diの間の自由な時間に写真を撮ることができる。 このとき、それぞれのカメラについて、連続した 区間であって、それに含まれるカンガルーすべて をとることができるような区間の内、最も長い区 間の長さを求めよ。
- 5. カンガルー A(2,6) B(1,3) C(5,5) カメラ(4,7) この場合はAとCの写真を撮ることができるの で、答えは1(AとCは連続していないから)
- 6. カンガルー A(2,6) B(1,5) C(3,4) カメラ(4,7) この場合はAとBとCの写真を撮ることができ るので、答えは3
- 8. カンガルーを[a,b]とおき、カメラを[c,d]とおくと、 [c,d]と[a,b]に共通部分があればよいので、共通部 分がない時が、d<a or b<c であるので、共通部分 があるためには、a<=d かつc<=b であればよい。
- 9. カンガルーの集合をKとおき、カメラを[c,d]とおく。 このとき、先の考察より、Kに含まれるすべての カンガルー[a,b]に対して、a<=d かつc<=b が成立 する。 よって、Kに含まれるカンガルーの始点の最大値 をA、Kに含まれるカンガルーの終点の最小値をB とおくと、A<=d かつc<=B が成り立てばよい。
- 12. 1以上N以下のある数Sを決めて、N匹のカンガ ルーをサイズSごとのグループに分ける。 NがSの倍数でないときは最後に[0,0]カンガルーを 高々S個入れればよいので、NがSの倍数としても よい。N=xSとおき、グループを [1…S][S+1…2S]...[(x-1)S…xS] とする。i個目(1<=i<x)のバケットを[iS...(i+1)S]と 呼ぶことにする。
- 14. 各々のカメラに対して、それぞれのバケットに含 まれるカンガルーをすべてとれるかを確かめる。 これは、各々のバケットに対してそれに含まれる カンガルーの始点の最大値、終点の最小値を前計 算O(N)で行うことで、各カメラに対し、 バケットがx個あるので、O(x)かかり、O(N+Mx) で行うことができる。
- 15. そのバケットに含まれるカンガルーすべてを撮る ことができないときは、左からいくつは撮ること ができる、右からはいくつ撮ることができる、と いうことを計算する。 これは各々のバケットに対して、左、右から1…S 個のカンガルーの始点の最大値、終点の最小値を O(N)で前計算しておき、各カメラに対して、二分 探索を行うことで、左からいくつ、右からいくつ 撮れるかO(xlogS)で行うことができる。よって、 O(N+MxlogS)で可能。
- 16. これが分かると、後はO(x)で各々のカメラに対し て計算可能。 左からi個、ok….ok、右からj個 のときは、S*hoge+i+j 個撮ることができる。 よって、二種類以上のバケットを含む区間につい て撮ることができるかどうかはO(N+MxlogS)で求 めることができる。
- 18. これを満たす区間は、バケットがx個、一つのバ ケットにS*(S-1)/2個あるので、x*S*(S-1)/2=N*(S- 1)/2個しかない。 よって、これらはすべて列挙でき、これらの区間 に含まれるカンガルーの始点の最大値及び終点の 最小値を計算する。これはO(NS)で可能である。
- 21. これらの区间を长さ别にして考える。 ある長さの区間集合について、この集合に含まれ る区間を撮ることができるか各カメラに対して考 える。 ここで、これに含まれる区間に対して、始点の最 大値、終点の最小値しか必要な情報ではないので、 集合Tをその区間集合に含まれる各々の区間に含ま れる（始点の最大値、終点の最小値）という数の ペアの集合とする。
- 22. さらに、場合分けをし、集合Tのうち、 （始点の最大値）<=（終点の最小値） となるペアの集合をT1、 （始点の最大値）>（終点の最小値） となるペアの集合をT2とする。
- 23. まず、集合罢1について考える。
- 24. まず、集合罢1について考える。 集合T1のある要素をカメラで撮るための条件を考 えると、ある要素(a,b)をカメラ[c,d]で撮ることが できるとき、 a<=bより、 a<=c<=b<=d or a<=c<=d<=b or c<=a<=b<=d or c<=a<=d<=b であればよく、すなわち、[a,b]と[c,d]が共通部分 をもてばよい。
- 25. 集合に現れる数を座標圧縮しておき、集合の要素 (a,b)について、初期状態が0で埋められた配列の要 素aから要素bまで1を足すと、各々のカメラ[c,d]が ある要素と交差するかどうかの判定はその配列の 要素cから要素dまでのいずれかが1以上であるかど うかで判定可能。 前半はimos法を使うことでO(M+N)、後半も累積 和を使うことで、前計算O(M+N)、クエリ(1)で対 応可能。 よって、この場合はO(M+N)で可能。
- 26. まず、集合罢2について考える。
- 27. 次に、集合T2について考える。 集合T2のある要素をカメラで撮るための条件を考 えると、ある要素(a,b)をカメラ[c,d]で撮ることが できるとき、 a>bより、 c<=b<a<=d であればよく、すなわち、[b,a]が[c,d]に含まれて いればよい。
- 28. これは、座標圧縮して各々の座標に対して、 dp[t]:=(集合T2に含まれる要素で、終点の最 小値がt以上となるもののうちの、始 点の最大値の最小) を計算する。これはDPを行うことでO(M+N)で計 算可能。 よって、これを用いることで、ある要素がカメラ [c,d]に含まれるか判定をO(1)で可能。 よって、この場合もO(M+N)で可能。
- 30. 二つ以上のバケットを含む区間：O(N+MxlogS) 一種類のバケットに含まれる区間:O(S(M+N)) で解けるので、 O(N+MxlogS+MS+NS)=O(NS+MNlogS/S+MS) である。 よって、S= ?????とおくことで、 O ? + ? ????? で解くことができる。
- 31. ?なかなか定数倍が重かった… ?もっといい解法も本に載ってます ?手元ではTLE13secが5secで通ったので たぶん大丈夫だと思います…
- 32. ?なかなか定数倍が重かった… ?もっといい解法も本に載ってます ?手元ではTLE13secが5secで通ったので たぶん大丈夫だと思います… ?夏季セミ面白かったです!!