buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

yukicoder No.629 グラフの中に眠る門松列

writer/tester contest : yukicoder

2018/02/24 表現を修正

writerしました

問題

本記事の目的

表記について

  • deg(v) は，頂点vの次数を表す．

基本

  • グラフ内に長さ2のパスはいくつ存在するか？
    • 頂点 v を中心とする長さ2のパスを数え上げれば良い．
    • 時間計算量は O(|E|) ． ( 頂点次数の数え上げに O(deg(v)) 掛かると考えた場合．通常は O(1) なので O(|V|)で済む． )
  • 余談： N頂点から成るクリークなグラフ(完全グラフ)に含まれる，長さ2のパスの個数は N*(N-1)*(N-2)/2 個

応用

  • グラフ内に🎍パスはいくつ存在するか？

    • 頂点 v を中心とする長さ2の🎍パスを数え上げれば良い．
    • 隣接頂点に書かれている数字を洗い出して ( 時間計算量O(deg(v)) )，えいっ( 時間計算量O(deg(v)) )とやれば，時間計算量 O(|E|) で全て求まりそう．

  • えいっとやる方法を考えるため，補題を考える．

えいっ

自然数 a_0 と N 要素から成る自然数のmultiset a_1 , ..., a_N が与えれる． 
a_1 , ... , a_N から2つ選び，a_0 を中心とした🎍列を作りたい．
何通り作ることが出来るか？ただし，左右反転した列は同一の列とみなす．

  • a_0が中央であることが分かっているので，a_0の左右には a_0 より小さい数が2つ，または a_0 より大きな数が2つ必ず来る必要がある．

    • 中央が小さい門松列，中央が大きい門松列と別に数え上げることが出来る．

  • a_0の左右に a_0 より小さい数が2つ来るケースを考えてみる．

    • a_0 より小さい数 を抽出した multiset b_1 , ..., b_M ⊆{a_1...a_N} を用意する．
    • 全てのペアの個数は， M*(M-1)/2 ．
    • 🎍列でないパターンは，ペアの両端が同じ数の場合．このペアの個数を引いていく．
    • 辞書や配列で管理して，同じ数字が何個現れるか求めて，そのペアの個数を求める．

  • a_0 より大きい数も同様．

  • 以上で時間計算量O(N)でこの補題の答えが求まった．

  • 本題に戻る．
  • 別の問題に含まれる変数に，『中心の頂点vに書かれた数字をa_0，頂点vに隣接する頂点に書かれた数字をa_1, ... 』と割り当てて解くと，頂点 v を中心とする長さ2の🎍パスの個数が求まる．
  • 頂点vに隣接する頂点の個数はO(deg(v))
  • 全ての頂点に対してこの計算を行うので，元の問題の全体の時間計算量はO(|E|)

コード

def ascan; gets.split.map(&:to_i);end


N, M = ascan
A    = ascan

# 隣接リスト
adjacents = Array.new(N){[]}

M.times do
    u, v = ascan
    u -= 1; v -= 1
    adjacents[u] << v
    adjacents[v] << u
end


ans = 0

# 頂点vを中心とする長さ2のパスについて調べたい
0.upto(N-1) do |v|
    
    # 頂点 v に書かれた数字
    a = A[v]
    
    # aより小さな数字が書かれた頂点 {key:数字, value:個数}
    small = Hash.new(0)
    # aより大きな数字が書かれた頂点
    large = Hash.new(0)
    
    adjacents[v].each do |u|
        small[A[u]] += 1 if A[u] < a
        large[A[u]] += 1 if A[u] > a
    end
    
    # aが最大となる🎍パスの数え上げ
    unless small.empty?
        cnt = small.values.reduce(:+)
        ans += cnt*(cnt-1)/2
        small.each do |key, val|
            ans -= val*(val-1)/2
        end
    end
    
    # aが最小となる🎍パスの数え上げ
    unless large.empty?
        cnt = large.values.reduce(:+)
        ans += cnt*(cnt-1)/2
        large.each do |key, val|
            ans -= val*(val-1)/2
        end
    end
    
end

# 個数
# p ans

puts ans > 0 ? :YES: :NO

感想

この解法でも☆2.5くらいですね…