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

ACM/ICPC国内予選突破の手引き”Step by step”の難易度：☆☆終わり。

Problem 1131 : Unit Fraction Partition

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

分母の組み合わせを試していく。
でも、はじめさっぱりだった。解説を見てから実装。

#include <iostream>

using namespace std;


int p, q, a, n;

int solve( int i, int last, int prod, int c, int d )
{
	if( c*q == d*p )
		return 1;

	if( i >= n )
		return 0;

	int cnt = 0;

	for( int j=last; prod*j<=a; j++ )
		if( (j*c+d)*q <= p*j*d )
			cnt += solve( i+1, j, prod*j, j*c+d, j*d );

	return cnt;
}

int main(void)
{
	int i, j;


	while( cin >> p >> q >> a >> n ){
		if( p == 0 && q == 0 && a == 0 && n == 0 )
			break;
		cout << solve( 0, 1, 1, 0, 1 ) << endl;
	}

	return 0;
}

Problem 1142 : Organize Your Train part II

• 難易度 : ☆☆
• 種類 : 文字列操作

文字列のパターン（8種類）を作ってはsetにつっこんでいく。setは重複したものを弾いてくれるので、最終的にsetの要素数を出力すればよい。
STLに助けられた感じ。

#include <iostream>
#include <string>
#include <set>

using namespace std;


set<string> patt;


string str_reverse( string src )
{
	string dec = src;

	for( int i=0; i<src.size(); i++ )
		dec[i] = src[src.size()-i-1];

	return dec;
}

void solve( int x, string str )
{
	string a, b;

	// 前半
	a = str.substr( 0, x );
	// 後半
	b = str.substr( x, str.size()-x );


	// 逆転:無
	patt.insert( a + b );
	patt.insert( b + a );

	// 逆転:A
	patt.insert( str_reverse( a ) + b );
	patt.insert( b + str_reverse( a ) );

	// 逆転:B
	patt.insert( a + str_reverse( b ) );
	patt.insert( str_reverse( b ) + a );

	// 逆転:A,B
	patt.insert( str_reverse( a ) + str_reverse( b ) );
	patt.insert( str_reverse( b ) + str_reverse( a ) );

	return;	
}

int main(void)
{
	int m, i;
	string input;

	cin >> m;
	while( m-- > 0 ){
		patt.clear();

		cin >> input;
		for( i=1; i<input.size(); i++ )
			solve( i, input );

		cout << patt.size() << endl;

	}

	return 0;
}

Problem 1144 : Curling 2.0

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

深さ優先探索。

#include <iostream>
#include <deque>

using namespace std;


int map[22][22];
int w, h;

void init()
{
	for( int i=0; i<=h+1; i++ ){
		for( int j=0; j<=w+1; j++ ){
			if( i == 0 || i == h+1 || j == 0 || j == w+1 )
				map[i][j] = -1;
			else
				map[i][j] = 0;
		}
	}

	return;
}

int solve( int x, int y, int n )
{
	if( n > 10 ) return -1;

	int i, j, mx, my, new_val, cnt = -1;
	int dx[4] = { 0, 1, 0, -1 };
	int dy[4] = { 1, 0, -1, 0 };

	for( i=0; i<4; i++ ){
		mx = x+dx[i]; my = y+dy[i];
		if( map[my][mx] == -1 || map[my][mx] == 1 ) continue;

		while( true ){
			if( map[my][mx] == 3 ){
				return n;
			}

			mx += dx[i]; my += dy[i];

			if( map[my][mx] == 1 ){
				map[my][mx] = 0;
				new_val = solve( mx-dx[i], my-dy[i], n+1 );
				if( new_val != -1 && ( cnt == -1 || cnt > new_val ) ){
					cnt = new_val;
				}
				map[my][mx] = 1;
				break;
			} else if( map[my][mx] == -1 ){
				break;
			}
		}

	}

	return cnt;
}

int main(void)
{
	int i, j, sx, sy;

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

		for( i=1; i<=h; i++ ){
			for( j=1; j<=w; j++ ){
				cin >> map[i][j];
				if( map[i][j] == 2 ){
					sx = j; sy = i;
				}
			}
		}

		cout << solve( sx, sy, 1 ) << endl;
	}

	return 0;
}