オフラインリアルタイムどう書くE11 writeup

風邪につきsemi-realtimeのonline参加ですが…

ネタバレを含むため続きを読む記法、あとかなり雑な解説です。

解答

gist.github.com

解説

最近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を作りにくい言語でも普通にできたし、そこに早く気づくべきだった。