ABC256 Eの解法メモ【Ruby】

入水目指して過去挑戦して解けてないAtCoder Problems上でDifficultyが水色の問題を解いていく。

ABC256 E: Takahashi's Anguish概要

$N$人の人を1列に並べたとき、並んでいる人の嫌いな人がその人よりも前に並んでいると不満度が増える。
好きな順に並べられるときの不満度の最小値を求める問題。

解法イメージ

$N$頂点$N$辺の有向辺グラフとしてみると、いくつかのループとループの頂点へ向かう枝からなるグラフになる。
この時、連続ではないグラフの頂点同士はどの順で並んでいても不満度は増えないので、以降は連結なグラフについて考える。

ループへと向かう枝についてはその枝の端から順に並べば嫌いな人よりも前に並ぶので不満度は増えない。異なる枝同士は嫌い合っていないのでどの順で並べても良い。
ループの中においては辺の向きに沿って並べれば不満度は増えないが、ループをどこかの辺で切る必要が出る。この切られた辺の不満度が各ループで発生する。

よって、それぞれのループに対してループを作っている辺の内、不満度が一番小さいものの合計を求めてあげれば答えとなる。

実装例

n = gets.to_i
xarr = [0] + gets.split.map(&:to_i)
carr = [0] + gets.split.map(&:to_i)

c = 0
h = {}
max = carr.max
(1..n).each do |i|
  next if h[i]

  flag = false
  arr = [i]
  hash = {i=>0}
  while hash[xarr[i]].nil?
    if h[xarr[i]]
      flag = true
      break
    end
    i = xarr[i]
    hash[i] = arr.length
    arr << i
  end
  arr.each{|j| h[j] = true }
  next if flag
  
  min = max
  arr[hash[xarr[i]]..].each do |j|
    min = [min, carr[j]].min
  end
  c += min
end

puts c