KUPC2012

(感想)難易度が丁度良かったから、5時間ずっと楽しめました。

A.
x*(t/x)でxの倍数でt以下の最大の整数を求めると、TLEしません。

int main(){
	int n,t,e;
	cin>>n>>t>>e;
	for(int i = 1; i <= n; i++){
		int x;
		cin>>x;
		int y = x*(t/x);
		if(t-e<=y||y+x<=t+e){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
	return 0;
}

B.
両端が同じ色のとき、その色のプレーヤーが勝ちます。
それ以外のときは、白が両端を白にするので先手が勝ちます。

int main(){
	string s;
	cin>>s;
	if(s[0]==s[s.size()-1])cout<<s[0]<<endl;
	else cout<<'o'<<endl;
	return 0;
}

C.
頑張って実装する。自分は、嫌いなペアがあるかどうかを考えました。

int n,k,r,boat[50][50],ab[50];
vector<int> ng[50];

int main(){
	cin>>n>>k;
	for(int i = 0; i < k; i++){
		int m;
		cin>>m;
		for(int j = 0; j < m; j++){
			int bunny;
			cin>>bunny;
			boat[i][bunny-1]++;
		}
	}
	cin>>r;
	for(int i = 0; i < r; i++){
		int b1,b2;
		cin>>b1>>b2;
		b1--;b2--;
		ng[b1].push_back(b2);
		ng[b2].push_back(b1);
	}
	for(int i = 0; i < n; i++){
		if(ab[i]||ng[i].empty())continue;
		int l = ng[i].size();
		for(int j = 0; j < l; j++){
			int t = ng[i][j];
			for(int j2 = 0; j2 < k; j2++){
				if(boat[j2][i]&&boat[j2][t]){
					ab[i]=ab[t]=1;
					break;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++)ans+=ab[i];
	cout<<ans<<endl;
	return 0;
}

D.
貪欲法で解けます。
左の部屋から見ていき、左端をカバーしつつ、出来るだけ右までカバーできる教授を見つけ出します。見付け出さなければ"Impossible"を出力します。

vector<pair<int,int> > d;
int n,m;

int main(){
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int a,b;
		cin>>a>>b;
		d.push_back(make_pair(b,a));
	}
	sort(d.begin(),d.end(),greater<pair<int,int> >());
	int pos = 1,res = 0;
	while(pos<=n){
		for(int i = 0; i <= m; i++){
			if(i==m){
				cout<<"Impossible"<<endl;
				return 0;
			}
			int b = d[i].first,a = d[i].second;
			if(a<=pos&&pos<=b){
				res++;
				pos = b+1;
				break;
			}
		}
	}
	cout<<res<<endl;
	return 0;
}

E.
これくらい酷いコードでも、少しずつ変えて何回もsubmitすればいつかは通ると思います。

int n,g[10][10],ai[10],s[10],t[10],put[10],point,win[10];

void update(){
	memset(s,0,sizeof(s));memset(t,0,sizeof(t));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			s[i]+=(g[i][j]*ai[j]);
			t[j]-=(g[i][j]*ai[i]);
		}
	}
}

void decide(){
	for(int i = 0; i < 10; i++){
		int a = rand()%n;
		int b = rand()%n;
		if(i%2){
			put[i]=s[a]>s[b]?a:b;
		}
		else{
			put[i]=t[a]>t[b]?a:b;
		}
	}
	random_shuffle(put,put+n);
}

int main(){
	srand(time(NULL));
	for(int i = 0; i < 10; i++)ai[i]++;
	cin>>n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			char c;
			scanf(" %c",&c);
			if(c=='o')g[i][j]=1;
			if(c=='x')g[i][j]=-1;
		}
	}
	for(int i = 0; i < 10; i++){
		int hand;
		printf("%d\n",rand()%n+1); fflush(stdout);
		scanf("%d", &hand);
		ai[hand-1]+=2;
	}
	update();
	int e = 99;
	for(int c = 0; c < 99; c++){
		if(point<-250){
			e = c;
			break;
		}
		decide();
		for(int i = 0; i < 10; i++){
			int hand;
			printf("%d\n",put[i]+1); fflush(stdout);
			scanf("%d", &hand);
			point+=g[put[i]][hand-1];
			if(g[put[i]][hand-1]>=0){
				win[put[i]]++;
			}
			ai[hand-1]++;
		}
		for(int i = 0; i < 10; i++){
			ai[i] *= 0.9;
			win[i] *= 0.6;
		}
		update();
	}
	for(int c = e; c < 99; c++){
		for(int i = 0; i < 10; i++){
			int hand;
			printf("%d\n",5%n+1); fflush(stdout);
			scanf("%d", &hand);
		}
	}
	
	return 0;
}

F.
シミュレーションで部分点を貰おうとする → RE

G.
UnionFind木を使うと解けます。

x軸か、y軸かでソートすると、枝刈りできますが、それぞれに強いデータが入っているので工夫が必要です。
x座標とy座標のそれぞれで分散を計算して、それが大きい方を基準に枝刈りするようにしたら通りました。

#define x first
#define y second

#define MAX_N 200000
	int par[MAX_N];
	bool united[MAX_N];
struct UF {
	void init(int n){
		for(int i = 0; i < n; i++){
			par[i] = i;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}
	
	void unite(int x, int y){
		united[y] = 1;
		x = find(x);
		y = find(y);
		if(x == y) return;
		par[x] = y;
	}
	
};

int N;
double R;
pair<double,double> p[MAX_N];
const double EPS = 1e-9;

double dist(int a,int b){
	return (p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y);
}

double distx(int a,int b){
	return (p[a].x-p[b].x)*(p[a].x-p[b].x);
}

void var(){
	double avex=0,avey=0;
	for(int i = 0; i < N; i++){
		avex+=p[i].x;avey+=p[i].y;
	}
	avex/=N;avey/=N;
	double sx=0,sy=0;
	for(int i = 0; i < N; i++){
		sx+=(avex-p[i].x)*(avex-p[i].x);
		sy+=(avey-p[i].y)*(avey-p[i].y);
	}
	if(sx<sy){
		for(int i = 0; i < N; i++){
			swap(p[i].x,p[i].y);
		}
	}
}

int main(){
	cin>>N>>R;
	for(int i = 0; i < N; i++)cin>>p[i].x>>p[i].y;
	var();
	UF uf;
	uf.init(N);
	sort(p,p+N);
	for(int i = 0; i < N; i++){
		if(!united[i]){
			for(int j = i+1; j < N; j++){
				if(distx(i,j)>R*R+EPS)break;
				if(dist(i,j)<=R*R+EPS){
					uf.unite(i,j);
				}
			}
		}
	}
	int res = 0;
	for(int i = 0; i < N; i++){
		if(i==uf.find(i))res++;
	}
	cout<<res<<endl;
	return 0;
}

H.
ある点の縦と横にある0の個数の奇数である点の縦横にある点の偶奇を入れ替えると、全て奇数になります。証明はまだ思いついていません。

追記:
正しいかわからないけど、一応考えてみた

ある点(a,b)の縦横の列とその点にある0の個数を2で割ったものをf(a,b)とする。
h,wは偶数であるため、ある点(a,b)とそれの縦横の列にある数字の偶奇を入れ替えると、f(a,b)だけ入れ替わって、他は入れ替わらない。
状態が2^(h*w)通りあるので、
∀a,b f(a,b) = 0
となるのは、全てのマスが1であるときだけであることが分かる (q.e.d.)

また、このことから任意の状態から、全てのマスを1にすることができ、出力は1通りしか無いことが分かる。

int h,w,g[1000][1000],gi[1000],gj[1000],gij[1000][1000];

int main(){
	scanf("%d%d",&h,&w);
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			scanf("%d",g[i]+j);
			g[i][j] = 1-g[i][j];
		}
	}
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			gi[i]+=g[i][j];
			gj[j]+=g[i][j];
		}
	}
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			gij[i][j] = gi[i]+gj[j]-g[i][j];
		}
	}
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			printf("%d",gij[i][j]&1);
			if(j!=w-1)printf(" ");
		}
		printf("\n");
	}
	return 0;
}

37thでした。