kmjp's blog

競技プログラミング参加記です

2012 WUPC2 : A - 団子とうさぎ、B - 雨上がり

第2回早稲田大学プログラミングコンテストにオンライン参加してました。
Eが部分点、Hが未着手だったけどそれ以外は順調に解けた。
順位は格別良かったわけではないけど、問GとHは以前なら解けなかった問題なので最近の練習の成果が出て良い感じ。

本当はEを解ききってHの部分点位まで行きたかったのだが…。
Eのバグが取りきれなくて残念。

では1問ずつ見ていきます。まずはAとB。
http://wupc2nd.contest.atcoder.jp/tasks/wupc_01
http://wupc2nd.contest.atcoder.jp/tasks/wupc_02

A - 団子とうさぎ

問題の指示通り足して剰余を取るだけ。
Nが小さいので、( (N*(N+1)*(2*N+1) )/6)%Mでまとめて計算しても良かったかもね。

int N,M;
void solve() {
	int i,t=0;
	
	N=GETi();
	M=GETi();
	
	FOR(i,N) t+=(i+1)*(i+1);
	
	_P("%d\n",t%M);
}

B - 雨上がり

1~3マスずつ歩けるプレイヤーが、できるだけ少ない数の水たまりを踏んで道を歩く。
一見、よくありがちなフィボナッチとかDPを想像するけど、実際は簡単。
3マス以上連続した水たまりは飛び越せないので、3マスあたり1回水たまりを踏むだけ。

void solve() {
	int f,r,i,j,k,l;
	int m=0,nm=0,n;
	
	N=GETi();
	GETs(str);
	j=n=0;
	FOR(i,N) {
		if(str[i]=='X') j++;
		if(str[i]=='.' && j>0) {
			n+=j/3;
			j=0;
		}
	}
	_P("%d\n",n);
	return;
}

まとめ

@AtCoderの予告通り、出だしは優しめ。
後の問題を見ても、若干難易度は低めなコンテストだね。
自分には後半の難易度がちょうどよかった。