Codeforces #233 Div1. A. Cards

この回はもともと不参加だったうえ、Unratedだったみたいね。
http://codeforces.com/contest/398/problem/A

問題

数AとBが与えられるので、oがA個、xがB個からなる文字列を作りたい。
この時、各連続するoがp個あると+p^2点、連続するxがq個あると-q^2点として文字列の得点が計算できる。

A,Bに対し最大の得点を与える文字列を答えよ。

解法

A問題とはいえ自力で解答出来ず、Editorialを見てしまった。

連続する文字数に対し2乗で得点が計算される。
よって、oはできるだけ長く連続させ、xは連続させないようにしたい。

oをN個、xを(N+1)個の塊にすることを考える。
oは(N-1)個の塊は1文字で、残り1つに(A-(N-1))を全部連続させる。
xは(N+1)個の塊に均等にわかれるようにすればよい。
後はNを総当たりするだけ。

void solve() {
	int f,i,j,k,l,x,y;
	ll A,B;
	cin>>A>>B;
	
	if(A==0 || B<=1) {
		cout<< A*A-B*B <<endl;
		cout<< string(A,'o') << string(B,'x') <<endl;
		return ;
	}
	
	int ls=-1;
	ll mac=-1LL<<40;
	for(i=1;i<=A && (i+1)<=B;i++) {
		ll cc=(i-1)+(A-(i-1))*(A-(i-1));
		ll bm=B%(i+1);
		cc-=bm*(1+B/(i+1))*(1+B/(i+1))+(i+1-bm)*(B/(i+1))*(B/(i+1));
		if(cc>mac) ls=i,mac=cc;
	}
	
	cout << mac << endl;
	ll bm=B%(ls+1);
	FOR(j,B/(ls+1)+(bm>0)) _P("x");
	for(i=1;i<=ls;i++) {
		if(i==1) {FOR(j,A-(ls-1)) _P("o");}
		else _P("o");
		FOR(j,B/(ls+1)+(bm>i)) _P("x");
	}
	_P("\n");
}

まとめ

結構本番も落とした人がいたようで、Aの割に難しかったようだ。