結果

問題 No.382 シャイな人たち (2)
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2016-12-05 01:24:13
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 2,083 bytes
コンパイル時間 556 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 186,616 KB
最終ジャッジ日時 2024-05-05 20:06:00
合計ジャッジ時間 19,360 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_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