AOJ 0574 : Nails
問題リンク:Nails | Aizu Online Judge
解法:
いもす法のサイトの解説参照
以下手順だけ
輪ゴムの頂点を(x,y),三角形のサイズをdとする
2次元配列gを用意する(vectorで動的にサイズを確保した)
gの(x,y),(x+1,y+d+2),(x+d+2,y+d+1)の値をプラス1
(x+1,y),(x,y+d+1),(x+d+2,y+d+2)の値をマイナス1する
入力の全てに対して上記の処理を行った後、
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 */