Codeforces #166, B : Prime Matrix

問題文

http://codeforces.com/contest/271/problem/B

概要

の行列が与えられる。
一回の操作で、この行列中の任意の要素に 1 を加算することができる。

また、行列が Prime Matrix であるとは、行列が次の条件のうち一つ以上を満たす場合と定義する。

• 素数のみからなる行をもつ
• 素数のみからなる列をもつ

与えられた行列を Prime Matix にするために必要な操作回数の最小数を求めよ。

解法

各要素について、それを素数にするために必要な操作の最小数を求めておき、行・列毎に和をとって最小値を答えとします。
このとき、各要素を 1 ずつ加算しながら で素数判定をすると TLE する（本番でやらかしました……）ので、予め Eratosthenes の篩等で素数列を求めておき、二分探索を用いて判定をするとよいと思います。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )
#define fst first
#define snd second

VI eratosthenes()
{
	vector<bool> nums( 100008, true );
	nums[0] = nums[1] = false;

	VI res;

	REP( i, 2, nums.size() )
	{
		if ( !nums[i] )
		{
			continue;
		}

		res.PB( i );

		for ( int j = 1; i * j < nums.size(); j++ )
		{
			nums[ i * j ] = false;
		}
	}

	return res;
}

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

	int h, w;
	cin >> h >> w;

	VI primes = eratosthenes();

	VVI matrix( h, VI( w ) );
	EACH( line, matrix )
	{
		EACH( a, line )
		{
			int tmp;
			cin >> tmp;
			auto pos = equal_range( ALL( primes ), tmp );

			if ( *( pos.fst ) == tmp )
			{
				a = 0;
			}
			else
			{
				a = *( pos.snd ) - tmp;
			}
		}
	}

	int res = INT_MAX;
	EACH( line, matrix )
	{
		res = min( res, accumulate( ALL( line ), 0 ) );
	}

	REP( i, 0, w )
	{
		int tmp = 0;

		REP( j, 0, h )
		{
			tmp += matrix[j][i];
		}

		res = min( res, tmp );
	}

	cout << res << endl;

	return 0;
}