Tenka1 Programmer Contest 2018 E. Equilateral
問題
HxWのグリッドにコインがいくつか置かれている。
このとき、相異なるコインの3つ組で「その3つのうち、どの2つのコインを取っても、それらの存在する座標の間のマンハッタン距離が一定」であるようなものの個数を求めよ。
制約
- 1 <= W, H <= 300
解法
「マンハッタン距離が一定」というのは、実際に図示してみると、ある点を中心とした正方形を45度回転させたところになる。
他の2点はこの正方形の線上に乗っている必要がある。
適当に2点を定めてみると、該当する点の範囲(赤い領域)は以下のように絞られる。
しかし、単純に2点を選んで3点目を考えてしまうと、3点目がO(1)で求められたとしてもO(W*H * W*H)になってしまい間に合わない。
ここで無駄なところを探してみると、「ある点xを決めた場合、残り2点のうちどちらかは必ずxの45度斜めに存在する」、ということに気付く必要がある。
ある点xに対して、45度斜め方向にある点yがある場合、最後の3点目zは上の図の一番右の図のように赤い範囲の部分となる。
赤い範囲の部分に点が何個あるか?は、前もって累積和を求めておけばO(1)で求められるので、点xを決めるのにO(W*H)、点yを見つけるのにO(W+H)、点zを見つけるのにO(1)、累積和を計算するのにO( (W+H)*(W+H) )で、全体としてO(W*H*(W+H))≒O(N^3)程度で求められる。
実装
上記のアルゴリズムを実装するのに、単純に45度の4方向すべてに対して求めると重複で数え上げてしまうので、その分を引いてあげる必要がある。
解説放送では、盤面全体を90度回転を4回行い、それぞれの回転ごとに、以下の部分をカウントする方法が紹介されていた。
ある点xについて、その右上方向の45度方向にだけ点yを探し、点zの範囲のうち、一番右上の部分だけカウントしない。
もしそのカウントしない部分に点zがあった場合は、時計回りに90度回転したときにカウントされる。
右下の範囲については、180度回転した場合にカウントされ、右上のカウントしないところも270度回転したときにカウントされるので、重複なくカウントできる。(天才)
反省
添え字間違い、範囲外アクセスなどしまくった。
怪しい部分は範囲外アクセスなどしていないかチェックする。
あと、斜めのまま実装したけど、「絶対値を見たら45度回転」から45度回転した状態で処理した方がいろいろミスがなさそう。。。