読者です 読者をやめる 読者になる 読者になる

JOI予選2011

JOI

切り捨てで 0点。 さすがに不参加でしょこれ。
一応コード晒します。


1番:やるだけ。

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int INF = 100000000;

int main(){
	int a, b, c, d, e, x, y;
	
	scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
	
	x = min(a,b);
	x = min(x,c);
	y = min(d,e);
	
	printf("%d\n",x+y-50);
	
	return 0;
}


2番:ソート力

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int INF = 100000000;

int main(){
	int i, n, a, b, c, d, ans[101], j, jx;
	P x[100];
	
	scanf("%d",&n);
	
	for(i = 0; i < n; i++){ x[i].fi = 0; x[i].se = i;}
	
	for(i = 0; i < n*(n-1)/2; i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		if(c < d){
			x[b-1].fi-=3;
		} else if(d < c){
			x[a-1].fi-=3;
		} else {
			x[a-1].fi--;
			x[b-1].fi--;
		}
	}
	
	sort(x,x+n);
	
	jx = INF;
	for(i = 0; i < n; i++){
		if(jx != x[i].fi){ j = i; jx = x[i].fi;}
		ans[x[i].se] = j+1;
	}
	
	for(i = 0; i < n; i++){
		printf("%d\n",ans[i]);
	}
	
	return 0;
}


3番:トッピングをカロリーでソートして貪欲に・・・

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int INF = 100000000;

int main(){
	int i, n, a, b, c, d[100], x, y, ma;
	
	scanf("%d%d%d%d",&n,&a,&b,&c);
	x = a; y = c; ma = y/x;
	
	for(i = 0; i < n; i++){
		scanf("%d",&d[i]);
	}
	sort(d,d+n);
	
	for(i = n-1; i >= 0; i--){
		x += b;
		y += d[i];
		ma = max(ma,y/x);
	}
	
	printf("%d\n",ma);
	
	return 0;
}


4番:2つ前までの状態を記録するDP

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int INF = 100000000, mod = 10000;

int s[101], dp[101][4][4];

int main(){
	int i, j, h, l, n, k, a, b;
	
	scanf("%d%d",&n,&k);
	
	for(i = 0; i < k; i++){
		scanf("%d%d",&a,&b);
		s[a] = b;
	}
	
	dp[0][0][0] = 1;
	
	for(i = 1; i <= n; i++){
		if(s[i]){
			for(j = 0; j <= 3; j++){
				for(h = 0; h <= 3; h++){
					dp[i][j][s[i]] += dp[i-1][h][j];
					dp[i][j][s[i]] %= mod;
				}
			}
			dp[i][s[i]][s[i]] -= dp[i-1][s[i]][s[i]];
			dp[i][s[i]][s[i]] %= mod;
		} else {
			for(l = 1; l <= 3; l++){
				for(j = 0; j <= 3; j++){
					for(h = 0; h <= 3; h++){
						dp[i][j][l] += dp[i-1][h][j];
						dp[i][j][l] %= mod;
					}
				}
				dp[i][l][l] += mod - dp[i-1][l][l];
				dp[i][l][l] %= mod;
			}
		}
	}
	
	a = 0;
	for(h = 0; h <= 3; h++){
		for(j = 0; j <= 3; j++){
			a += dp[n][h][j];
			a %= mod;
		}
	}
	
	printf("%d\n",a);
	
	return 0;
}


5番:BFS (DFSでもいけるらしい)
偶数段目と奇数段目で左右逆になってる感じのグラフ。
長方形上に並んでると考えれば良い。

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int INF = 100000000;
const int dx[2][6] = {{0,1,1,1,0,-1},{0,1,0,-1,-1,-1}};
const int dy[2][6] = {{-1,-1,0,1,1,0},{-1,0,1,1,0,-1}};

int m[105][105];
bool used[105][105];

int main(){
	int i, j, w, h, a, ans = 0;
	queue<P> q;
	P p;
	
	scanf("%d%d",&w,&h);
	
	for(j = 2; j < h+2; j++){
		for(i = 2; i < w+2; i++){
			scanf("%d",&a);
			if(a){
				m[i][j] = 2;
			} else {
				m[i][j] = 1;
			}
		}
	}
	
	for(i = 1; i < w+3; i++){
		m[i][1] = 1; q.push(P(i,1));
		m[i][h+2] = 1; q.push(P(i,h+2));
	}
	for(i = 2; i < h+2; i++){
		m[1][i] = 1; q.push(P(1,i));
		m[w+2][i] = 1; q.push(P(w+2,i));
	}
	
	while(!q.empty()){
		p = q.front(); q.pop();
		if(used[p.fi][p.se] || !m[p.fi][p.se]) continue;
		if(m[p.fi][p.se] == 2){ ans++; continue;}
		used[p.fi][p.se] = true;
		
		j = p.se&1;
		for(i = 0; i < 6; i++){
			q.push(P(p.fi+dx[j][i],p.se+dy[j][i]));
		}
	}
	
	printf("%d\n",ans);
	
	return 0;
}

1ヶ所、コピペの名残でwとhが逆になってて、縦長のマップでエンバグorz


6番:いろんな要素でDP
実装は重くない?
やり方がマズかったのかな?

There are too many bugs.


今年いっぱいはプロコンやって、年が明けたらHOJ禁して猛精進します。