解説
別のねこが最後に通過した時間より、最後に掃除された時間が後であることが、ねこがその線を通過可能である必要十分条件です。
通る線と重なっている、平行な線(本)と垂直な線(本)について考えます。
平行な線の最後の掃除時間が、他すべて(本)の線の最後の通過時間より後であるとき、明らかに達成可能です。
そうでないとき、垂直な線の最後の掃除時間が、それぞれ、すべてそれらの最後の通過時間より後であり、尚且つ、その最後の掃除時間の最古が、平行な線の最後の通過時間より後であるとき、達成可能です。
ほかの場合は、通過ができません。
これは、例えば、セグメント木を本活用することで解くことができます。
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。