AtCoder Beginner Contest 168 F - . (Single Dot)
公式解説: 解説 pdf
問題概要
無限に広がる平面上に $N (\leq 1000)$ 本の縦線と $M (\leq 1000)$ 本の横線がある。 縦線と横線の端点の座標の値は$-10^9$ 以上 $10^9$ 以下の範囲に収まる。
座標 $(0, 0)$ から動くことのできる範囲の面積を求めよ。
解法概要
座標の範囲が広いが，線の本数，つまり出てくる座標の種類数は多くない。 このような性質を持つ問題では，座標を圧縮したくなる。
座標圧縮とは，座標の数値を「出てくる値の中で何番目に小さいか」という順位で置き換えることで値の範囲を狭めるテクニックである。実装方法についてはここでは立ち入らないので，下記のソースコード やけんちょんさんのブログ記事などを参考に。
今回は $x$ 軸 $y$ 軸それぞれで出てくる値の数がせいぜい $3000 + 1$ 種類なので，座標圧縮することで以下のような行列を使って問題で与えられた平面を表すことができるようになる。
1111111111111111111 1111101111111111111 1111101111111111111 1111101111111011111 1111101111111011111 1000000000000000001 1111101111111011111 1111101110001011111 1111101110101011111 1111101000100000111 1111101011101011111 1111101000001011111 1111101111111011111 1110000000000000111 1111101111111011111 1111101111111011111 1111111111111011111 1111111111111011111 1111111111111111111
(Sample 1 の例。マス目とマス目の境界，またはマス目の中を両方1文字分の幅で扱っている。 0 は境界上かつ線が引かれていることであることを表し，1 はマス目または「境界上だが線が引かれていない場所」を意味する)
上のように入力を表すことができれば，後は BFS なり DFS なりを適用させれば良い。 なのでここからの目標は上のような行列を作ることである。
「線分と線分の間」と「線分上」を両方扱うので，目標となる行列のサイズは ($x$座標の値の種類数 $\times 2 + 1$) $\times$ ($y$座標の値の種類数 $ \times 2 + 1$) とすることができる。
また，座標圧縮後の座標の値を $0$ 始まりで $1$ 刻みに割り当てるとすると，座標圧縮後の座標と目標となる行列上の座標は，座標圧縮後の座標を $(x, y)$ とすると $(2\times x + 1, 2 \times y + 1)$ とすることができる。
この座標の値の対応に合わせて，目標の行列で線分上に対応している要素を 0 で塗っていく。
すると，ここで言う「目標となる行列」が完成。
しかしこの行列，圧縮前の値と値の間隔の情報が落ちてしまっている。例えば，$(1, 0)$ と $(10^9, 0)$ のような 2 つの座標が登場したとして，圧縮後には $(0, 0)$, $(1, 0)$ とかになってしまい，「両者の幅が $10^9-1$ もあった」という情報は落ちる。
これに対処するために，$x$ 座標方向の幅， $y$ 座標方向の幅をそれぞれ持っておく。例えば $x = x_1$ となる座標がマス目の境界に相当するなら幅を 0 にしておき，そうでないならその両側に対応する圧縮前の座標の差を幅としておけば良い。 また，添字が 0 または最大の行 (列) に関しては幅を無限大にしておく。無限大の幅のマスにもし移動することができたら，その地点で答えは INF である。本段落の話は，$y$ 座標についても同様。
こうすることで，BFS や DFS をするときに，今いる座標の「面積」$x$ 座標方向の幅と $y$ 座標方向の幅の積で求められる。BFS や DFS で動ける範囲全体を動き，動けたマスの面積の総和をとったものが答えになる。
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <map> #include <set> #include <tuple> using namespace std; using ll = long long; using Pii = pair<int, int>; constexpr int INF = 1 << 30; constexpr int dyx[4][2] = { { 0, 1}, {-1, 0}, {0,-1}, {1, 0} }; struct Segment { ll x1, x2, y1, y2; Segment(ll a, ll b, ll c, bool is_vertical) { if(is_vertical) { x1 = a; x2 = b; y1 = y2 = c; } else { x1 = x2 = a; y1 = b; y2 = c; } } }; int main() { int n, m; ll a, b, c; cin >> n >> m; vector<Segment> segs; set<ll> xs, ys; xs.insert(0); ys.insert(0); for(int i=0;i<n+m;++i) { cin >> a >> b >> c; segs.push_back(Segment(a, b, c, i < n)); xs.insert(segs.back().x1); xs.insert(segs.back().x2); ys.insert(segs.back().y1); ys.insert(segs.back().y2); } int nx = xs.size()*2+1, ny = ys.size()*2+1; map<ll, ll> mpx, mpy; // 圧縮後の座標への変換 vector<ll> widthx(nx, 0), widthy(ny, 0); // 変換後のフィールドでの各マスの幅 { int i = 0; ll prev = -INF; for(ll x: xs) { mpx[x] = i*2+1; widthx[i*2] = (prev == -INF) ? INF : (x - prev); prev = x; i++; } widthx[i*2] = INF; i = 0; prev = -INF; for(ll y: ys) { mpy[y] = i*2+1; widthy[i*2] = (prev == -INF) ? INF : (y - prev); prev = y; i++; } widthy[i*2] = INF; } vector<vector<bool>> matrix(nx, vector<bool>(ny, true)); // 変換後の草原 vector<vector<bool>> used(nx, vector<bool>(ny, false)); for(int i=0;i<n+m;++i) { // x と y のいずれかは単一の値しか取らないはず for(ll x=mpx[segs[i].x1];x<=mpx[segs[i].x2];++x) { for(ll y=mpy[segs[i].y1] ;y<=mpy[segs[i].y2] ;++y) { matrix[x][y] = false; } } } // 変換後の草原の上で BFS ll ans = 0LL; queue<Pii> que; que.emplace(mpx[0], mpy[0]); used[mpx[0]][mpy[0]] = true; { ll x, y; while(!que.empty()) { tie(x, y) = que.front(); que.pop(); if(widthx[x] == INF || widthy[y] == INF) { ans = -1; break; } ans += widthx[x] * widthy[y]; for(int k=0;k<4;++k) { ll xx = x + dyx[k][0], yy = y + dyx[k][1]; if(0 <= xx && xx < nx && 0 <= yy && yy < ny && !used[xx][yy] && matrix[xx][yy]) { que.emplace(xx, yy); used[xx][yy] = true; } } } } if(ans == -1) { cout << "INF" << endl; return 0; } cout << ans << endl; }
所感
ほどよく筋肉な問題で好き。コンテスト中に解きたかった。
