Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-04-22TCO2012 Round2A

TCO2012 Round2A 300 SwitchesAndLamps

| 17:48 | TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) のブックマークコメント

コーディングフェーズ

以下の2つの問題に分けて考えればいい

  1. 与えられた情報から、スイッチとランプをこれ以上分割できないグループに分割する
  2. 各グループを更にスイッチ・ランプ1個ずつのグループまで分割するための最小テスト数を求める

時間をかけた挙句、1,2ともに間違った解答を出してしまいチャレンジされる


後で

1のほうは、実は縦に見て全く同じ結果のものを集めればいいだけだったりする

つまり、1回目のテストがY、2回目がN、3回目がYのスイッチがあったとすると、それと同じグループに入れるスイッチは、やはり1回目のテストがY、2回目がN、3回目がYのスイッチである。

同様に、ランプの全く同じパターンのものを集める。

1つのグループ内で、スイッチとランプの数が違っていたら-1。


2のほうは、とりあえず全てのグループに対し、並列で試験ができるので、一番スイッチ数の多いグループだけを考えればいい。

並列で試験できることを考えると、試験数を最小にするには、グループをYとNで2分割することである

分かれた2つのグループに対し同時に試験ができるから、さらに大きい方を2分割して・・・と続けていくと、いつかスイッチ数が1になる

これにかかる回数を出せばOK


ソースコード

試験結果の比較はstringでやればいいのだが、何かあまり整理しきれてないときに書いたコード

任意のスイッチorランプのペアに対して、1つでも結果が異なる試験があれば別グループという判定をしている

class SwitchesAndLamps {
public:
	int calc(ll cnt) {
		int res=0;
		while(cnt>1) {
			cnt=(cnt+1)/2;
			res++;
		}
		return res;
	}

	int theMin(vector <string> sw, vector <string> lmp) {
		int res;
		int esz=sw.size(), n=sw[0].size();

		int conn[102][102];
		for(int i=0; i<n*2; i++) for(int j=0; j<n*2; j++) conn[i][j]=1;
		for(int i=0; i<esz; i++) {
			for(int j=0; j<n; j++) {
				for(int k=j+1; k<n; k++) {
					if(sw[i][j]!=sw[i][k]) conn[j][k]=conn[k][j]=0;
					if(lmp[i][j]!=lmp[i][k]) conn[n+j][n+k]=conn[n+k][n+j]=0;
				}
				for(int k=0; k<n; k++) {
					if(sw[i][j]!=lmp[i][k]) conn[j][n+k]=conn[n+k][j]=0;
				}
			}
		}

		res=0;
		vector <int> used(n*2);
		for(int i=0; i<n; i++) {
			if(used[i]) continue;
			used[i]=1;
			int swcnt=1, lmpcnt=0;
			for(int j=i+1; j<2*n; j++) {
				if(!conn[i][j]) continue;
				assert(!used[j]);
				used[j]=1;
				if(j<n) swcnt++;
				else lmpcnt++;
			}
			if(swcnt!=lmpcnt) return -1;
			res=max(res, calc(swcnt));
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120422