CTPCに参加しました。

http://koj.cms.am/contest/
突然暇になったので出てました。
競技プログラミング初心者にしては頑張ったとか勝手に思ってます。

A - Average
puts()なんて関数ないよとか言われてコンパイルエラーしたり
sort範囲を間違えてWA食らったりで無駄に時間がかかってもうやめようかと思った。

int main(){
	int p[4];
	cin>>p[0]>>p[1]>>p[2]>>p[3];
	sort(p,p+4);
	puts((p[0]+p[1]+p[2]+p[3]+p[3])/5>=60?"Yes":"No");
	return 0;
}

B - Macaron
ひどいコード。

int w,h;
int m[100][100] = {};

void cnv(int x,int y){
	if(x>=0&&x<w&&y>=0&&y<h)
		m[x][y] = 1 - m[x][y];
}

int main(){
	int k,x,y,l,s;
	cin>>w>>h>>k;
	rep(q,k){
		cin>>x>>y>>l;
		x-=l;
		y-=l;
		s=l*2;
		while(x>=0||y>=0||x+s<w||y+s<h){
			for(int i=1;i<s;i++){
				cnv(x+i,y);
				cnv(x+i,y+s);
				cnv(x,y+i);
				cnv(x+s,y+i);
			}
			cnv(x,y);
			cnv(x+s,y);
			cnv(x,y+s);
			cnv(x+s,y+s);
			
			x -= l+1;
			y -= l+1;
			s += 2*(l+1);
		}
	}
	
	rep(y,h){
		rep(x,w) printf("%c",m[x][y]?'#':'.');
		puts("");
	}
	
	return 0;
}

C - Communication Tool
NAを出力する条件を間違えたりしてた。

int main(){
	int n,t=0,r=0;
	string str;
	cin>>n;
	getline(cin,str);
	rep(i,n){
		getline(cin,str);
		if(str.length()<=140&&str.length()>=1){
			t++;
			if(str[0] == '@')
				r++;
		}
	}
	if(t==0)puts("Tweet:NA Reply:NA");
	else cout<<"Tweet:"<<100*(t-r)/t<<" Reply:"<<100*r/t<<endl;
	return 0;
}

D - Knapsack Problem
入れ替えが発生するアイテムを後ろの方に集めれば何かできそうだったけど
そもそもナップサック問題解けないので無理。

E - Airport
「どの相異なる空港A , B の間にも, A よりB への, 或いは, B からA への直行便のどちらか一方を必ず開設する.」のチェックをしてなくてWA連発した。
色々無駄なことしてそう。

map<string,int> in;
int f[20][20] = {};

int main(){
	int n,m;
	string s,s2;
	cin>>n;
	rep(i,n){
		cin>>s;
		in[s] = i;
	}
	cin>>m;
	rep(i,m){
		cin>>s>>s2;
		f[in[s]][in[s2]]=1;
	}
	rep(i,n)
		rep(j,n)
			if(i!=j&&f[i][j]+f[j][i]!=1){puts("No");return 0;}
	
	int sum=0;
	rep(i,n){
		int go[20] = {};
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			int p = q.front();q.pop();
			rep(j,n){
				if(f[p][j] && !go[j]){
					q.push(j);
					go[j]=1;
				}
			}
		}
		rep(j,n){
			if(i==j)continue;
			sum+=go[j];
		}
	}
	puts(n*(n-1)==sum?"Yes":"No");
	
	return 0;
}

F - Night Museum
無理。

G - Lucky Number
ビットシフトとかよく分かってないまま書いてる。

int main(){
	long long n,se=1,sum=0;
	cin>>n;
	while(1){
		if(n%2)sum=(se+sum)%1000000;
		se=(se*7)%1000000;
		if(n==1)break;
		n>>=1;
	}
	cout<<sum%1000000<<endl;
	
	return 0;
}

H - Magical Jump
移動回数を記録しつつDP。DPの意味を知らないけどきっとこんなのでいいはず。

int w,h;
int m[30][30] = {};
int dp[30][30] = {};
int cnt[30][30] = {};

void set(int x,int y,int n){
	if(x>=0&&x<w&&y>=0&&y<h&&m[x][y]<n) m[x][y] = n;
}

int main(){
	int n,x,y;
	cin>>w>>h>>n;
	w++;h++;
	rep(i,n){
		cin>>x>>y;
		set(x-1,y-1,1);
		set(x-1,y,1);
		set(x-1,y+1,1);
		set(x,y-1,1);
		set(x,y,2);
		set(x,y+1,1);
		set(x+1,y-1,1);
		set(x+1,y,1);
		set(x+1,y+1,1);
		cnt[x][y] = INTMAX;
	}
	dp[0][0]=1;
	cnt[0][0]=1;
	rep(x,w)rep(y,h){
		if(x+y==0||m[x][y] == 2)continue;
		int c=0;
		if(x!=0){
			if(y!=0){
				if(m[x-1][y-1]==0){
					c = min(cnt[x-1][y-1],min(cnt[x-1][y],cnt[x][y-1]));
					if(cnt[x-1][y] == c) dp[x][y] += dp[x-1][y];
					if(cnt[x-1][y-1] == c) dp[x][y] += dp[x-1][y-1];
					if(cnt[x][y-1] == c) dp[x][y] += dp[x][y-1];
				}else{
					c = min(cnt[x-1][y],cnt[x][y-1]);
					if(cnt[x-1][y] == c) dp[x][y] += dp[x-1][y];
					if(cnt[x][y-1] == c) dp[x][y] += dp[x][y-1];
				}
			}else{
				c = cnt[x-1][y];
				dp[x][y] = dp[x-1][y];
			}
		}else{
			c = cnt[x][y-1];
			dp[x][y] = dp[x][y-1];
		}
		cnt[x][y] = c+1;
	}
	cout<<dp[w-1][h-1]%1000000<<endl;
	
	return 0;
}

I - Card Game
読んでない。

J - Favorite Number
できそうになかった。

K - Prime Factorial
エラトステネスの篩の実装をミスってTLEした。あほらしい。