情報オリンピック 第9回予選問題

Programming Algorithm AOJ JOI

JOI対策の一環で解いた。

AOJ in JOI,PCK 回別リスト - 簡潔なQ
ありがてえありがてえqnighyさんありがとうございます。

AOJ 0543 Receipt

404 Not Found

#include <cstdio>
int main()
{
	int total;
	while(scanf("%d\n", &total), total){
		int others = 0;
		for(int i = 0; i < 9; i++){
			int t;
			scanf("%d\n", &t);
			others += t;
		}
		printf("%d\n", total - others);
	}
	return 0;
}

FizzBuzz的問題。

AOJ 0544 Sugoroku

404 Not Found

#include <cstdio>
#include <vector>
using namespace std;
int main()
{
	int N, M;
	while(scanf("%d %d\n", &N, &M), N || M){
		vector<int> v(N), w(M);
		for(int i = 0; i < N; i++) scanf("%d\n", &v[i]);
		for(int i = 0; i < M; i++) scanf("%d\n", &w[i]);
		for(int i = 0, p = 0; i < M; i++){
			if((p += w[i]) >= N){ printf("%d\n", i + 1); break; }
			p += v[p];
			if(p >= (N - 1)){ printf("%d\n", i + 1); break; }
		}
	}
	return 0;
}

もうちょっときれいに解けるかなーとか解けないかなーとか

AOJ 0545 Party

404 Not Found

#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int main()
{
	int n, m;
	while(scanf("%d\n%d\n", &n, &m), n ||Party m){
		vector<vector<int> > v(n);
		set<int> se;
		for(int i = 0; i < m; i++){
			int a, b;
			scanf("%d %d\n", &a, &b);
			a--;b--;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		for(int i = 0; i < v[0].size(); i++){
			se.insert(v[0][i]);
			for(int j = 0; j < v[v[0][i]].size(); j++){
				se.insert(v[v[0][i]][j]);
			}
		}
		se.erase(0);
		printf("%d\n", se.size());
	}
	return 0;
}

そこそこきれいに解けたと思う。

AOJ 0546 Lining up the cards

404 Not Found

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
long long fact(long long x){
	long long y = x;
	if(x == 0) return 0;
	while(--x) y *= x;
	return y;
}

int main()
{
	int n, k;
	while(scanf("%d\n%d\n", &n, &k), n || k){
		vector<int> v(n);
		set<vector<int> > se;
		set<string> tf;
		for(int i = 0; i < n; i++) scanf("%d\n", &v[i]);
		for(int i = 0; i < (1 << n); i++){
			int c = 0;
			for(int j = 0; j < n; j++)
				if(i & (1 << j)) c++;
			if(c != k) continue;
			vector<int> w;
			for(int j = 0; j < n; j++)
				if(i & (1 << j)) w.push_back(v[j]);
			sort(w.begin(), w.end());
			if(se.find(w) == se.end()){
				se.insert(w);
				do {
					stringstream ss;
					for(vector<int>::iterator it = w.begin(); it != w.end(); it++){
						ss<<*it;
					}
					tf.insert(ss.str());
				} while(next_permutation(w.begin(), w.end()));
			}
		}
		printf("%d\n", tf.size());
	}

	return 0;
}

最初問題を読み違えてさらにその読み違えた解法のデバッグとかでかなり時間くった、こういうの本番だと致命的やよなあ。

AOJ 0547 Commute routes

404 Not Found

#include <cstdio>
#include <map>
#include <algorithm>
#define X 1
#define Y 2
using namespace std;
int w, h;
class quad_memo {
private:
	map<pair<int, int>, map<pair<int, int>, long long> > m;
public:
	inline bool empty(int a, int b, int c, int d){
		return m[make_pair(a, b)].find(make_pair(c, d)) == m[make_pair(a, b)].end();
	}
	inline long long get(int a, int b, int c, int d){
		return m[make_pair(a, b)][make_pair(c, d)];
	}
	inline long long set(int a, int b, int c, int d, long long e){
		return m[make_pair(a, b)][make_pair(c, d)] = e % 100000;
	}
	inline void clear(){
		m.clear();
		return;
	}
};
quad_memo qm;
long long dfs(int x, int y, int vector, int prev){
	if(!qm.empty(x, y, vector, prev)){
		return qm.get(x, y, vector, prev);
	}

	if(x == w && y == h) return qm.set(x, y, vector, prev, 1);

	long long total = 0;
	
	if(vector == 0){
		if((x + 1) <= w) total += dfs(x + 1, y, X, 0);
		if((y + 1) <= h) total += dfs(x, y + 1, Y, 0);
	}else if(vector == X){
		if((x + 1) <= w) total += dfs(x + 1, y, X, 0);
		if(!prev && ((y + 1) <= h)) total += dfs(x, y + 1, Y, 1);
	}else if(vector == Y){
		if(!prev &&((x + 1) <= w)) total += dfs(x + 1, y, X, 1);
		if((y + 1) <= h) total += dfs(x, y + 1, Y, 0);
	}

	return qm.set(x, y, vector, prev, total);
}
int main()
{
	while(scanf("%d %d\n", &w, &h), w || h){
		w--, h--;
		qm.clear();
		printf("%lld\n", dfs(0, 0, 0, 0) % 100000);
	}
	return 0;
}

メモ化再帰化に時間かけすぎた。しかもこれ多分世界一汚ないメモ化配列だろ。ダラダラ解いたのもあるけど1時間ぐらいかけてた気もする。これじゃまだまだだなあ…

AOJ 0548 Reindeer with no sense of direction

404 Not Found
Not solved