AOJ 0574 : Nails

問題リンク：Nails | Aizu Online Judge

解法：
いもす法のサイトの解説参照

以下手順だけ
輪ゴムの頂点を(x,y),三角形のサイズをdとする
２次元配列gを用意する（vectorで動的にサイズを確保した）
gの(x,y),(x+1,y+d+2),(x+d+2,y+d+1)の値をプラス１
(x+1,y),(x,y+d+1),(x+d+2,y+d+2)の値をマイナス１する

入力の全てに対して上記の処理を行った後、
x,y,斜めの順で累積和をとる
そしてgの配列の要素で1以上のものを数え上げて出力する

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 5100
using namespace std;

int N,M;
//int g[MAX][MAX];

int main()
{
  scanf("%d %d",&N,&M);
  vector<int> g[N+5];
  rep(i,N+5)g[i].resize(i+5);
  rep(i,N+5)rep(j,i+1)g[i][j] = 0;
  rep(i,M)
    {
      int x,y,d;
      scanf("%d %d %d",&y,&x,&d);
      x--,y--;
      g[y][x]++,g[y+d+2][x+1]++,g[y+d+1][x+d+2]++;
      g[y][x+1]--,g[y+d+1][x]--,g[y+d+2][x+d+2]--;
    }

  rep(i,N+2)rep(j,i+2)if(j-1>=0)g[i][j] += g[i][j-1];
  rep(x,N+2)REP(y,x,N+2)if(y-1>=0)g[y][x] += g[y-1][x];
  rep(i,N+2)
    {
      int y = i,x = 0;
      while(y <= N+2 && x <= N+2)
	{
	  if(y-1>=0 && x-1>=0)g[y][x] += g[y-1][x-1];
	  y++,x++;
	}
    }

  int ans = 0;
  rep(y,N+2)rep(x,y+2)if(g[y][x]>0)ans++;
  cout << ans << endl;

  return 0;
}

メモ：

/*
.
1x
...
....
.....
x....1
.1...x.
........
.........
..........

x -> y -> (斜め)

大きさ d

1 : (x  ,y) (x+1,y+d+2) (x+d+2,y+d+1)
x : (x+1,y) (x,y+d+1)   (x+d+2,y+d+2)

xは-1
*/