風邪につきsemi-realtimeのonline参加ですが…
ネタバレを含むため続きを読む記法、あとかなり雑な解説です。
解答
解説
最近Neo4j触ってたせいか最初見た印象が「ノードの生成条件だけ作ってNeo4jに投げれば秒殺やろ＾〜〜〜〜〜」と思ったのですが、当然そういうのは想定されていないので普通に解くことにします。
- とりあえずある数字の約数の一覧を出す関数(
divisors)とある数字のノードの子ノードの数字の一覧を出す関数(child_values)を作る。 - このへんでRubyでツリー作るのつらそうと思って他の言語への浮気を考えて、でも結局間に合わなさそうなのでやめる。
- Nodeクラスを作る。val, children, parentの要素を持たせて、生成時にchildrenに値を代入するところまで。
- で再帰がうまくかけていなかったようで無限ループした。
- 現在の形に書き直す。
- ツリーの親を与えて、子から値nを持つノードの一覧を返すfind(n)を実装。
- その後、「一番上のノードから見てどの位置にあるか」を示すindexという値を導入
- give_children_indexを実装
- その後、indexを元に距離を計算する方法を考えて
- あとはテストケースを実行可能にした。
indexの仕組み
- 上から何段目にあるかが配列の長さ
- 配列のn番目の要素は、「同じ高さの中で左から何番目(0-start)にあるか」を示す
- 同じ高さでの並び方は「小さい順」になるようソートしているので、indexを使ってノードの位置は一意に表現できる
- そのうえで、2つのノードの距離は「2つのindexが一致するところまでの長さ」(
diffという関数名を使ってるが正直名前がよくない)＋「そこからの各配列の長さ」で計算できる(l.70)。
test関数内の解説
- まあ順当に値をパースして
- ツリーの親のノードの数字からツリーを作る
- 与えられた数字のノードの列を探す(l.65,66)
- そのうえで、2つのノードの列から組み合わせを生成し(
Array#product, l.68)、それぞれについて- indexを計算
- 距離を計算
- …で、その値の列から最小の値を取り出す。
感想
グラフ探索じゃなくてツリー探索で、しかも厳密には親を再帰的に参照して…みたいな探索をしなかったので、Rubyみたいにlinked-listを作りにくい言語でも普通にできたし、そこに早く気づくべきだった。
