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

AIZU Online Judge C/C++

（『ACM/ICPC国内予選突破の手引き』をやってみる（１）に引き続きACM/ICPC国内予選突破の手引きの”Step by step”。
これで”Step by step”の難易度：☆がすべて終了。

Problem 1119 : Exploring Caves

  • 難易度 : ☆
  • 種類 : シミュレーション

入力ごとに座標移動、距離計算、最大値更新して最後に出力するだけ。
英文の問題を読むのが一番大変だった…。

#include <iostream>

using namespace std;


int main(void)
{
	int n, x, y, dx, dy, max_x, max_y;

	cin >> n;
	while( n-- > 0 ){
		x = y = 0; max_x = max_y = 0;
		while( cin >> dx >> dy, dx != 0 || dy != 0 ){
			x += dx; y += dy;
			if( (double)max_x*max_x+(double)max_y*max_y < (double)x*x+(double)y*y ){
				max_x = x; max_y = y;
			} else if( (double)max_x*max_x+(double)max_y*max_y == (double)x*x+(double)y*y && x > max_x ){
				max_x = x; max_y = y;
			}
		}
		cout << max_x << " " << max_y << endl;
	}

	return 0;
}

Problem 1124 : When Can We Meet?

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

日付ごとカウントして、最大値を出力。
言語の壁を乗り越えればそれほど難しい問題じゃなかった。

#include <iostream>

using namespace std;


int main(void)
{
	int n, q, m, input;
	int max, max_i;
	int d[100];
	int i, j;


	while( cin >> n >> q, n!=0 || q!=0 ){
		for( i=0; i<100; i++ )
			d[i] = 0;

		for( i=0; i<n; i++ ){
			cin >> m;
			for( j=0; j<m; j++ ){
				cin >> input;
				d[input]++;
			}
		}

		max_i = 0;
		for( i=1; i<100; i++ )
			if( q <= d[i] && d[max_i] < d[i] )
				max_i = i;

		cout << max_i << endl;
	}

	return 0;
}

Problem 2007 : Make Purse Light

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

愚直に全組み合わせを試して、最小値を出力。
ソースがきちゃない。

……全ての硬貨の組み合わせに対して全探索を行いましたが，実はそんなことをしなくても解が求まる方法があります。その方法はとても単純で，「持っている全ての硬貨を店員に渡す」というアイデアです。そうすると店員から最適な枚数が返ってきますが，それは支払うべき金額を払った状況において最小の枚数になっているはずです。ですから，それが求めたかった解なのです。

Make Purse Light 解説

気づかなかった！

#include <iostream>

using namespace std;


int change( int val )
{
	int result = 0;

	result += val/500;
	val = val%500;

	result += val/100;
	val = val%100;

	result += val/50;
	val = val%50;

	result += val/10;

	return result;
}

int main(void)
{
	int price, n, min, new_val;
	int coin[4], result[4];
	int table[4] = { 10, 50, 100, 500 };
	int i, j, k, l;
	bool first = true;

	while( cin >> price, price != 0 ){
		if( !first ) cout << endl;

		n = 0; min = 100;
		for( i=0; i<4; i++ ){
			cin >> coin[i];
			n += coin[i];
			result[i] = 0;
		}

		for( i=0; i<=coin[0]; i++ ){
			for( j=0; j<=coin[1]; j++ ){
				for( k=0; k<=coin[2]; k++ ){
					for( l=0; l<=coin[3]; l++ ){
						if( i*10+j*50+k*100+l*500 < price ) continue;
							new_val = n-(i+j+k+l) + change(i*10+j*50+k*100+l*500-price);
							if( min > new_val ){
								min = new_val;
								result[0] = i; result[1] = j; result[2] = k; result[3] = l;
							}
					}
				}
			}
		}

		for( i=0; i<4; i++ )
			if( result[i] )
				cout << table[i] << " " << result[i] << endl;

		first = false;
	}

	return 0;
}

Problem 1125 : Get Many Persimmon Trees

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

座標を全探索。
英語もやさしめで大変よろしい！

#include <iostream>

using namespace std;


int w, h;
bool map[101][101];

int count( int x, int y, int s, int t ){
	int cnt = 0;

	for( int i=0; i<s; i++ )
		for( int j=0; j<t; j++ )
			if( map[x+i][y+j] )
				cnt++;

	return cnt;
}

int main(void)
{
	int n, x, y, s, t, max, new_val;
	int i, j;


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

		for( i=0; i<=100; i++ )
			for( j=0; j<=100; j++ )
				map[i][j] = false;

		for( i=0; i<n; i++ ){
			cin >> x >> y;
			map[x][y] = true;
		}

		cin >> s >> t;

		max = 0;
		for( i=1; i<=w-s+1; i++ ){
			for( j=1; j<=h-t+1; j++ ){
				new_val = count( i, j, s, t );
				if( max < new_val )
					max = new_val;
			}
		}

		cout << max << endl;
	}

	return 0;
}

Problem 1137 : Numeral System

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

２つの文字列を数字に変換→足し算→結果を文字列に変換→出力
今思うと、文字列の変換と出力を一緒にやってもよかったな…。

#include <iostream>
#include <string>
#include <ctype.h>

using namespace std;


int toInt( string str )
{
	int result = 0, n = 1;
	int i;

	for( i=0; i<str.size(); i++ ){
		if( isdigit(str[i]) ){
			n = str[i] - '0';
		} else {
			switch( str[i] ){
				case 'm' :
					result += n*1000; break;
				case 'c' :
					result += n*100; break;
				case 'x' :
					result += n*10; break;
				case 'i' :
					result += n*1; break;
			}
			n = 1;
		}
	}
	
	return result;
}

string toString( int num )
{
	string result;
	char table[] = { 'm', 'c', 'x', 'i' };
	int i, n;

	n = 1000;
	for( i=0; i<4; i++ ){
		if( num/n ){
			if( num/n != 1 )
				result += '0'+num/n;
			result += table[i];
			num = num%n;
		}
		n /= 10;
	}

	return result;
}

int main(void)
{
	int n;

	string a, b;

	cin >> n;
	while( n-- > 0 ){
		cin >> a >> b;

		cout << toString( toInt(a)+toInt(b) ) << endl;
	}

	return 0;
}