SRM433@TopCoderの復習

500@Div1@SRM433を解きなおしてみた。
初めに菱形を全部列挙して、格子の中に当てはめて数を数えるという戦略。
菱形の列挙は1点目を原点、2、3点目を全探索という形にしてみた。計算量はO(N^2M^2)。アリーナに送ってみたところ(91,93)で限界。(100,100)がTLEで通らない。
続いて3点目のy座標を2点目のx/y、3点目のxから求めるというO(N^2M)にしたところ、worstケースが1.5秒で通せた。

これを本番中に書くのは今の自分には厳しいと思う・・・。