kmjp's blog

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

CODE FESTIVAL 2015 決勝 : A - コード川柳、B - ダイスゲーム、C - 寿司タワー

運よく優勝、だけど本戦参加の人交えると6位だし、1問は自分のブログのコピペなのでまだまだだね。
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_a
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_b
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_c

A - コード川柳

3つの文字列が与えられるので、5-7-5になっているか答えよ。
文字の長さをチェックするだけ。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	string A,B,C;
	cin>>A>>B>>C;
	if(A.size()!=5) return _P("invalid\n");
	if(B.size()!=7) return _P("invalid\n");
	if(C.size()!=5) return _P("invalid\n");
	_P("valid\n");
}

B - ダイスゲーム

N個の6面サイコロを振って和を取るとき、最も登場確率の高い和はいくつか。
同着の値が複数ある場合、最小値を答えよ。

1個の時は1、2個以上の時はfloor(3.5*N)を答えればよい。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	if(N==1) cout<<1<<endl;
	else cout<<N*7/2<<endl;
	
}

C - 寿司タワー

寿司N個分の具材、すなわちシャリと具N個ずつが積み重なったタワーがある。
手元にN個の寿司があるので、このタワーを形成したい。
寿司はそのままタワーに重ねても良いし、ひっくり返して重ねても良い。
またシャリと具を分割して、それぞれ別の位置に重ねても良い。
タワーを形成するのに必要な、分割する寿司の数の最小値を答えよ。

タワの下から2つずつ見ていって、2つが異なるなら(分割しない)寿司を乗せればよい。
そうでない場合、下の方の具材は分割したものか調達する。
既に分割した余りがあればそれを使えばいいし、なければ1個新規に分割しよう。

int L;
string S;

void solve() {
	int i,j,k,l,x,y; string s;
	
	cin>>L>>S;
	
	int n0=0,n1=0,r=0;
	FOR(i,2*L-1) {
		if(S[i]!=S[i+1]) {
			i++;
		}
		else {
			if(S[i]=='0') {
				if(n0) n0--;
				else r++,n1++;
			}
			else {
				if(n1) n1--;
				else r++,n0++;
			}
		}
	}
	cout<<r<<endl;
	
	
}

まとめ

Bは昨晩のyukicoderの影響で無駄にDPしに行ってタイムロスした。

広告を非表示にする