『ACM/ICPC国内予選突破の手引き』をやってみる（５）

AIZU Online Judge C/C++

ACM/ICPC国内予選突破の手引き”Step by step”の難易度：☆☆☆ スタート。

Problem 2008 : Dragon Fantasy

  • 難易度 : ☆☆☆
  • 種類 : 探索

解説見てやっとできた。
(double)<=(double)という比較をしたいとき、doubleの計算では誤差があるため==の比較ができない。
したがって、==の場合に対応するために

if( dist( c[i].x-d.x, c[i].y-d.y ) < new_t + 1e-10 )

みたいに、近似値を使用する。これは大事らしいので覚える。

#include <iostream>
#include <deque>
#include <cmath>

using namespace std;

struct POINT {
	int x, y;
	bool v;
} c[21], p, d;
int n;
bool Ans;


inline double dist( int dx, int dy ){
	return sqrt( (double)dx*dx + (double)dy*dy );
}

void solve( double t, int x, int y )
{
	if( Ans ) return;

	int i, cnt;
	double new_t;

	cnt = 0;
	for( i=0; i<n; i++ ){
		if( c[i].v ){
			cnt++;
			continue;
		}

		new_t = t + dist( c[i].x-x, c[i].y-y );
		if( dist( c[i].x-d.x, c[i].y-d.y ) < new_t + 1e-10 )
			return;
	}

	if( cnt == n ){
		Ans = true;
		return;
	}

	for( i=0; i<n; i++ ){
		if( Ans ) break;
		if( c[i].v ) continue;

		new_t = t + dist( c[i].x-x, c[i].y-y );
		c[i].v = true;
		solve( new_t, c[i].x, c[i].y );
		c[i].v = false;
	}

	return;
}

int main(void)
{
	while( cin >> n >> p.x >> p.y >> d.x >> d.y ){
		if( n == 0 && p.x == 0 && p.y == 0 && d.x == 0 && d.y == 0 )
			break;

		for( int i=0; i<n; i++ ){
			cin >> c[i].x >> c[i].y;
			c[i].v = false;
		}
		Ans = false;

		solve( 0, p.x, p.y );
		if( Ans )
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

Problem 1126 : The Secret Number

  • 難易度 : ☆☆☆
  • 種類 : DP

DPだと考えるとなかなか簡単だった。
でも気づくのが難しい…。

#include <iostream>
#include <deque>
#include <string>

using namespace std;

#define MAX 70


string mat[MAX+2][MAX+2];
int w, h;

string maxString( string a, string b )
{
	if( a.size() > b.size() )
		return a;
	if( a.size() < b.size() )
		return b;

	for( int i=0; i<a.size(); i++ ){
		if( a[i] > b[i] )
			return a;
		if( a[i] < b[i] )
			return b;
	}

	return a;
}

int main(void)
{
	int i, j;
	string input, max, tmp[2];

	for( i=0; i<=h+1; i++ )
		for( j=0; j<=w+1; j++ )
			mat[i][j] = "";

	while( cin >> w >> h, w != 0 && h != 0 ){
		max = "";

		for( i=1; i<=h; i++){
			cin >> input;
			for( j=1; j<=w; j++ )
				mat[i][j] = input[j-1];
		}

		for( i=1; i<=h; i++ ){
			for( j=1; j<=w; j++ ){
				if( "A" <= mat[i][j] && mat[i][j] <= "Z" )
					continue;
				
				tmp[0] = tmp[1] = "";
				if( '0' < mat[i-1][j][0] && mat[i-1][j][0] <= '9' )
					tmp[0] = maxString( mat[i][j], mat[i-1][j]+mat[i][j] );
				if( '0' < mat[i][j-1][0] && mat[i][j-1][0] <= '9' )
					tmp[1] = maxString( mat[i][j], mat[i][j-1]+mat[i][j] );
				mat[i][j] = maxString( maxString( mat[i][j], tmp[0] ), tmp[1] );
				max = maxString( max, mat[i][j] );
			}
		}

		cout << max << endl;
	}

	return 0;
}

Problem 2011 : Gather the Maps!

  • 難易度 : ☆☆☆
  • 種類 : DP

まえーに一回解いたことがあったので、解説ナシで解けた。

#include <iostream>
#include <vector>

using namespace std;


int n;
int d[51][31];	// d[子孫の番号][日付] = 1:出席できる / 2:できない
int p[51][51];	// p[子孫の番号][地図の断片の番号] = 1:所持 / 2:所持していない

// すべての地図の断片を持っている人が存在すればtrueを返す。
bool check()
{
	int i, j;

	for( i=1; i<=n; i++ ){
		for( j=1; j<=n; j++ )
			if( !p[i][j] )
				break;

		if( j == n+1 )
			return true;
	}

	return false;
}

// 初期化
void initialize()
{
	int i, j;

	for( i=0; i<=n; i++ ){
		for( j=0; j<=30; j++ )
			d[i][j] = 0;

		for( j=0; j<=n; j++ ){
			if( i == j )
				p[i][j] = 1;
			else
				p[i][j] = 0;
		}
	}

	return;
}

int main(void)
{
	int f, i, j, k, input;
	vector<int> list;

	while( cin >> n, n != 0 ){

		initialize();

		// 入力
		for( i=1; i<=n; i++ ){
			cin >> f;
			for( j=0; j<f; j++ ){
				cin >> input;
				d[i][input] = 1;
			}
		}

		// 日ごと
		for( i=0; i<=30; i++ ){
			// 出席できる人を探す
			list.clear();
			for( j=1; j<=n; j++ )
				if( d[j][i] )
					list.push_back(j);
			if( list.size() == 0 )
				continue;

			// 地図の交換
			int work = 0;
			for( j=1; j<=n; j++ ){
				work = 0;
				for( k=0; k<list.size(); k++ )
					work += p[list[k]][j];
				work = ( work ) ? 1 : 0;
				for( k=0; k<list.size(); k++ )
					p[list[k]][j] = work;
			}

			if( check() )
				break;
		}

		// 結果の出力
		if( i <= 30 )
			cout << i << endl;
		else
			cout << "-1" << endl;

	}

	return 0;
}