オフラインリアルタイムどう書くE11参加しました

yhpg

はじめに

2017/2/4開催の「オフラインリアルタイムどう書くE11」に参加しましたので、そのレポートです。

どんな感じ?

前回は所用でオンライン参加だったため、実に久しぶりでした。

今回は鍋谷さん出題の回でした。いかにも木構造な問題ですが、値の重複が有り得るというところが悩みのたねでした。…Rubyでまともに木構造扱ったことなかったですし。

会場では様々なアプローチで木構造を攻略してました。正答率は高めというところでしょうか。 私はケアレスミスでバグが抜けず、ちょっと時間超過で解いた、という感じでした。

問題

問題はツリーの中の距離でした。概要は次の通りです。

  • 自然数で構成された、ルートの数値が与えられた木構造を考える
  • 指定された異なる2数を持つノード ( 複数存在しうる ) の最短距離を求める
  • 各ノードには、そのノードの数値の全ての約数 ( ただし 1 とそれ自身を除く ) に、それぞれ 1 を加算した数値を持つ子ノードが作成されている。

詳細は上のリンクからご覧ください。なお、しっかりと事前に図解したケースの説明がありました。…図があることを気に留めない参加者が多かったせいですね。( 心に棚 )

解説

実装1

会場で実装したコードは次の通りです。

今回は関数を2つも余分に作ってしまいました。

指定された2ノードのうち、大きい方の数値をもつノード基準として考えるのですが、その上で

  • 下に、つまり直系の子ノードを幅優先探索して、小さい方の数値を持つノードの最短距離 ( 見つからなければ nil ) を探る lineal
  • 木を構成し、大きい方の数値を持つノードのポインタというか参照を一覧として返す maketree

という処理を担当します。

同じ数値を持つノードに関しては、そこから下に展開される部分木は、必ず同じものになります。なので、直系との距離は、1変数のlinealだけで求めることができます。

問題は傍系の場合です。どこかの親ノードを経由して距離を計測する必要があるため、探索で見つかったノードから親を順次辿っていき、それぞれで lineal を計算して親への距離と合算したものの中で最短を探す、ということになります。

なお、指定のノードより小さい数値が出てきたら、もうその下に目的のノードはないので ( 半順序関係が成立 )、どちらの関数でもそこで探索を打ち切るようにしています。

実装2

しかし、帰りの電車の中で、木構造を作らずに単純な再帰で処理する方法を思いつきました。まあ、記事にする前に、既にしえるさんが実装してたりするのですが、こちらでも解説を。

ソースコードは http://ideone.com/O3eWKM にありますが、そこからメインの処理を抜粋します。

def solve(input)
  root,*c=input.split(/\D/).map(&:to_i)
  (f=->n{
    m=[]
    m[(c.index(n)||2)+1]=-1
    (2..n/2).each{|e|
      next if n%e!=0
      t=f[e+1]
      3.times{|i| m[i]=t[i] if t[i]&&(!m[i]||m[i]>t[i]) }
    }
    m[1]+=1 if m[1]
    m[2]+=1 if m[2]
    m[0]=m[1]+m[2] if m[1]&&m[2]&&(!m[0]||m[0]>m[1]+m[2])
    m
  })[root][0]
end

実に14行で済みました。

どのような再帰になるかというと、次の通りです。

  • 3種類の値を組 ( というか Array ) にして返す。内訳は
    • 自分をルートとする部分木の中での、指定の2種類のノードの最短距離
    • 自分から指定のノードへの最短距離 ( 2種類 )
  • あるノードに対応する返り値の計算 ( 漸化式 ) は次の通り
    • 指定のノードへの最短距離は、直下の子ノードから返る最短距離の中の最小値+1。ただし、自ノードがその指定のノードに等しい場合は 0。
    • 2種類のノードの最短距離は、直下の子ノードから返る最短距離全てと、1つ上で計算した「指定のノードへの最短距離」( 2種 ) の和の中の最小値

まあ、ノードが見つからない時のため、nil の処理を考える必要がありますが、これを素直に再帰させれば済むわけです。約数+1 の列挙は手抜きして$O(n)$にしてますが、もともと問題の規模は大きくないので今回は十分です。

速度のことを考えるなら、もちろん更にメモ化再帰にするところです。

終わりに

なんというか、「関数を分割しない人」「変数名に滅多に意味を持たせない人」という風評が固まりつつある気がするのですが…。私だって、普段はちゃんと…。…。あ、そもそもプログラミングしてなかった。

まあこんな感じで、次も参加したいと思います。

なお、色々な方の実装例は、オフラインリアルタイムどう書くE11 の問題 - Qiitaに紹介されています。