AOJ2015 Square Route

問題リンク Square Route

• 解法

道路の数は各方向それぞれ1500、そして幅の最大は1000なので、最大の正方形でも1辺の長さは高々1500000です。
それぞれの方向に対して、作ることができる1辺の長さとその個数をカウントします。
カウントし終えたら、同じ長さ同士で積を取ったものの個数だけ正方形が作れます。例えば、横方向に長さ4の辺を2個、縦方向に長さ4を3個作れるとしたら、2*3個の面積16の正方形が作れることになります。

• ソース

import java.util.Scanner;

//Square Route
public class AOJ2015 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if((n|m)==0)break;
			int[] h = new int[n];
			for(int i=0;i<n;i++)h[i]=sc.nextInt();
			int[] w = new int[m];
			for(int i=0;i<m;i++)w[i]=sc.nextInt();
			int[] wh = new int[1500001];
			int[] ww = new int[1500001];
			for(int i=0;i<n;i++){
				int s = 0;
				for(int j=i;j<n;j++){
					s+=h[j];
					wh[s]++;
				}
			}
			for(int i=0;i<m;i++){
				int s = 0;
				for(int j=i;j<m;j++){
					s+=w[j];
					ww[s]++;
				}
			}
			int c = 0;
			for(int i=0;i<1500001;i++)c+=wh[i]*ww[i];
			System.out.println(c);
		}
	}
}