CodeIQ「中学入試から：図形と場合の数」解答コード

cn_zukeitobaainokazu.cpp

#include <cstdio>
#include <vector>
#include <string>
#include <set>

struct triangle_t {
	int length[3];
	triangle_t() {}
	triangle_t(int a, int b, int c) {
		int candidates[3][3] = {{a, b, c}, {b, c, a}, {c, a, b}};
		int min_index = 0;
		// 辞書順最小の並べ方を求める
		for (int i = 1; i < 3; i++) {
			bool is_smaller = false;
			for (int j = 0; j < 3; j++) {
				if (candidates[i][j] < candidates[min_index][j]) {
					is_smaller = true;
					break;
				} else if (candidates[i][j] > candidates[min_index][j]) {
					break;
				}
			}
			if (is_smaller) min_index = i;
		}
		for (int i = 0; i < 3; i++) length[i] = candidates[min_index][i];
	}

	bool operator<(const triangle_t& tr) const {
		for (int i = 0; i < 3; i++) {
			if (length[i] < tr.length[i]) return true;
			if (length[i] > tr.length[i]) return false;
		}
		return false;
	}
};

std::vector<int> parse_i(const char *str) {
	std::vector<int> ret;
	while (*str != '\0') {
		ret.push_back(*str - 'A');
		if (*(str + 1) != ',') break;
		str += 2;
	}
	return ret;
}

int solve(int choten_num, const std::vector<int>& choten_list) {
	std::vector<int> ruisekiwa(choten_list.size() * 2);
	std::set<triangle_t> triangles;
	// 円2周分のデータを作成
	for (size_t i = 0; i < choten_list.size(); i++) {
		ruisekiwa[i] = choten_list[i];
		ruisekiwa[i + choten_list.size()] = choten_list[i] + choten_num;
	}
	// 全探索
	for (size_t i = 0; i < choten_list.size(); i++) {
		for (size_t j = i + 1; j < choten_list.size(); j++) {
			for (size_t k = j + 1; k < i + choten_list.size(); k++) {
				triangles.insert(triangle_t(
					ruisekiwa[j] - ruisekiwa[i],
					ruisekiwa[k] - ruisekiwa[j],
					ruisekiwa[i + choten_list.size()] - ruisekiwa[k]
				));
			}
		}
	}
	return (int) triangles.size();
}

int main(void) {
	std::vector<std::string> wrong_id_list;
	char id[1024];
	int a;
	char i[1024];
	int answer;
	while (scanf("%s%d%s%d", id, &a, i, &answer) == 4) {
		int got_answer;
		std::vector<int> i_vec = parse_i(i);
		got_answer = solve(a, i_vec);
		if (answer != got_answer) {
			printf("%s : expected %d, got %d\n", id, answer, got_answer);
			wrong_id_list.push_back(id);
		}
	}
	printf("\n%u answer(s) found.\n", (unsigned int) wrong_id_list.size());
	if (wrong_id_list.size() > 0) {
		printf("answer(s) = %s", wrong_id_list[0].c_str());
		for (std::vector<std::string>::iterator it = wrong_id_list.begin() + 1;
		it != wrong_id_list.end(); it++) {
			printf(",%s", it->c_str());
		}
		putchar('\n');
	}
}