torus711 のアレ

主に競技プログラミングの問題について書きます

AtCoder Beginner Contest 168, F: . (Single Dot)

問題概要

 平面上に,$Y$ 軸に平行な線分が $N$ 本,$X$ 軸に平行な線分が $M $ 本引かれている.$i$ 番目の縦線は 2 点 $( A_i, C_i )$ と $( B_i, C_i )$ を結んでいて,$j$ 番目の横線は 2 点 $( D_j, E_j )$ と $( D_j, F_j )$ を結んでいる.
 原点からスタートして平面状を歩くとき,いずれの線分も跨がずに行ける領域の面積を求めよ.無限に広い場合は,代わりに "INF" と出力せよ.

制約

  • 座標の絶対値は $10^9$ 以下で,整数
  • $1 \leq N, M \leq 1{,}000$
  • $A_i < B_i$
  • $E_j < F_j$
  • 原点を通る線分は無い

解法

 線分が軸に平行かつ整数なので,平面をグリッド状に刻んで考えることができます.ここでは,各グリッドをその左上の座標によって識別することにします(例えば,原点はその右下のグリッドに含まれていることにする($Y$ 軸を下向きにとります)).
 問われている面積を求めるだけであれば,原点を含むグリッドからスタートして BFS などをすることで求めることができますが,(意味のある)空間がそれなりに広いため,これでは TLE します.しかしよく考えてみると,空間を広くとったとき,広さに対して線分の本数がかなり少なくなるため,中身は「スカスカ」になります.このときにできる「変化の起こらない領域」をひとまとめにして扱うことで,探索空間を $O( N M )$ ぐらいのサイズにすることができます.
 具体的には,線分の端点及び原点の座標を軸ごとにソート + unique することで,ソート後に隣接する座標値の間にはその軸に関して「何も無い」というような状態を作れます.これは「座標圧縮」として知られていて,蟻本 [1] にも記載がありますので,そちらもご参照ください.
 今回の問題で座標圧縮をすると,グリッドはいくつかの長方形領域に区切られて,それぞれの辺は「全て線分に乗っている」か「(端点を除いて)全く線分に乗っていない」かのいずれかになります*1.なので,座標圧縮をした跡の各領域について,その境界を跨げるかどうかを判定できるようにしておくと BFS などをすることができます.無限大かどうかの判定については,外平面まで歩けるかどうかを調べられれば良いので,樹部分大きい値を座標に加えることで外平面を表現し,そこに行けるかどうかで判定できます.
 以下の参考実装では Disjoint Set Forest (Union-FInd) を使って横着をしていますので,$O( N M \alpha( NM ) )$ 時間です.

コード

constexpr auto INF = LIM<>::max() / 2;

class DisjointSetForest;
// DisjointSetForest( N )
// find( x )
// same( x, y )
// unite( x, y )
// groups()
// groupSize( x )

VI compress( const VI &a, const VI &b, const VI &c )
{
	VI res{ -INF, 0, INF };
	copy( ALL( a ), BI( res ) );
	copy( ALL( b ), BI( res ) );
	copy( ALL( c ), BI( res ) );

	sort( ALL( res ) );
	res.erase( unique( ALL( res ) ), end( res ) );

	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	IN( int, N, M );
	VI A( N ), B( N ), C( N ), D( M ), E( M ), F( M );
	REP( i, N )
	{
		cin >> A[i] >> B[i] >> C[i];
	}
	REP( i, M )
	{
		cin >> D[i] >> E[i] >> F[i];
	}

	const VI ys = compress( A, B, D );
	const VI xs = compress( C, E, F );

	const int H = SZ( ys );
	const int W = SZ( xs );

	VVI right_bounded( H, VI( W ) ), down_bounded( H, VI( W ) );
	REP( i, N )
	{
		const int idx_x = --lower_bound( ALL( xs ), C[i] ) - begin( xs );
		const int idx_y1 = lower_bound( ALL( ys ), A[i] ) - begin( ys );
		const int idx_y2 = lower_bound( ALL( ys ), B[i] ) - begin( ys );
		REP( j, idx_y1, idx_y2 )
		{
			right_bounded[j][ idx_x ] = true;
		}
	}
	REP( i, M )
	{
		const int idx_y = --lower_bound( ALL( ys ), D[i] ) - begin( ys );
		const int idx_x1 = lower_bound( ALL( xs ), E[i] ) - begin( xs );
		const int idx_x2 = lower_bound( ALL( xs ), F[i] ) - begin( xs );
		REP( j, idx_x1, idx_x2 )
		{
			down_bounded[ idx_y ][j] = true;
		}
	}

	DisjointSetForest dsf( H * W );
	const auto grid_id = [&]( const int y, const int x )
	{
		return y * W + x;
	};

	REP( i, H )
	{
		REP( j, W )
		{
			if ( i + 1 < H && !down_bounded[i][j] )
			{
				dsf.unite( grid_id( i, j ), grid_id( i + 1, j ) );
			}
			if ( j + 1 < W && !right_bounded[i][j] )
			{
				dsf.unite( grid_id( i, j ), grid_id( i, j + 1 ) );
			}
		}
	}

	const int idx_y0 = lower_bound( ALL( ys ), 0 ) - begin( ys );
	const int idx_x0 = lower_bound( ALL( xs ), 0 ) - begin( xs );

	if ( dsf.same( 0, grid_id( idx_y0, idx_x0 ) ) )
	{
		cout << "INF" << endl;
		return 0;
	}

	LL res = 0;
	REP( i, H )
	{
		REP( j, W )
		{
			if ( !dsf.same( grid_id( i, j ), grid_id( idx_y0, idx_x0 ) ) )
			{
				continue;
			}

			const LL dy = ys[ i + 1 ] - ys[i];
			const LL dx = xs[ j + 1 ] - xs[j];
			res += dy * dx;
		}
	}

	cout << res << endl;

	return 0;
}

参考文献

[1] 秋葉拓哉, 岩田陽一, and 北川宜稔. プログラミングコンテストチャレンジブック: 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える. マイナビ出版, 2012.

*1:辺ごとに乗っていたり乗っていなかったりします.一応