（自身最後の）情報オリンピック予選終わった。

疲れたー。

今回の予選は、サイトがやたら重くて問題なかなか開けず、入力ファイルダウンロードできず、出力ファイル提出できず、な状態で予選が2時間延長。
情オリ委員会の人、お疲れ様でした。

解けた（半分含む）のはQ1~5の5問。去年よりはがんばった！

Q1

問題が開けなくて、解いたのが3番目。ここまでで2時過ぎくらい。
合計金額から入力を引いて出力するだけ。

#include <iostream>

using namespace std;


int main(void)
{
	int price, input;

	cin >> price;
	for( int i=0; i<9; i++ ){
		cin >> input;
		price -= input;
	}

	cout << price << endl;

	return 0;
}

Q2

最初に解いた問題。
単純にシミュレーション。

#include <iostream>
#include <vector>

using namespace std;


int main(void)
{
	int n, m, pos, i, dice;
	vector<int> masu;

	cin >> n >> m;

	masu.resize(n);
	for( i=0; i<n; i++ ){
		cin >> masu[i];
	}

	pos = 0;
	for( i=1; i<=m; i++ ){
		cin >> dice;
		pos += dice;
		if( pos >= n-1 )
			break;
		pos += masu[pos];
		if( pos >= n-1 )
			break;
	}
	cout << i << endl;

	return 0;
}

Q3

再帰とか使って探索するのかと思ったけど、範囲が”友達の友達”までなので、2重ループでいける。

#include <iostream>

using namespace std;

int n, m;
bool table[501][501] = {false};
bool f[501] = {false};

void calc()
{
	int x, i, j;
	queue<int> num;

	for( i=2; i<=n; i++ ){
		if( table[1][i] ){
			f[i] = true;
			for( j=2; j<=n; j++ ){
				if( table[i][j] )
					f[j] = true;
			}
		}
	}

	return;
}

int main(void)
{
	int i, a, b;

	cin >> n;
	cin >> m;

	for( i=0; i<m; i++ ){
		cin >> a >> b;
		table[a][b] = table[b][a] = true;
	}

	calc();

	int cnt = 0;
	for( i=1; i<=n; i++ ){
		if( f[i] ){
			cnt++;
		}
	}
	cout << cnt << endl;

	return 0;
}

Q4

出来うる数字の数がそれほど多くないので、順列を重複なく作って数え上げる。
という作戦を立てたものの、再帰の終了条件とかミスってハマる。かなり時間かかった。
結局間違えてるみたいだし。

// 間違いがある可能性大。あんまりアテにしちゃいけません。
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, k, cnt;
vector<string> input;
vector<string> stock;


bool exist( string s )
{
	for( int i=0; i<stock.size(); i++ )
		if( s == stock[i] ) return true;

	return false;
}

void create( int x, string str, vector<bool> used )
{
	if( x > k ){
		stock.push_back(str);
		cnt++;
		return;
	}

	int i, j;
	string new_str;
	for( i=0; i<n; i++ ){
		if( used[i] ) continue;

		used[i] = true;

		new_str = str+input[i];
		if( !exist(new_str) ){
			create( x+1, new_str, used );
		}

		used[i] = false;
	}

	return;
}

int main(void)
{
	int i;

	cin >> n;
	cin >> k;

	stock.clear();
	input.resize(n);
	for( i=0; i<n; i++ ){
		cin >> input[i];
	}

	vector<bool> used;
	used.resize(n);

	cnt = 0;
	for( i=0; i<n; i++ ){
		used[i] = true;
		create( 2, input[i], used );
		used[i] = false;
	}

	cout << cnt << endl;

	return 0;
}

Q5

時間もそれほどなかったので、深さ優先で愚直に解く。部分点狙い。
15時50分ちょい前に提出できたのだけど、ここで予選が2時間延長になったと知る。
16時から18時まで、枝刈りやら別の解法やら考えていたのだけど結局解けず。

// 出力３までしか解けません。
#include <iostream>
#include <vector>
#include <string>

using namespace std;


#define MAX

int w, h;


int calc( int x, int y, int d )
{
	if( ( x == w && y == h ) || ( x+1 == w && y == h ) || ( x == w && y+1 == h ) )
		return 1;

	int cnt = 0;

	if( d == 1 ){
		if( x+1 <= w )
			cnt += calc( x+1, y, 1 )%100000;
		if( y+2 <= h )
			cnt += calc( x, y+2, 2 )%100000;
	} else {
		if( x+2 <= w )
			cnt += calc( x+2, y, 1 )%100000;
		if( y+1 <= h )
			cnt += calc( x, y+1, 2 )%100000;
	}

	return cnt;
}

int main(void)
{
	int cnt = 0;

	cin >> w >> h;

	cnt += calc( 2, 1, 1 )%100000;
	cnt += calc( 1, 2, 2 )%100000;

	cout << cnt%100000 << endl;

	return 0;
}

ほかの人の解答と答えを照合してみたらQ4の出力2つがミスってたっぽい。
予想だと20+20+20+12+12で84点。通過はどーだろー…。
ちなみに、過去のAランクボーダーは

2008-2009	63点
2007-2008	76点
2006-2007	90点
2005-2006	60点

でも、今年は時間延長したからもっと上がるのかも。

結果は17日（木曜日）頃発表らしい。
落ちたらスッパリ諦めて受験勉強します。