画像(差分)が与えられるたびに全ピクセルをチェックするアルゴリズムはO(CN2)となり、制限時間内に解を求めることはできません。計算量を落とす工夫が求められます。

まず1枚目の画像を読み込み、左上半分(全体の4分の1)における各ピクセルについて、対応する左右方向のピクセル、上下方向のピクセル、斜め方向のピクセルが全て一致するか確認し、一致しない場合diffをカウントします。左上半分のピクセルについて処理した後、diffの値が0の場合は、上下対象かつ左右対称な画像のため、答えansに1を加算します。

続く画像については、各ピクセルの差分を更新する前の状態と後の状態によってdiffの値を更新します。ここで、状態は与えられたピクセル(r, c)とその上下対象、左右対称、斜め対称の4つのピクセルが一致しているかどうかを表します。処理前が一致、処理後が不一致の場合はdiffを加算します。一方、処理前が不一致、処理後が一致の場合はdiffを減算します。各画像について、全ての差分を処理した後にdiffが0となった場合に、ansに1を加算します。

差分のみを考慮すると、O(N2 + C×D)のアルゴリズムとなります。