【AOJ 2015】Square Route

問題

Square Route | Aizu Online Judge

方針

• 道と道の間隔が与えられるので, 正方形の区画がいくつあるか数える問題
• すべてのパターンを試す方法では, となり終わらない.
• そこで, 辺の長さの全パターンを予め求め, その出現個数を元に計算する.（この場合はとなる）
  • 長さが出現する場所, 順序はあまり関係がないため.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define m0(x) memset(x, 0, sizeof(x))

using namespace std;

int x[2000], y[2000];
int count_x[1500001], count_y[1500001];

signed main(){
  int n, m;
  vector<int> w, h;
  while(cin >> n >> m, n||m){
    rep(i, n) cin >> y[i];  
    rep(i, m) cin >> x[i];  
    m0(count_x);
    m0(count_y);
    rep(i, n){
      int sum = 0;
      REP(j, i, n){
        sum += y[j];
        count_y[sum]++; // 長さがsumの個数を数える
      }
    }
    
    rep(i, m){
      int sum = 0;
      REP(j, i, m){
        sum += x[j];
        count_x[sum]++;
      }
    }
    
    int ans = 0;
    rep(i, 1500001){
      ans += count_x[i] * count_y[i]; // 同じ長さの個数の積が答えになる.
    }
    
    cout << ans << endl;
  }
}

参考

Square Route 解説
こちらの図がとてもわかり易い.