Volume 5 / 0538->0540

情報オリンピック 2009本選 解答
難しい……。データが大きくなるとダメダメ。

Problem 0538 : IOIOI / IOIOI

BM法でやると時間切れになる。愚直にカウントして解いた。

#include <iostream>

using namespace std;


int main(void)
{
	int n, m, cnt, result, i, j;
	char ch = ' ';

	while( cin >> n, n!= 0 ){
		cin >> m; cin.get(ch);
		result = 0;
		do {
			cin.get(ch);
			if( ch == 'I' ){
				for( cnt=0; ; cnt++ ){
					cin.get(ch);
					if( ch == '\n' )
						break;
					if( ch == 'I' ){
						cin.putback(ch);
						break;
					}

					cin.get(ch);
					if( ch != 'I' )
						break;
				}
				result += ( cnt-n >= 0 ) ? 1 + cnt-n : 0;
			}
		} while( ch != '\n' );

		cout << result << endl;
	}

	return 0;
}

Problem 0539 : Pizza / ピザ

店の位置をソートするために、はじめはvectorじゃなくてsetを使っていたのだけど、それよりvectorで保存して後でソートしたほうが早いみたい。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main(void)
{
	int d, n, m, k, i, input, sum, a, b;
	vector<int> shops;
	vector<int>::iterator it;

	while( cin >> d, d != 0 ){
		cin >> n;
		cin >> m;
		shops.clear();
		for( i=0; i<n-1; i++ ){
			cin >> input;
			shops.push_back(input);
		}

		sort( shops.begin(), shops.end() );

		sum = 0;
		for( i=0; i<m; i++ ){
			cin >> k;
			it = upper_bound( shops.begin(), shops.end(), k );
			if( it != shops.end() ){
				a = *it - k;
			} else {
				a = d - k;
			}

			if( it != shops.begin() ){
				it--; b = k - *it;
			} else {
				b = k;
			}

			sum += min( a, b );
		}

		cout << sum << endl;
	}

	return 0;
}

Problem 0540 : Amidakuji / あみだくじ（未）

たぶん時間切れになるから未提出。
sort()を使って構造体の配列をソートするのは初めてだった。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct BAR {
	int a, b;
};


// 構造体のソート
bool bar_cmp( const BAR &left, const BAR &right ){
	if( left.b == right.b )
		return left.a < right.a;
	return left.b < right.b;
}


int solve( int x, int k, vector<int> amida, vector<BAR> bars )
{
	int i;
	int tmp;
	for( i=bars.size()-1; i>=0; i-- ){
		if( i != x ){
			tmp = amida[bars[i].a-1];
			amida[bars[i].a-1] = amida[bars[i].a];
			amida[bars[i].a] = tmp;
		}
	}

	int sum = 0;
	for( i=0; i<k; i++ )
		sum += amida[i];

	return sum;
}

int main(void)
{
	int n, m, h, k, i;
	vector<int> amida;
	vector<BAR> bars;

	while( cin >> n >> m >> h >> k, n != 0 ){
		amida.resize(n);
		for( i=0; i<n; i++ )
			cin >> amida[i];

		bars.resize(m);
		for( i=0; i<m; i++ )
			cin >> bars[i].a >> bars[i].b;

		sort( bars.begin(), bars.end(), bar_cmp );

		int result = solve( -1, k, amida, bars );
		int new_val;
		for( i=0; i<m; i++ ){
			new_val = solve( i, k, amida, bars );
			if( result > new_val )
				result = new_val;
		}

		cout << result << endl;
	}
	return 0;
}