torus711 のアレ

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

Codeforces 323, Division 1, A ( Division 2, C ) - GCD Table

問題概要

 $n$ 要素の数列 $a$ から生成されるGCD Table を,$$g_{ ij } = \mathrm{ gcd }( a_i, a_j )$$ なる $n \times n$ 行列とする.
 今,$g$ の要素を適当に並び替えた $n \times n$ 個の整数が与えられるので,$a$ として妥当なものを 1 つ復元せよ.解の存在は保証される.
 $1 \leq n \leq 500$

解法

 同じ値同士の GCD は元の値と同じなので,$g$ の元になった $a$ の要素は与えられる数値の中に全て含まれています.$a$ の要素は $g$ の対角要素に現れます.
 また,GCD をとったとき,結果は元の値の内大きくない方を超えません.従って,あるインデックス $i$ に着目すると,$g$ の $i$ 行と $i$ 列のそれぞれについて,$a_i$ より大きい要素は出現しません.
 これらのことを考慮すると,$a$ の要素を大きい方から 1 つずつ決めていくことができると分かります.以下の手順を繰り返します.

  1. 未使用の整数の内,最大のものを選ぶ
  2. 選んだ整数と,既に確定した $a$ の各要素との GCD を計算して,それらを使用済みにする(引数の順序で 2 個出てくるので 2 個ずつ消す)
  3. 手順 1 で選んだ値を $a$ に加える

 正当性ですが,未確定の値の内最大のものが $a$ の要素でない(⇔ $g$ の対角要素でない)とすると先程の条件に反することから妥当であると言えます.
 実装するにあたり必要な操作は,

  • 整数の多重集合から最大のものをとる($O( n )$ 回発生)
  • 集合から値を削除する($O( n^2 )$ 回発生)

の 2 種類です.制約を考えるとてきとーにやっても大丈夫そうですが(未検証),std::multiset がこれらの機能を備えているので,そのまま使うのが楽です.
 std::multiset の操作が 1 回あたり $O( \log n )$ 時間なので,全体では $O( n^2 \log n )$ 時間となります.

コード

using VI = vector< int >;

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; }

#define FOR( e, c ) for ( auto &e : c )

#define PB push_back

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int N;
	cin >> N;

	multiset< int, greater< int > > G( istream_iterator< int >( cin ), ( istream_iterator< int >() ) );

	VI res;
	while ( !G.empty() )
	{
		const int g = *begin( G );
		G.erase( begin( G ) );

		FOR( a, res )
		{
			auto pos1 = G.find( __gcd( g, a ) ), pos2( pos1 );
			advance( pos2, 2 );
			G.erase( pos1, pos2 );
		}

		res.PB( g );
	}

	cout << res << endl;

	return 0;
}