Volume 0 / 0036->0042

Problem 0035 : Is it Convex?

パス。

Problem 0036 : A Figure on Surface

長くなっちゃった。

#include <iostream>

using namespace std;


int main(void)
{
	int pat[7][4][4] = {
		{{0,0,0,0},
		 {0,1,1,0},
		 {0,1,1,0},
		 {0,0,0,0}},
		{{0,1,0,0},
		 {0,1,0,0},
		 {0,1,0,0},
		 {0,1,0,0}},
		{{0,0,0,0},
		 {1,1,1,1},
		 {0,0,0,0},
		 {0,0,0,0}},
		{{0,0,1,0},
		 {0,1,1,0},
		 {0,1,0,0},
		 {0,0,0,0}},
		{{0,0,0,0},
		 {1,1,0,0},
		 {0,1,1,0},
		 {0,0,0,0}},
		{{0,1,0,0},
		 {0,1,1,0},
		 {0,0,1,0},
		 {0,0,0,0}},
		{{0,0,0,0},
		 {0,0,1,1},
		 {0,1,1,0},
		 {0,0,0,0}},
	};
	int p[14][14], i, j, x0, y0, t, x, y;
	char let[7] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }, ch;
	bool flag = false;

	while( cin.get(ch) ){
		if( ch == '\n' )
			continue;
		else
			cin.putback(ch);

		for( i=0; i<14; i++)
			for( j=0; j<14; j++ )
				p[i][j] = 0;

		for( i=3; i<11; i++){
			for( j=3; j<11; j++ ){
				cin.get(ch);
				if( ch == '0' )
					p[i][j] = 0;
				if( ch == '1' )
					p[i][j] = 1;
			}
			cin.get(ch);
		}

		for( y0=0; y0<11; y0++){
			for( x0=0; x0<11; x0++ ){
				for( t=0; t<7; t++ ){
					for( y=0; y<4; y++ ){
						for( x=0; x<4; x++ ){
							if( p[y0+y][x0+x] != pat[t][y][x] )
								break;
						}
						if( x != 4 ) break;
					}
					if( y == 4 ){
						cout << let[t] << endl;
						flag = true;
						break;
					}
					if( flag ) break;
				}
				if( flag ) break;
			}
			if( flag ) break;
		}

	}

	return 0;
}

Problem 0037 : Path on a Grid

#include <iostream>

using namespace std;

void calc( int prev, int x, int y, bool p[5][5][4], bool firstFlag ){
	if( firstFlag == false && x == 0 && y == 0 )
		return;

	int v[4] = { 3, 0, 1, 2 },
		vx[4] = { 0, 1, 0, -1 },
		vy[4] = { -1, 0, 1, 0 },
		i, a;
	char let[4] = { 'U', 'R', 'D', 'L' };

	for( i=0; i<4; i++ ){
		if( p[y][x][v[(prev+i)%4]] ){
			a = v[(prev+i)%4];
			cout << let[a];
			calc( a, x+vx[a], y+vy[a], p, false );
			break;
		}
	}

	return;

}

int main(void)
{
	bool p[5][5][4];
	int i, j, k;
	char ch;

	for( i=0; i<5; i++ ){
		for( j=0; j<5; j++ ){
			for( k=0; k<4; k++ ){
				p[i][j][k] = false;
			}
		}
	}

	for( i=0; i<5; i++ ){
		for( j=0; j<4; j++ ){
			cin.get(ch);
			if( ch == '1' )
				p[i][j][1] = p[i][j+1][3] = true;
		}

		cin.get(ch);
		if( i == 4 ) break;

		for( j=0; j<5; j++ ){
			cin.get(ch);
			if( ch == '1' )
				p[i][j][2] = p[i+1][j][0] = true;
		}
		cin.get(ch);
	}

	calc( 1, 0, 0, p, true );

	cout << endl;

	return 0;
}

Problem 0038 : Poker Hand

#include <iostream>

using namespace std;


int main(void)
{
	int cards[5], cnt[13], i;
	bool fin = false;
	
	while( scanf("%d,%d,%d,%d,%d", &cards[0], &cards[1], &cards[2], &cards[3], &cards[4] ) != -1 ){
		fin = false;

		for( i=0; i<13; i++ )
			cnt[i] = 0;

		for( i=0; i<5; i++ )
			cnt[cards[i]-1]++;

		fin = false;
		for( i=0; i<13 && !fin; i++ ){
			if( cnt[i] == 4 ){
				cout << "four card" << endl;
				fin = true;
			}
		}

		bool three, two;
		three = two = false;
		for( i=0; i<13 && !fin; i++ ){
			if( cnt[i] == 3 ) three = true;
			if( cnt[i] == 2 ) two = true;
			if( three && two ){
				cout << "full house" << endl;
				fin = true;
			}
		}

		for( i=0; i<10 && !fin; i++ ){
			if( cnt[i] && cnt[i+1] && cnt[i+2] && cnt[i+3] && cnt[(i+4)%13] ){
				cout << "straight" << endl;
				fin = true;
			}
		}

		int cnt_two = 0;
		for( i=0; i<13 && !fin; i++ ){
			if( cnt[i] == 3 ){
				cout << "three card" << endl;
				fin = true;
			} else if( cnt[i] == 2 ){
				cnt_two++;
			}
		}
		if( cnt_two == 2 ){
			cout << "two pair" << endl;
		} else if( cnt_two == 1 ){
			cout << "one pair" << endl;
		} else if( !fin ) {
			cout << "null" << endl;
		}

	}

	return 0;
}

Problem 0039 : Roman Figure

#include <iostream>
#include <string>

using namespace std;


int is_small( char ch, int n, char c_table[7] ){

	for( int i=0; i<n; i++ )
		if( ch == c_table[i] )
			return i;

	return -1;
}

int main(void)
{
	string str;
	int num, cnt, i;
	char c_table[7] = { 'I', 'V', 'X', 'L', 'C', 'D', 'M' };
	int n_table[7] = { 1, 5, 10, 50, 100, 500, 1000 };

	while( cin >> str ){
		num = 0; cnt = 0;
		for( i=str.size()-1; i>=0; i-- ){
			if( str[i] == c_table[cnt] ){
				num += n_table[cnt];
			} else if( is_small( str[i], cnt, c_table ) != -1 ){
				num -= n_table[is_small( str[i], cnt, c_table )];
			} else {
				cnt++;
				i++; continue;
			}
		}
		cout << num << endl;
	}
	return 0;
}

Problem 0040 : Affine Cipher（未）

パス。

Problem 0041 : Expression（未）

パス。

Problem 0042 : A Thief

2011.08.11 修正

#include <iostream>
#include <climits>

using namespace std;


int main(void)
{
	int a[1000], b[1000];	// お宝の価値と重さ
	int value[1001] = {0};	// 重さ制限がiのときの価値の総和の最大値をvalue[i]とする
	int weight[1001] = {INT_MAX};	// 重さ制限がiのときの価値の総和の最大となるときの重さをweight[i]とする
	int value_temp[1001] = {0};	// 作業用
	int weight_temp[1001] = {INT_MAX}; // 作業用
	int count, w, n, new_value, new_weight, p;
	int i, j;

	count = 0;

	// 風呂敷の耐えられる重さ
	while( cin >> w, w != 0 ){
		count++;

		// お宝の数
		cin >> n;
		for( i=0; i<n; i++ ){
			// お宝の価値と重さ
			scanf("%d,%d", &a[i], &b[i] );
		}

		//　初期化
		for( i=0; i<=w; i++ ){
			value[i] = 0;
			weight[i] = INT_MAX;
		}

		// お宝を順番に調査
		for( i=0; i<n; i++ ){
			// 1つ前のお宝までを調査した結果を保存
			for( j=0; j<=w; j++ ){
				value_temp[j] = value[j];
				weight_temp[j] = weight[j];
			}

			for( j=b[i]; j<=w; j++ ){
				// 袋の空きスペース
				p = j - b[i];
				new_value = value_temp[p] + a[i];
				new_weight = ( weight_temp[p] == INT_MAX ) ? b[i] :  weight_temp[p] + b[i];
				// 新しい値のほうが既存の値以上ならば
				if( new_value >= value[j] ){
					// ※新しい値と既存の値が等しく、重さが上回るときは更新しない
					if( new_value > value[j] || new_weight <= weight[j] ){
						value[j] = new_value;
						weight[j] = new_weight;
					}
				}
			}
		}

		cout << "Case " << count << ":" << endl;
		cout << value[w] << endl;
		cout << weight[w] << endl;

	}
	return 0;
}

美しくはないですが。解けてるみたいです。

以前のひどいコードは↓
"Wrong Answer"
う〜ん、どこが間違ってるんだろ。

#include <iostream>

using namespace std;



int main(void)
{
	int a[1000], b[1000];
	int value[1001] = {0};
	int w, n, min_w, new_value, p, i, j;

	cin >> w;
	for( i=0; i<=w; i++ )
		value[i] = 0;

	cin >> n;
	min_w = w;
	for( i=0; i<n; i++ ){
		scanf("%d,%d", &a[i], &b[i] );
	}

	for( i=0; i<n; i++ ){
		for( j=b[i]; j<=w; j++ ){
			p = j - b[i];
			new_value = value[p] + a[i];
			if( new_value > value[j] ){
				value[j] = new_value;
			}
		}
	}

	cout << value[w] << endl;

	return 0;
}

とりあえず問題の条件を満たしていない。しっかり！
それから、お宝の重複を許してしまっている。あるお宝を取り上げて最適解を更新するときに、そのお宝自体を使っているときの最適解を評価の対象にしてしまっているのがだめ。修正版ではそのお宝がまだ使われていない時点での最適解を評価の対象とした。(2011.08.11)