TopCoder SRM 825 : Div1 Easy Div2 Medium OptimalMemoryGame

しょうもないミスで3完を逃した…。
https://community.topcoder.com/stat?c=problem_statement&pm=17426

問題

N種類のカード2枚ずつからなる、2N枚のカードを使った神経衰弱を考える。
一部のカードは所在が分かっており、その位置が与えられる。
最適にふるまうと、1回の手番で最大何組のカードを確定で得られるか。

解法

場所が確定していないカードの枚数で分岐する。

• 1枚だけわかっているカードと、場所が確定していないカードの枚数が等しい
  • 場所が確定していないカードを1枚めくれば、対になるカードの位置は確実にわかる。よって全カード取得できる。
• そうでない場合、場所が確定していないカードがちょうど2枚
  • その2枚は確実にペアになるので、こちらも同じく全カード取得できる。
• それ以外の場合
  • 場所が確定していないカードをめくると、対になるカードの位置を特定できない場合がある。よって、このケースは2枚とも位置がわかっているものしか確実に取得することはできない。

class OptimalMemoryGame {
	public:
	int findPairs(string known) {
		int N=known.size()/2;
		int C[26]={};
		FORR(c,known) if(c!='-') C[c-'A']++;
		int D[3]={};
		int i;
		FOR(i,26) {
			if(C[i]==1) D[1]++;
			if(C[i]==2) D[2]++;
		}
		D[0]=N-D[1]-D[2];
		int ret=D[2];
		if(D[0]==0) {
			ret+=D[1];
		}
		else if(D[1]==0&&D[0]==1) {
			ret++;
		}
		return ret;
		
	}
}

まとめ

本番中なんとかコーナーケースを見落とせず済んでよかった。