CodeIQ に出した「共通の祖先は誰だろう」の解題解説

CodeIQ に出した「共通の祖先は誰だろう」の解題解説

「共通の祖先は誰だろう」( https://codeiq.jp/q/2825 )という問題を CodeIQ に出していたが、先日締め切られた。

100名を超える方の挑戦をいただいた。ありがとうございます。

で。

まずは問題。

問題

問題は

図のような家系図があります。
紙面の都合で 29 までしか書いていませんが、正の整数が全て含まれています。
上が祖先で下が子孫です。
上から順、左から順に 1, 2, ... と番号が振られています。
偶数には子が2人、奇数には子が3人います。
で。
複数の数を与えます。共通の祖先の番号のうち、最大のものを出力してください。

• 入力の値は、10億を超えることはありません。
• 入力の数は、10個を超えることはありません。
• 「祖先」には自分自身を含みません。[A]と[Aの親]の共通の祖先は[Aの親の親]ということになります。
• 「共通の祖先」に該当する数がない場合には「-」を出力して下さい。

というような内容だった。

解題解説

作問の意図としては、ツリーを扱う問題を作ろいうという辺り。
やや不規則なツリーを扱うという辺りが見どころかも。

ツリーをじっと見ると。あるいはもう少し大きな数まで作ってみるともっと明らかなんだけど、だいたい 2.5 で割ると親になる。偶数と奇数をセットにすると 親2人に対して子が5人なので、その比率になる。

たとえば、 27。27÷2.5=10.8。実際の親は 11。だいたい合っている。
あとは端数を微調整すると親を求めることができるようになる。
親が計算できれば、そのまた親、そのまた親 と辿っていける。

自分自身は「祖先」に含まないとか、「1」には祖先がいないとか、その辺りが要注意。

実装例

ruby による実装例は以下の通り：

def parent(x)
  return nil if x==1
  x/5*2 + ( x%5<2 ? 0 : 1 )
end

def parents(x)
  pas=[]
  loop do
    pa = parent(pas.last || x)
    return pas unless pa
    pas.push pa
  end
end

def solve(src)
  ( src.split(",").map{ |x|
    parents(x.to_i)
  }.inject(&:&).max || "-" ).to_s
end

puts solve(gets.strip)

ツリーの構造は parent メソッドにに入っている。parents メソッドで祖先をたどり、solve で共通部分の最大値を求めている。
簡単でしょ？

他の方の実装

• angel as ㌵㌤の猫 様 : http://twitter.com/angel_p_57/status/766686074571587584
• haruya 様 :
  • https://twitter.com/haruya1212/status/766681329853353984
  • https://twitter.com/haruya1212/status/766933280469897216
• ininsanus 様 : http://yuppe19.bitbucket.org/common_anc.html
• みけCAT 様 : https://gist.github.com/mikecat/910e21243ccb0ea21dc40f4bbaa646f0

他にもありましたら twitter のメンションなどで教えていただけると助かります。