Codeforces #164 Div2. A. Games, B. Buttons

#164はDiv2のみだったので非正規参加。時間中にはCまで解けた。
ではAから練習。
http://codeforces.com/contest/268/problem/A
http://codeforces.com/contest/268/problem/B

A. Games

３０個のチームがあって、ホームとアウェイ用のユニフォームの色が与えられる。
これらのチームが試合をする場合、片方がホーム用、もう片方がアウェイ用のユニフォームを着たとき、色が重複してしまう試合の組み合わせ数を答える問題。

これはチーム数も少ないので律儀に全通り試せばよい。
O(N^2)なので計算量も問題なし。

int N;
int C[101][2];

void solve() {
	int f,r,i,j,k,l;
	char str[100];
	int x,y;
	
	N=GETi();
	FOR(i,N) {
		C[i][0]=GETi();
		C[i][1]=GETi();
	}
	
	r=0;
	FOR(i,N) FOR(j,N) if(i!=j) {
		if(C[i][0]==C[j][1]) r++;
	}
	
	_P("%d\n",r);
	return;
}

B. Buttons

ボタン列があり、正しい順に押していく。
途中誤った順で押すと、今までのボタンが全部戻ってしまう。
全部を押し切るまでに押さないといけないボタンの数の最大値を求める。

i個目のボタンを押す場合を考える。(i-1)個目まではすでに押してあって、(N-i-1)個の中から正解をさがす。
よって、最悪N-i-2回間違えて、そのたびにすでに押した(i-1)個をまた押さないといけない。
最後に正解のボタンを押すとi個分押したことになる。
よって(N-i-2)*i+1が押すべき数。これを累積すればよい。

int N,T;

void solve() {
	int f,r,i,j,k,l;
	
	N=GETi();
	r=0;
	FOR(i,N) {
		r += (N-i-1)*(i+1);
		r++;
	}
	_P("%d\n",r);
	return;
}

まとめ

Bは単純だけどちょっと考えさせられる問題。
この位の難易度としては適度な頭の使い方でいいね。