PCK 2011 本選 - ダジャレ

問題 : ダジャレ

※Active Learning Studio にあがっているテストケースはvalid なものになっていました(確認済).

解法 :

まず, (x, y, z) を(正直な審査員の評価, へそまがりな審査員の評価, 笑いの敷居の低い審査員の評価とする).

ここで, (f, f, b) という評価があれば正直な審査員がかならず不正をしていることが分かる. ((*, *, b) という評価であれば必ずつまらないダジャレで, (f, b, b) という評価はありえない(不正をしている人が2 人いることになってしまうから.)

そうでなければ, 1 つ1 つのダジャレを不正が行われたと仮定して検証していく.
あるダジャレで不正が行われたとしてvalid な結果になり, 他のものは正当に評価されているとしてもvalid であれば不正回数に加算する.
そうでなければ何かがおかしいので加算しない.

計算量は$O(n^2)$ となる.

#include <cstdio>

using namespace std;

int main()
{
	int n;
	char honest[128], lier[128], low[128];
	
	while (scanf("%d", &n) && n){
		for (int i = 0; i < n; i++){
			scanf(" %c", &honest[i]);
		}
		
		for (int i = 0; i < n; i++){
			scanf(" %c", &lier[i]);
		}
		
		for (int i = 0; i < n; i++){
			scanf(" %c", &low[i]);
		}
		
		int hC = 0, lC = 0, loC = 0;
		for (int i = 0; i < n; i++){
			if (low[i] == 'b' && honest[i] == 'f') hC += 10000;
		}
		
		for (int i = 0; i < n; i++){
			int dxh = 0, dxl = 0, dxlo = 0;
			int mul = 1;
			for (int j = 0; j < n; j++){
				if (i == j){
					if (honest[i] == 'f'){
						if (low[i] != 'b' || lier[i] != 'b') dxh++;
					}
					if (lier[i] == 'f'){
						if (low[i] == 'f') dxl++; 
					}
					if (low[i] == 'f'){
						if (honest[i] == 'b' && lier[i] == 'f') dxlo++;
					}
				}
				else {
					if (low[j] == 'f') continue;
					if (honest[j] == 'b' && lier[j] == 'f') continue;
					mul = 0; 
				}
			}
			hC += dxh * mul; lC += dxl * mul; loC += dxlo * mul;
		}
		if (hC >= lC && hC >= loC) printf("1\n");
		else if (lC >= hC && lC >= loC) printf("2\n");
		else printf("3\n");
	}
	return (0);
}