UTPC2012

東京大学プログラミングコンテスト2012 に先週参加してました。
期末テストから解放されたので記事書きます。
A:100
B:100
C:50
F:0.52
合計 250.52
順位 66位
でした。
実力相応です。

A

#include <cstdio>
#include <algorithm>
using namespace std;

int y, m, d;
bool u[4];
int a[4];
bool solve(int n, int s){
	if(n == 4){
		if(s == y) return true;
		else return false;
	}
	bool f = false;
	for(int i = 0; i < 4; i++){
		if(!u[i]){
			u[i] = true;
			f = f||solve(n+1, s * 10 + a[i]);
			u[i] = false;
		}
	}
	return f;
}
int main(){
	scanf("%d/%d/%d", &y, &m, &d);
	a[0] = m/10; a[1] = m%10; a[2] = d/10; a[3]=d%10;
	fill(u, u + 4, false);
	if(solve(0,0))
		printf("yes\n");
	else
		printf("no\n");
	return 0;
}

B

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string str;
int L;
bool u[8];
char s[9];

bool c(){
	int p = -1;
	for(int i = 0; i < 8; i++){
		char l = s[i];
		int j;
		for(j = L-1; str[j] != l && j >= 0; j--){;}
		if(!(p <= j))
			return false;
		p = j;
	}
	return true;
}
bool solve(int n){
	if(n == 8){
			//printf("%s\n",s);
		if(c()){
			printf("%s\n",s);
			return true;
		}else{
			return false;
		}
	}
	for(int i = 0; i < 8; i++){
		if(!u[i]){
			u[i] = true;
			s[n] = 'A' + i;
			if(solve(n + 1))
				return true;
			u[i] = false;
		}
	}
	return false;
}
int main(){
	cin >> str;
	L = str.size();
	fill(u, u + 8, false);
	solve(0);
	return 0;
}

C(50)

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 100;
int N, M;
int a[MAX_N][MAX_N];
bool u[MAX_N];
bool ua[MAX_N][MAX_N];
bool c(int v){
	bool f = true;
	for(int i = 0; i < N; i++){
		if(a[v][i] == 1){
			if(!u[i]){
				ua[v][i] = true;
				ua[i][v] = true;
				u[i] = true;
				f = f&&c(i);
			}else if(!ua[v][i]){
				return false;
			}
		}
	}
	return f;
}
int main(){
	scanf("%d %d", &N, &M);
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++){
			if(i != j)a[i][j] = 1;
	}
	for(int i = 0; i < M; i++){
		int s, t;
		scanf("%d %d", &s, &t);
		s--; t--;
		if(a[s][t] == 1){
			a[s][t] = 0; a[t][s] = 0;
		}else{
			a[s][t] = 1; a[t][s] = 1;
		}
		bool f = true;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++)
				for(int k = 0; k < N; k++) ua[j][k] = false;
			fill(u, u+MAX_N, false);
			u[i] = true;
			f = f && c(i);
		}
		if(f)
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}

F(0.52)

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
ll A, B;
ll mod_pow(ll a, ll n){
	ll ret = 1;
	ll t = a;
	while(n){
		if(n&1)
			ret = ret * t % B;
		t = t * t % B;
		n >>= 1;
	}
	return ret;
}

int main(){
	scanf("%lld %lld", &A, &B);
	for(int i = 1; i < 50; i++){
		if(mod_pow(A, i) == 0){
			for(int j = 0; j < 26  ; j++){
				printf("%c", 'a' + j);
				for(int k = 1; k <= i; k++){
					printf("a");
				}
				puts("");
			}
			return 0;
		}
	}
	return 0;
}

Cの解きなおし
C(100)

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1001;
int N, M;
vector<int> G[MAX_N];
bool u[MAX_N];
bool c(int p, int v){
	u[v] = true;
	for(int i = 0; i < G[v].size(); i++){
		int t = G[v][i];
		if(t == p) continue;
		if(u[t])
			return false;
		if(!c(v, t))
			return false;
	}
	return true;
}
int main(){
	scanf("%d %d", &N, &M);
	int n = N * (N - 1) / 2;
	if(M < n - (N - 1) || N > 1000){
		for(int i = 0; i < M; i++)
			puts("no");
		return 0;
	}
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(i == j) continue;
			G[i].push_back(j);
		}
	}
	for(int i = 0; i < M; i++){
		int s, t;
		scanf("%d %d", &s, &t);
		s--;
		t--;
		bool f = false;
		for(int j = 0; j < G[s].size(); j++){
			if(G[s][j] == t){
				f = true;
				vector<int>::iterator it = G[s].begin() + j;
				G[s].erase(it);
				break;
			}
		}
		if(f){
			for(int j = 0; j < G[t].size(); j++){
				if(G[t][j] == s){
					vector<int>::iterator it = G[t].begin() + j;
					G[t].erase(it);
					break;
				}
			}
			n--;
		}else{
			G[t].push_back(s);
			G[s].push_back(t);
			n++;
		}
		if(n < N){
			fill(u, u + MAX_N, false);
			bool b = true;
			for(int i = 0; i < N; i++){
				if(!u[i] && !c(-1, i)){
					b = false;
					break;
				}
			}
			if(b) puts("yes");
			else puts("no");
		}else{
			puts("no");
		}
	}
	return 0;
}