読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

Codeforces #341 Div2 B

問題

codeforces.com
1000×1000のマスにN個のビショップが置かれている。
2つのビショップ同士が互いに斜め方向に位置する場合、お互いを攻撃し合う。
この互いに攻撃し合う組み合わせを数える。
ここで、マスの列は左から右へ、行は上から下に、1から1000まで番号付けされる。

解法

コンテスト中には解けなかったので、Editorialとか見てました。

codeforces.com
ビショップの座標ごとにx + y と x - y の計算結果の値をカウントしていく。
そのカウント数をaとすると,a個のビショップの中から2つのビショップを選ぶ組み合わせを計算するので aC2 を求める。
そして、その計算を各マスごとに行う。

でも、Editorial見ても x1 + y1 == x2 + y2 OR x1 - y1 == x2 - y2 が成り立つ時にどうしてビショップ同士が斜め方向に存在することが分かるのかが分かりませんでしたが、
何となくx1 + y1とかx1 - y1の式が二次元座標上で図形を回転させる処理に似てるなぁとか思って勝手に納得したんですが、どうなんでしょうか。

ソースコード

import java.util.*;
public class B
{
	public void solve()
	{
		Scanner cin = new Scanner(System.in);
		int N = cin.nextInt();
		int[] x = new int[N],y = new int[N];
		int[] rotate1 = new int[2500];
		int[] rotate2 = new int[2500];
		for(int i = 0;i < N;i++)
		{
			x[i] = cin.nextInt();
			y[i] = cin.nextInt();
			rotate1[x[i] + y[i]]++;
                        /*ここの999はx[i]よりy[i]の値が大きい場合に配列に格納できるようにするため
              最悪でもx = 1でy = 1000の場合がある。*/
			rotate2[x[i] - y[i] + 999]++;
		}
		long ans = 0;
		for(int i = 0;i < 2500;i++)
		{
			ans += rotate1[i] * (rotate1[i] - 1) / 2;
		}
		
		for(int i = 0;i < 2500;i++)
		{
			ans += rotate2[i] * (rotate2[i] - 1) / 2;
		}
		System.out.println(ans);
	}
	public static void main(String[] args)
	{
		new B().solve();
	}
}