第6回 JOI2007年 日本情報オリンピック 本選 ソースコード 解答

n回もといているのでさすがに短時間で全完できた。

第一問

やるだけ

#include <bits/stdc++.h>
using namespace std;

int n,ans;
int sum;
int d[100005];
int k;

int main(){
	while(1){
	scanf("%d%d",&n,&k);
	if(n+k == 0)break;
	ans = 0;
	sum = 0;
	for(int i = 1;i <= n;i++){
		scanf("%d",&d[i]);
	}

	for(int i = 1;i <= k;i++){
		sum += d[i];
	}

	ans = sum;

	for(int i = k+1;i <= n;i++){
		sum += d[i] - d[i-k];
		ans = max(ans,sum);
	}
	printf("%d\n",ans);
	}
	return 0;
}

第二問

やるだけ

#include <bits/stdc++.h>
using namespace std;

int n,k,ren[100005],ans;
bool ch[100005];

int main(){
	while(1){
		scanf("%d%d",&n,&k);
		if(n+k == 0)break;
		ans = 0;
		for(int i = 0;i <= n+1;i++) ch[i]=false,ren[i]=0;
		for(int i = 1;i <= k;i++){
			int t;
			scanf("%d",&t);
			ch[t] = true;
		}

		for(int i = 1;i <= n;i++){
			if(ch[i] == true){
				ren[i] = ren[i-1] + 1;
			}else{
				ren[i-ren[i-1]] = ren[i-1];
			}
			ans = max(ans,ren[i]);
		}
		ren[n+1-ren[n]] = ren[n];

		if(ch[0] == true){
			for(int i = 1;i <= n;i++){
				if(ch[i] == true)continue;
				ans = max(ans,ren[i-1]+1+ren[i+1]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

第三問

やるだけ
柱の検出にbool配列使った方がはやいけどあえてSTLのset使った。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int n,d[3004][2],ans;

int nj(int a){
	return (a*a);
}

int main(){
	while(1){
		ans = 0;
		scanf("%d",&n);
		if(n == 0)break;
		set<P> s;
		for(int i = 0;i < n;i++){
			scanf("%d%d",&d[i][0],&d[i][1]);
			s.insert(P(d[i][0],d[i][1]));
		}

		for(int i = 0;i < n-1;i++){
			for(int j = i+1;j < n;j++){
				if(nj(d[i][0]-d[j][0])+nj(d[i][1]-d[j][1]) <= ans)continue;
				int x1 = d[i][0];
				int y1 = d[i][1];
				int x2 = d[j][0];
				int y2 = d[j][1];

				int x3 = x1 + y1 - y2;
				int y3 = y1 + x2 - x1;
				int x4 = x2 + y1 - y2;
				int y4 = y2 + x2 - x1;
				set<P>::iterator it;
				it = s.find(P(x3,y3));
				if(it != s.end()){
					it = s.find(P(x4,y4));
					if(it != s.end()){
						ans = nj(x1-x2)+nj(y1-y2);
						continue;
					}
				}
				int h1 = y1 - y2;
				int h2 = x2 - x1;

				x3 = x1 - h1;
				y3 = y1 - h2;
				x4 = x2 - h1;
				y4 = y2 - h2;
				it = s.find(P(x3,y3));
				if(it != s.end()){
					it = s.find(P(x4,y4));
					if(it != s.end()){
						ans = nj(x1-x2)+nj(y1-y2);
						continue;
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

第四問

トポロジカルソートやるだけ

#include <bits/stdc++.h>
using namespace std;

int n,m,ans[5004],co;
bool used[5004];
vector<int> maketa[5004];

void dfs(int a){
	if(used[a] == true)return;
	used[a] = true;
	for(int i = 0;i < maketa[a].size();i++){
		dfs(maketa[a][i]);
	}
	ans[co++] = a;
}

int main(){
	scanf("%d%d",&n,&m);

	for(int i = 0;i < m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		maketa[b].push_back(a);
	}

	for(int i = 1;i <= n;i++)dfs(i);

	bool flag = false;
	for(int i = 1;i < co;i++){
		for(int j = 0;j < maketa[ans[i]].size();j++){
			if(maketa[ans[i]][j] == ans[i-1])goto out;
		}
		flag = true;
		break;
		out:
		;
	}

	for(int i = 0;i < co;i++){
		printf("%d\n",ans[i]);
	}
	if(flag){
		printf("1\n");
	}else{
		printf("0\n");
	}
	return 0;
}

第五問

ユークリッド互除法乱用するだけ
頭悪いのでint型に収まり切らなかったからしかたなくlong longつかった

#include <bits/stdc++.h>
using namespace std;
typedef long long  lli;
lli n,d[120][4];
bool used[120];

lli sks(lli a,lli b){
	if(b > a)swap(a,b);
	if(b == 0)return a;
	return sks(b,a%b);
}

lli dfs(lli a){
	if(a == 0)return -1;
	lli res = 0;
	lli l = dfs(d[a][2]),r = dfs(d[a][3]);
	if(l == -1 && r == -1){
		return (d[a][0]+d[a][1]);
	}else if(l != -1 && r != -1){
		lli x = (l*d[a][0])*(r*d[a][1])/sks(l*d[a][0],r*d[a][1]);
		return (x/d[a][0]+x/d[a][1]);
	}else{
		lli ll = d[a][0],rr = d[a][1];
		if(l == -1){
			swap(l,r);
			swap(ll,rr);
		}
		lli x = (l*ll)*rr/sks(l*ll,rr);
		return (x/ll+x/rr);
	}
}


	

int main(){
	while(1){
	scanf("%lld",&n);
	if(n == 0)break;
	for(lli i = 0;i <= n;i++)used[i] = false;
	for(lli i = 1;i <= n;i++){
		for(lli j = 0;j < 4;j++){
			scanf("%lld",&d[i][j]);
		}
		lli wa = sks(d[i][0],d[i][1]);
		d[i][0] /= wa;
		d[i][1] /= wa;
		used[d[i][2]] = true;
		used[d[i][3]] = true;
	}

	for(lli i = 1;i <= n;i++){
		if(used[i] == false)printf("%lld\n",dfs(i));
	}
	for(lli i = 1;i <= n;i++){
		//cout << "dfs" << i << "is " << dfs(i) << endl;
	}
	}
	return 0;
}