CodeIQ「共通の祖先は誰だろう」解答コード

kyoutuunososennwadaredarou.c

#include <stdio.h>
#include <inttypes.h>

uint64_t get_parent(uint64_t n) {
	uint64_t min, max, prev_min;
	uint64_t block_index, in_block_index, threshold;
	if (n <= 1) return 0;
	/* 対象の数が含まれる段を探す */
	prev_min = min = max = 1;
	while (max < n) {
		uint64_t kisuu_num = (max + 1) / 2 - ((min - 1) + 1) / 2;
		uint64_t gusuu_num = max / 2 - (min - 1) / 2;
		uint64_t next_num = 3 * kisuu_num + 2 * gusuu_num;
		prev_min = min;
		min = max + 1;
		max = min + next_num - 1;
	}
	/* 親を求める */
	block_index = (n - min) / 5;
	in_block_index = (n - min) % 5;
	threshold = (prev_min % 2 == 0 ? 2 : 3);
	return prev_min + 2 * block_index + (in_block_index >= threshold ? 1 : 0);
}

int main(void) {
	int n = 0;
	uint64_t input[100];
	int log_count[100];
	uint64_t log[100][100];
	int i, j;
	while (scanf("%"SCNu64",", &input[n]) == 1) n++;
	/* それぞれの祖先を求める */
	for (i = 0; i < n; i++) {
		log[i][0] = get_parent(input[i]);
		log_count[i] = 1;
		while (log[i][log_count[i] - 1] != 0) {
			log[i][log_count[i]] = get_parent(log[i][log_count[i] - 1]);
			log_count[i]++;
		}
	}
	/* どこまで共通しているかを求める */
	for (i = 1; i <= log_count[0]; i++) {
		int ok = 1;
		for (j = 1; j < n; j++) {
			if (log_count[j] - i < 0 || log[j][log_count[j] - i] != log[0][log_count[0] - i]) {
				ok = 0;
				break;
			}
		}
		if (!ok) break;
	}
	if (log[0][log_count[0] - i + 1] == 0) {
		puts("-");
	} else {
		printf("%"PRIu64"\n", log[0][log_count[0] - i + 1]);
	}
	return 0;
}

meikai.md

名状しがたい解説のようなもの

• 前の段の奇数と偶数の数を元に、次の段に含まれる数の数を計算する
• 親を求めたい数がある段に来たら、次にその段の中での位置を計算する
• 上の段の一番左が偶数にしろ奇数にしろ5個ずつまとめて位置を計算するとよい
• 親を求めたい数がある5個のブロックの位置が求まったら、上の段の一番左の数によって変わる境界を用いて親を求める
• 祖先の一覧を求めたら、それらを最後から見てどこまで共通しているかを求める
• 一覧の最初にはもとの数があるので、見ない
• 0までしか共通していなかったら、番兵なので解なしとする