Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
CodeIQ「共通の祖先は誰だろう」解答コード
#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;
}

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

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