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

AIZU Online Judge C/C++

Problem 1130 : Red and Black

  • 難易度 : ☆☆
  • 種類 : 再帰

深さ優先探索。

#include <iostream>

using namespace std;


#define MAX 20

bool map[MAX+2][MAX+2];
int dx[4] = { 0, 1, 0, -1 },
	dy[4] = { -1, 0, 1, 0 };
int w, h;

int count( int x, int y )
{
	int cnt = 1;
	map[y][x] = false;

	for( int i=0; i<4; i++ )
		if( 1 <= x+dx[i] && x+dx[i] <= w && 1 <= y+dy[i] && y+dy[i] <= h && map[y+dy[i]][x+dx[i]] )
			cnt += count( x+dx[i], y+dy[i] );

	return cnt;
}

int main(void)
{
	int px, py, i, j;
	char ch;

	while( cin >> w >> h, w != 0 && h != 0 ){
		cin.get(ch);

		for( i=1; i<=h; i++ ){
			for( j=1; j<=w; j++ ){
				cin.get(ch);
				switch( ch ){
					case '.':
						map[i][j] = true; break;
					case '#':
						map[i][j] = false; break;
					case '@':
						map[i][j] = true; px = j; py = i; break;
				}
			}
			cin.get(ch);
		}

		cout << count( px, py ) << endl;
	}

	return 0;
}

Problem 1136 : Polygonal Line Search

  • 難易度 : ☆☆
  • 種類 : 幾何

線の長さと向きを照合するばーじょん。"Accepted"
幾何系は苦手…。

#include <iostream>
#include <cstdlib>

using namespace std;


struct LINE {
	int l;
	int d;
} lines[51][12];


int main(void)
{
	int n, m[51], x, y, d;
	int px, py, pd;
	int i, j, k, l;


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

		for( i=0; i<=n; i++ ){
			cin >> m[i];
			cin >> px >> py;
			pd = px + py;
			for( j=1; j<m[i]; j++ ){
				cin >> x >> y;
				d = x-px + y-py;
				lines[i][j-1].l = abs(d);

				if( j == 1 ){
					lines[i][j-1].d = 0;
				} else {
					if( x == px )
						lines[i][j-1].d = ( pd*d > 0 ) ? 1 : -1;
					else
						lines[i][j-1].d = ( pd*d > 0 ) ? -1 : 1;
				}
				px = x; py = y; pd = d;
			}
			m[i]--;
			lines[i][m[i]].d = 0;

			if( i == 0 ) continue;
			if( m[i] != m[0] ) continue;

			// 順
			for( j=0; j<m[i]; j++ ){
				if( lines[0][j].l != lines[i][j].l )
					break;
				if( lines[0][j].d != lines[i][j].d )
					break;
			}
			if( j == m[i] ){
				cout << i << endl;
				continue;
			}

			// 逆
			for( j=0; j<m[i]; j++ ){
				if( lines[0][m[i]-j-1].l != lines[i][j].l )
					break;
				if( lines[0][m[i]-j].d != lines[i][j].d*-1 )
					break;
			}
			if( j == m[i] ){
				cout << i << endl;
				continue;
			}
		}

		cout << "+++++" << endl;
	}
	return 0;
}


最初に試した、回転・逆順にしたパターンをすべてつくって照合していくばーじょん。
でも"Wrong Answer"。
うーん…。

#include <iostream>

using namespace std;


int n, m0;
struct POINT {
	int x, y;
};
POINT line0[8][10],
	  lines[50][10];

void initLine0()
{
	int x, y, i, j;

	cin >> m0;
	cin >> line0[0][0].x >> line0[0][0].y;
	for( i=1; i<m0; i++ ){
		cin >> x >> y;
		line0[0][i].x = x-line0[0][0].x;
		line0[0][i].y = y-line0[0][0].y;
		cout << line0[0][i].x << "," << line0[0][i].y << endl;
	}

	for( i=1; i<4; i++ ){
		for( j=1; j<m0; j++ ){
			line0[i][j].x = line0[i-1][j].y;
			line0[i][j].y = -line0[i-1][j].x;
			cout << line0[i][j].x << "," << line0[i][j].y << endl;
		}
	}

	line0[4][0].x = line0[0][m0-1].x;
	line0[4][0].y = line0[0][m0-1].y;
	for( i=1; i<m0; i++ ){
		line0[4][i].x = line0[0][m0-i-1].x-line0[4][0].x;
		line0[4][i].y = line0[0][m0-i-1].y-line0[4][0].y;
		cout << line0[4][i].x << "," << line0[4][i].y << endl;
	}
	for( i=5; i<8; i++ ){
		for( j=1; j<m0; j++ ){
			line0[i][j].x = line0[i-1][j].y;
			line0[i][j].y = -line0[i-1][j].x;
		cout << line0[i][j].x << "," << line0[i][j].y << endl;
		}
	}


	return;
}

int main(void)
{
	int x, y, i, j, k;
	int m[50];

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

		for( i=0; i<n; i++ ){
			cin >> m[i];
			cin >> lines[i][0].x >> lines[i][0].y;

			for( j=1; j<m[i]; j++ ){
				cin >> x >> y;
				lines[i][j].x = x-lines[i][0].x;
				lines[i][j].y = y-lines[i][0].y;
			}
		}

		for( i=0; i<n; i++ ){
			if( m[i] != m0 ) continue;

			for( j=0; j<8; j++ ){
				for( k=1; k<m[i]; k++ ){
					if( line0[j][k].x != lines[i][k].x || line0[j][k].y != lines[i][k].y ){
						break;
					}
				}

				if( k == m[i] ){
					cout << i+1 << endl;
					break;
				}
			}
		}

		cout << "+++++" << endl;
	}

	return 0;
}

Problem 1141 : Dirichlet's Theorem on Arithmetic Progressions

  • 難易度 : ☆☆
  • 種類 : 数論

エラトステネスの篩で素数表をつくって、数列の中に含まれる素数の数をカウント。

#include <iostream>

using namespace std;


bool primes[1000001];

void eratos()
{
	int i, j;

	for( i=0; i<=1000000; i++ )
		primes[i] = true;

	primes[0] = primes[1] = false;

	for( i=4; i<=1000000; i+=2 )
		primes[i] = false;

	for( i=3; i*i<=1000000; i+=2 )
		if( primes[i] )
			for( j=i+i; j<=1000000; j+=i )
				primes[j] = false;

	return;
}

int main(void)
{
	int a, d, n, cnt;

	eratos();

	while( cin >> a >> d >> n, a != 0 || d != 0 || n != 0 ){
		cnt = 0;

		while( a <= 1000000 ){
			if( primes[a] )
				cnt++;
			if( cnt == n ){
				cout << a << endl;
				break;
			}

			a += d;
		}
	}

	return 0;
}