第７回日本情報オリンピック 予選 過去問 解答

一応といてみた（n回目）
解説はJOI 2007-2008 予選 問題・データにあるのでそっちを見てください。

サンプルソースだけﾄﾞﾃﾞﾝとはっておきます。
続きを読むでよめる・

このぐらいのセットは30分で全完しないとだめだよな・・・

1

#include <bits/stdc++.h>

using namespace std;
int c[6] = {500,100,50,10,5,1};
int main(){

	int n;
	scanf("%d",&n);

	n = 1000 - n;
	int ans = 0;

	for(int i = 0;i < 6;i++){
		ans += (n / c[i]);

		n = n % c[i];
	}

	printf("%d\n",ans);

	return 0;

}

2

#include <bits/stdc++.h>

using namespace std;

int main(){

	char s[10003];

	cin >> s;

	int len = strlen(s);

	int joi=0,ioi=0;

	for(int i = 0;i < len - 2;i++){
		if(s[i+1] == 'O' && s[i+2] == 'I'){
			if(s[i] == 'J'){
				joi++;
			}else if(s[i] == 'I'){
				ioi++;
			}
		}
	}
	printf("%d\n%d\n",joi,ioi);

	return 0;
}

3

#include <bits/stdc++.h>

using namespace std;
int n;
int t[202];
int h[202];
int main(){

	scanf("%d",&n);

	for(int i = 0;i < n;i++){
		int tmp;
		scanf("%d",&tmp);
		t[tmp] = 1;
	}
	for(int i = 1;i <= n*2;i++){
		if(t[i] != 1){
			h[i] = 1;
		}
	}

	int tk  = n,hk = n;
	int ba = 0;
	bool ban = true;
	while(tk > 0 && hk > 0){
		if(ban){
			ban = false;
			for(int i = ba;i <= n*2;i++){
				if(t[i] == 1){
					t[i] = 0;
					tk--;
					ba = i;
					goto out;
				}
			}
		}else{
			ban = true;
			for(int i = ba;i <= n*2;i++){
				if(h[i] == 1){
					h[i] = 0;
					hk--;
					ba = i;
					goto out;
				}
			}
		}
		ba = 0;
		out:
		;
	}
	printf("%d\n%d\n",hk,tk);
	return 0;
}

4

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> P;
int ch[202][2];
int d[1002][2];
int main(){
	int m,n;
	set<P> s;
	scanf("%d",&m);
	for(int i = 0;i < m;i++){
		scanf("%d%d",&ch[i][0],&ch[i][1]);
	}
	scanf("%d",&n);
	for(int i = 0;i < n;i++){
		cin >> d[i][0] >> d[i][1];
		s.insert(P(d[i][0],d[i][1]));
	}
	int x,y;
	for(int i = 0;i < n;i++){
		x = d[i][0] - ch[0][0];
		y = d[i][1] - ch[0][1];
		for(int j = 1;j < m;j++){
			int nx = ch[j][0] + x;
			int ny = ch[j][1] + y;
			set<P>::iterator it = s.find(P(nx,ny));
			if(it == s.end()){
				goto out;
			}
		}
		break;
		out:
		;
	}
	printf("%d %d\n",x,y);

	return 0;
}

5

#include <bits/stdc++.h>

using namespace std;
int r,c;
bool ch[11][10002];
int main(){
	int ans = 0;
	scanf("%d%d",&r,&c);

	for(int i = 0;i < r;i++){
		for(int j = 0;j < c;j++){
			int tmp;
			scanf("%d",&tmp);
			if(tmp == 1){
				ch[i][j] = true;
			}else{
				ch[i][j] = false;
			}
		}
	}
	bool u[11];
	for(int i = (1 << r) - 1;i >= 0;i--){
		int tmpans = 0;
		for(int j = 0;j < r;j++){
			if(i >> j & 1){
				u[j] = true;
			}else{
				u[j] = false;
			}
		}
		for(int j = 0;j < c;j++){
			int co = 0;
			for(int k = 0;k < r;k++){
				if(u[k] == false && ch[k][j] == true)co++;
				if(u[k] == true && ch[k][j] == false)co++;
			}
			tmpans += max(co,r-co);
		}
		ans = max(ans,tmpans);
	}

	printf("%d\n",ans);

	return 0;
}

6

#include <bits/stdc++.h>

using namespace std;
const int INF = 100000000;
typedef pair<int,int> P;
struct edge{int to,cost;};
int n,k;
vector<edge> e[101];
int d[101];

void dijkstra(int x){
	for(int i = 1;i <= n;i++){
		d[i] = INF;
	}
	d[x] = 0;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,x));
	while(que.size()){
		P p = que.top(); que.pop();
		if(p.first > d[p.second])continue;
		for(int i = 0;i < e[p.second].size();i++){
			edge es = e[p.second][i];
			if(d[es.to] > p.first + es.cost){
				d[es.to] = p.first + es.cost;
				que.push(P(d[es.to],es.to));
			}
		}
	}
}


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

	for(int i = 0;i < k;i++){
		int hyo;
		scanf("%d",&hyo);
		if(hyo == 0){
			int a,b;
			scanf("%d%d",&a,&b);

			dijkstra(a);
			int ans = d[b];
			if(ans == INF){
				printf("-1\n");
			}else{
				printf("%d\n",ans);
			}
		}else{
			int a1,a2,a3;
			scanf("%d%d%d",&a1,&a2,&a3);
			edge tmp = {a2,a3};
			e[a1].push_back(tmp);
			edge tmp2 = {a1,a3};
			e[a2].push_back(tmp2);
		}
	}
	return 0;
}