トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 014

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 014 - D

この問題、いろいろなハマりポイントがあり一筋縄ではいかないので記録しておく

    • 解答には ダブリング を使います(解説によると)
      • それと、木構造に関する慣れや知識の蓄積が必要に思われる。

たぶん、セグメント木とオイラーツアーを使うほうが簡単そうではある。

  ダブリングでの解答

満点回答の概要

  • 「最小共通祖先」という言葉はただの概念なので、それをうまいこと取得するためのアルゴリズムではないです

「最小共通祖先」を高速に求めるための方法

  • やること
    • ダブリング を使用して木の親要素の情報を集めたテーブルを作る
    • 木の深さを使用する
      • どうやって?→解答者のソースをみると、テーブル構築時に深さも図っているみたい

親要素を取得するテーブル構築のコード

lines = <<'EOS'
5
1 2
1 3
1 4
4 5
3
2 3
2 5
2 4
EOS

#lines = $stdin.read
array = lines.split("\n")

N = array[0].to_i
LOGN = Math.log2(N).floor
Q = array[N].to_i

next_hash = {}
array[1..N-1].each do |s|
  k,v = s.split(" ").map(&:to_i)
  k,v = k-1,v-1
  if next_hash[k].nil?
    next_hash[k] = v
  else
    next_hash[k] = -1
  end
  if next_hash[v].nil?
    next_hash[v] = k
  else
    next_hash[v] = -1
  end
end

next_obj = Array.new(LOGN+1).map{Array.new(N, 0)}

for i in 0...N
  next_obj[0][i] = next_hash[i]
end

for k in 0...LOGN
  for i in i...N
    if next_obj[k][i] == -1
      next_obj[k+1][i] = -1
    else
      next_obj[k+1][i] = next_obj[k][next_obj[k][i]]
    end
  end
end

具体的な処理