torus711 のアレ

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

CODE THANKS FESTIVAL 2017, H : Union Sets

やや無理やり通したので,釈明を残しておこうと思いました.

問題概要

 (原文が日本語かつ十分に簡潔なので省略)

解法

 問題設定自体がどう見ても Union-Find なので,Union-Find が関係しそうだということは前提とします.
 記事中の表記については,まず,関数 $\alpha$ を,Ackermann 関数を $A( \cdot, \cdot )$ としたときの関数 $x \mapsto A( x, x )$ の逆関数とします.また,マージ操作は時系列的なイベントなので,連続する操作をしている途中のある時点のことを「時刻」と呼びます.

 (公式の解説でも触れられていますが),一瞬で思いつく(けど TLE する)解法としては,「一回マージする毎に,全部の質問クエリについて Union-Find の $\mathit{same}$ 操作を使ってチェックする」というのがあります.毎回チェックしているので,$\mathit{same}( x_j, y_j )$ が初めて $\mathrm{True}$ になったときが,クエリ $j$ に対する答えとなりますが,$O( N + MQ\alpha( N )$ 時間がかかって死にます.
 この解法を高速化する方向性で問題を解こうと思うと,「無駄な計算をしているのはどこか?」というのが気になってきます.では何処が無駄かと考えると,(マージは全部やらないとだめそうなので)マージ毎に「全部のクエリについてチェックする」という操作をしているところが疑わしいです.実際,$MQ$ 回のクエリの内,新しい情報が分かるのは $Q$ 回しかありません.そこで,$MQ - Q$ 回ある「無駄なチェック」を何とかして減らせないか,という方向性で解法を考えます.

 「無駄なチェックを減らす」ということは即ち,一つのクエリについて「初期状態から終状態までの全ての時刻でチェックする」のをやめて「一部の時刻だけでチェックし,かつ見落としもしない」というのを実現することです.飛び飛びの時刻でチェックするといかにも見落としそうな気がするので,ある時刻からある時刻まで連続した時刻でチェックをした方がよさそうだと考えると,「解が判明する可能性がある範囲」をある程度絞ることができれば,無駄なチェックを減らせそうです.

 やや天啓的ですが,マージ操作を $\mathrm\Theta( \sqrt M )$ 回ずつに区切って,それぞれのブロックで関係あるクエリについてだけ(上記 TLE 解法のように)チェックすれば全体でのチェックの回数を減らせそうです.そのためには各クエリがどのブロックに関係するか(どのブロックに含まれる時刻で解を発見するか)を予め知っておかねばなりません.なので解法は,

  1. 各クエリがどのブロックに関係するかを前計算
  2. マージ操作を進めながら,各時刻で関係するクエリについてだけ(上記 TLE 解法と同様に)チェックする

という 2 段階になります.
 前計算部分は,

  1. $\mathrm\Theta( \sqrt M )$ 回マージ操作を一気に進める
  2. 全クエリについてチェックする

というのを繰り返せば,各クエリについて「初めて $\mathrm{True}$ が返ってきたとき」の直前のブロックの中で解を発見できることが言えます.2 段階目については上で書いたこと以上はあまり言うことがないので,あとは実装をがんばるということになります.

 さて,この解法で本当に高速化できているのでしょうか.
 前計算部分では $M $ 回のマージ操作と,マージ $\mathrm\Theta( \sqrt M ) )$ 回ごとの全クエリチェックが $\mathrm\Theta( \sqrt M )$ 回行われます.それぞれ $O( M \alpha( N ) )$ 時間と $O( \sqrt M Q \alpha( N ) )$ 時間です.これに入力の受け取りと Union-Find の初期化が入るので,前処理の全体は $O\left( N + \left( M + \sqrt M Q \right) \alpha\left( N \right) \right)$ 時間になります
 解を求める段階でも,Union-Find の初期化に $O( N )$ 時間,マージ操作の全体に $O( M \alpha( N ) )$ 時間かかるのは同様です.クエリの方はどうでしょうか.ループが回る回数を考えるとちょっと難しいですが,クエリ毎に何回操作の対象になるかを考えると楽に解析できます.各クエリは高々 1 つのブロックに関係していて,ブロックのサイズは $O( \sqrt M )$ です.なので,各クエリについて実行されるチェックの回数は $O( \sqrt M )$ だと言えて,クエリ全体では $O( \sqrt M Q )$ 回のチェックが実行されます.従って 2 段階目全体では $O\left( N + \left( M + \sqrt M Q \right) \alpha\left( N \right) \right)$ 時間となります.
 結局どちらの段階も同じオーダーになって,アルゴリズム全体でも $O\left( N + \left( M + \sqrt M Q \right) \alpha\left( N \right) \right)$ 時間です(出力にかかる時間は定数倍の中に消える).

using VI = vector< int >;
using VVI = vector< vector< int > >;
 
template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }
 
void in_impl(){};
template < typename T, typename... TS > void in_impl( T &head, TS &... tail ){ cin >> head; in_impl( tail ... ); }
#define IN( T, ... ) T __VA_ARGS__; in_impl( __VA_ARGS__ );
 
template < typename T > struct getv_fmt;
template <> struct getv_fmt<       int >{ static constexpr const char *fmt = "%d"; };
template <> struct getv_fmt< long long >{ static constexpr const char *fmt = "%lld"; };
template < typename T > void getv( std::vector< T > &v ){ for_each( begin( v ), end( v ), []( T &a ){ scanf( getv_fmt< T >::fmt, &a ); } ); };
 
#define NUMBERED( name, number ) NUMBERED2( name, number )
#define NUMBERED2( name, number ) name ## _ ## number
#define REP1( n ) REP2( NUMBERED( REP_COUNTER, __LINE__ ), n )
#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2, REP1 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &&e : c )
#define ALL( c ) begin( c ), end( c )
 
#define PB push_back
 
class UnionFind; // 中身省略
// UnionFind( N )
// find( x )
// same( x, y )
// unite( x, y )
// groups()
// groupSize( x )
 
constexpr int SQ = 317;
 
int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;
 
	IN( int, N, M );
 
	VI A( M ), B( M );
	REP( i, M )
	{
		cin >> A[i] >> B[i];
		--A[i], --B[i];
	}
 
	IN( int, Q );
	VI X( Q ), Y( Q );
	REP( i, Q )
	{
		cin >> X[i] >> Y[i];
		--X[i], --Y[i];
	}
 
	VVI queries( SQ );
	{
		UnionFind uf( N );
		VI merged( Q );
 
		REP( i, SQ )
		{
			REP( j, i * SQ, min( M, ( i + 1 ) * SQ ) )
			{
				uf.unite( A[j], B[j] );
			}
 
			REP( q, Q )
			{
				if ( !merged[q] && uf.same( X[q], Y[q] ) )
				{
					merged[q] = 1;
					queries[i].PB( q );
				}
			}
		}
	}
 
	VI res( Q, -2 );
	{
		UnionFind uf( N );
 
		REP( i, SQ )
		{ 
			REP( j, i * SQ, min( M, ( i + 1 ) * SQ ) )
			{
				uf.unite( A[j], B[j] );
 
				FOR( q, queries[i] )
				{
					if ( res[q] < 0 && uf.same( X[q], Y[q] ) )
					{
						res[q] = j;
					}
				}
			}
		}
	}
 
	transform( ALL( res ), ostream_iterator< int >( cout, "\n" ), bind( plus< int >(), _1, 1 ) );
	cout << flush;
 
	return 0;
}