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]を返せばいい。
青 +橙 +緑 +赤 : 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...