JOI2011本戦 第一問「惑星探索」

JOIの本戦が終了した。
フィードバックたんは「4問正解だよ〜」って言ってるけど、正直5番はO(n^2)だから甘く見積もっても20点だし、3番はpriority_queue使うべきところで単なるqueue使っちゃったから分からん。
上位陣との差を改めて痛感した。


せっかくなのでソース公開。(終わった後で組み直したやつ)


まずは1番から。
「やるだけ。」は使わない方針で・・・

1番「惑星探索」

旅人(去年の1番)の2次元版。
(i,j)までの'J','O','I'の個数をそれぞれ記録しておいて(d[i][j][0~2])、
クエリ(x1,y1,x2,y2)には、d[x2][y2][0~2] - d[x1-1][y2][0~2] - d[x2][y1-1][0~2] + d[x1-1][y-1][0~2]を返せばいい。

つまり、
f:id:snuke:20110213180416p:image

 青 +橙 +緑 +赤  : d[x2][y2]
-青 -橙        : d[x1-1][y2]
-青    -緑     : d[x2][y1-1]
+青           : d[x1-1][y1-1]
ーーーーーーーーー
          赤

ってやれば赤を求められるよ〜、ってこと。

#include<cstdio>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;

int d[1001][1001][3];

int main(){
	int m, n, k, x1,y1,x2,y2;
	char a[1002];
	scanf("%d%d%d", &m, &n, &k);
	
	rrep(i,m){
		scanf("%s",a);
		rrep(j,n){
			rep(h,3) d[i][j][h] = d[i-1][j][h] + d[i][j-1][h] - d[i-1][j-1][h];
			
			switch(a[j-1]){
				case 'J':
					d[i][j][0]++;
					break;
				case 'O':
					d[i][j][1]++;
					break;
				case 'I':
					d[i][j][2]++;
					break;
			}
		}
	}
	
	rep(i,k){
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		x1--; y1--;
		rep(h,3) printf("%d%c",d[x2][y2][h] - d[x1][y2][h] - d[x2][y1][h] + d[x1][y1][h], (h == 2)?'\n':' ');
	}
	return 0;
}

〜変数説明〜
d[i][j][h] : 左上の座標が(1,1)、右下が(i,j)の長方形の中に 'J','O','I' が何個あるか。
    ('J' = 0、'O' = 1、'I' = 2)
m, n, k, x1,y1,x2,y2, a[1002] : 入力データを受け取る。


To be continued...