phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

Tenka1 Programmer Contest 2018 E. Equilateral

問題

HxWのグリッドにコインがいくつか置かれている。
このとき、相異なるコインの3つ組で「その3つのうち、どの2つのコインを取っても、それらの存在する座標の間のマンハッタン距離が一定」であるようなものの個数を求めよ。

制約

  • 1 <= W, H <= 300

解法

「マンハッタン距離が一定」というのは、実際に図示してみると、ある点を中心とした正方形を45度回転させたところになる。

f:id:phyllo_algo:20181028233734p:plain

他の2点はこの正方形の線上に乗っている必要がある。
適当に2点を定めてみると、該当する点の範囲(赤い領域)は以下のように絞られる。

f:id:phyllo_algo:20181028233815p:plain

しかし、単純に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回行い、それぞれの回転ごとに、以下の部分をカウントする方法が紹介されていた。

f:id:phyllo_algo:20181028235340p:plain

ある点xについて、その右上方向の45度方向にだけ点yを探し、点zの範囲のうち、一番右上の部分だけカウントしない。
もしそのカウントしない部分に点zがあった場合は、時計回りに90度回転したときにカウントされる。
右下の範囲については、180度回転した場合にカウントされ、右上のカウントしないところも270度回転したときにカウントされるので、重複なくカウントできる。(天才)

反省

添え字間違い、範囲外アクセスなどしまくった。
怪しい部分は範囲外アクセスなどしていないかチェックする。

あと、斜めのまま実装したけど、「絶対値を見たら45度回転」から45度回転した状態で処理した方がいろいろミスがなさそう。。。