kmjp's blog

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

Codeforces #169 Div2. A. Lunch Rush、B. Little Girl and Game

TCO R2Aが延期になっていたのでCFR169でも。
この回は不参加なので練習のみ。
http://codeforces.com/contest/276/problem/A
http://codeforces.com/contest/276/problem/B

A. Lunch Rush

N個のレストランについて、満足度F[i]と食事時間T[i]が与えられる。
ここで、昼休み時間がKあるとき、K>=T[i]ならそのレストランの満足度はF[i]、K<T[i]ならF[i]-(T[i]-K)となる。
最大の満足度を得られるレストランの満足度を答える。

これは題意通りシミュレートするだけ。

int N,K;

void solve() {
	int f,r,i,j,k,l, x,y,ma;
	
	N=GETi();
	K=GETi();
	ma=-1<<30;
	FOR(i,N) {
		x=GETi();
		y=GETi();
		if(y<=K) ma=max(ma,x);
		else ma=max(ma, x-(y-K));
	}
	_P("%d\n",ma);
	
	return;
}

B. Little Girl and Game

ある文字列が与えられ、それに対して2人でゲームを行う。
各人は自分の順番において、文字列を並べ替えて回文を作れれば勝ち。
そうでない場合、文字列の任意の1文字を削除して順番を終える。
上記条件で、両者が最適な動きをしたときの勝者を求める。

回文を作れるのは、奇数回登場する文字が0または1の時。
よって奇数回登場する文字が2以上の偶数のとき、先手の動作により奇数回登場する文字を1個にしてしまうので後手が勝ち。
0または奇数個の時は先手の勝ち。

int N;
char S[1003];
int num[27];

void solve() {
	int f,r,i,j,k,l,x,y;
	
	GETs(S);
	N=strlen(S);
	ZERO(num);
	FOR(i,N) num[S[i]-'a']++;
	j=0;
	FOR(i,26) j+=num[i]%2;
	
	if(j==0 || j%2) _P("First\n");
	else _P("Second\n");
	
	return;
}
||

*まとめ