結果

問題 No.382 シャイな人たち (2)
コンテスト
ユーザー TANIGUCHI Kousuke
提出日時 2016-12-05 01:24:13
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 2,083 bytes
コンパイル時間 47 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 174,592 KB
最終ジャッジ日時 2024-11-27 20:55:04
合計ジャッジ時間 193,240 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 1 TLE * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 


def make_n(s)
    s = (s * 12345) % 1000003
    s % 120 + 2
end

def make_p(s)
    s = (s * 12345) % 1000003
    (s * 12345) % 1000003
end


def make_graph(s)
    s = (s * 12345) % 1000003
    s = (s * 12345) % 1000003
    (1 .. V).each do |v|
        G[v] = []
    end
    (1 .. V).each do |from|
        ((from + 1) .. V).each do |to|
            s = (s * 12345) % 1000003
            if s < P
                G[from] << to
                G[to] << from
            end
        end
    end
end

s = gets.to_i

G = {} # Graph
U = {} # G[U]
CLIQUES = []
V = make_n(s)
P = make_p(s)
make_graph(s)

# puts V
# puts G.inject(0) {|s,(k,v)| s + v.size} / 2 

def init_induced_subgraph(v)
  if v < 0
    U[v] = []
    (1 .. V).each {|u| U[u] = []}
    (1 .. V).each do |u|
      U[v] << u
      U[u] << v
      G[u].each do |w|
        U[u] << w
      end
    end
  else
    U[v] = []
    G[v].each {|u| U[u] = [] }
    G[v].each do |u|
      if U[u]
        U[u] << v
        U[v] << u
      end
    end
  end
end

def complete_graph?
  v = U.size
  e = U.inject(0) {|s, (u, link)| s + link.size }
  v * (v - 1) == e

end

def complete_number(v)
  if v < 0
    return U.size - 1
  else
    return U.size
  end
end

def fusion_clique?(complete, a, b)
  U[a.last].include?(b.last)
end

def belongs_max_clique(v, c = U.size)
  return complete_number(v) if complete_graph?

  U[v].each do |u|
    CLIQUES << [v,u]
  end
  
  cqsize = (1 .. c).find do |k|
    fusioned = []
    dd = CLIQUES.group_by {|cq| cq[0,k].join(' ') }
    dd.each do |shared, cqn|
      complete = shared.split.map(&:to_i)
      cqn.combination(2) do |a,b|
        if fusion_clique?(complete, a, b)
          joined = (a + b).uniq.sort
          fusioned <<  joined
        end
      end
    end
    if fusioned.empty?
      true
    else
      CLIQUES.clear
      fusioned.each do |cq|
        CLIQUES << cq
      end
      false
    end
  end
  if v < 0
    cqsize
  else
    cqsize + 1
  end
end


init_induced_subgraph(-1)
puts belongs_max_clique(-1)
sample = CLIQUES.sample
sample.shift
puts sample.join(' ')
0