hama_DU@TopCoderへの道

SRM 306 LightSwitches

Java, div1q2 |

http://www.topcoder.com/stat?c=problem_statement&pm=6407

ある複数個のスイッチの組み合わせで再現できるスイッチを取り除いて、

答えは 2^(最後に残ったスイッチの数) ということはすぐ分かる。

問題はその余分なスイッチをどうやって見つけるか。

各スイッチはベクトルとみなすことができて、その各要素は各バルブにつながっているかどうか。（つながっている＝１　つながっていない＝０）

すると、余分なスイッチとは他のスイッチ（ベクトル）に対して一次従属であるということ。

余分なスイッチを全て取り除いた残りのスイッチ（ベクトル）は線形独立なので、

各スイッチに対応するベクトルを縦に並べた行列をAとおくと、この問題はAのランクを求めることに帰着できる。

参考：

http://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E3%81%AE%E6%B6%88%E5%8E%BB%E6%B3%95

public class LightSwitches {
	public long countPossibleConfigurations(String[] switches) {
		int sn = switches.length;
		int bn = switches[0].length();
		int[][] conf = new int[sn][bn];
		for (int i = 0 ; i < sn ; i++) {
			for (int j = 0 ; j < bn ; j++) {
				if (switches[i].charAt(j) == 'Y') {
					conf[i][j] = 1;
				} else {
					conf[i][j] = 0;
				}
			}
		}

		int cnt = 0;
		for (int i = 0 ; i < bn ; i++) {
			int chosen = -1;
			for (int x = cnt ; x < sn ; x++) {
				if (conf[x][i] == 1) {
					chosen = x;
					break;
				}
			}
			if (chosen == -1) continue;

			for (int m = 0 ; m < bn ; m++) {
				int tmp = conf[chosen][m];
				conf[chosen][m] = conf[cnt][m];
				conf[cnt][m] = tmp;
			}

			for (int n = cnt + 1 ; n < sn ; n++) {
				if (conf[n][i] == 1) {
					for (int m = 0 ; m < bn ; m++) {
						if (conf[n][m] == 1 ^ conf[cnt][m] == 1) {
							conf[n][m] = 1;
						} else {
							conf[n][m] = 0;
						}
					}
				}
			}
			cnt++;
		}
		return 1L << cnt;
	}
}