小課題 1

\(N = 1\) なので、その 1 本の道路に重なる家の個数を数えれば良いです。\(O(M)\) で解くことができます。

小課題 2

\(N, M\) がともに小さいので、道路の選び方を全探索して、全ての家について、それに重なる選ばれた道路があるかを調べて加算すれば良いです。\(O(2^NNM)\) で解くことができます。

小課題 3

\(N\) が大きいので、道路の選び方を調べることはできません。 それぞれの家について、その家を通る道路が \(X\) 本あったとき、答えの値にその家は \(2^N-2^{N-X}\) 回寄与します。 よって、すべての家についてこの値を求めて足し合わせてやれば良いです。\(O(NM)\) で解くことができます。

小課題 4

\(N,M\) がともに大きいですが、\(a_i\) が distinct だという条件があります。 すべての直線について、その上にある家を列挙してみることを考えてみましょう。 \(y_i\leq 5\cdot 10^4\) より、ある直線 \(y=a_ix+b_i\) 上において、家がある可能性のある座標は高々 \(\frac{5\cdot 10^4}{{a_i}}\) 個程度です。 \(a_i\) は distinct なので、正負合わせてもこの個数の総和は \(5\cdot 10^4(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{N})\sim 5\cdot 10^4\log N\) の定数倍に収まり、家の列挙に連想配列を使うこともあわせて、\(O(\max(y)\log^2N)\) や \(O(\max(y)\log N)\) でこの問題を解くことができます。

小課題 5

\(a_i\) が distinct ではないので、小課題 4 のような不等式評価が成り立たず、計算回数が最悪 \(5\cdot 10^4N\) 回程度となり、間に合いません。

ところで、\(|a_i|\geq B\) の直線に対しては直線上の格子点を全探索し、\(|a_i|<B\) の直線に対しては、家ごとにそれを通る直線の傾きを全探索してやるとします。

このとき、計算回数は \(\frac{5\cdot 10^4MlogM}{B}+BlogN\) 回程度となりますが、ここで \(B=\sqrt{\max(y)}\) 程度とすると、計算回数が十分少なくなり、正解することができます。 なお、工夫して連想配列を使わないようにすれば、\(O(\sqrt{\max(y)}M)\) でこの問題を解くことができます。