競技プログラミング 問題名：派閥

問題名　派閥

高橋くんは、AtCoder国の腐敗した政治を正すため、国会議員となろうと決めました。
もともと人心掌握術とスピーチに定評があった高橋くんは、何の苦労をすることもなく当選しました。
しかし、議員になってからが本番です。国を正すためには、首相に任命される必要があります。

AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係
(x, y) が存在します。人間関係 (x, y) とは、議員 x と議員 y が知り合いであることを意味します。
高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。
派閥に含まれるすべての議員は互いに知り合いでなければなりません。
高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。

ルール

入出力のサンプル 1

入力例.1

5 3
1 2
2 3
1 3

1 行目：5 人の議員と 3 つの人間関係が存在する。
2 行目：議員 1 と議員 2 は知り合いである。
3 行目：議員 2 と議員 3 は知り合いである。
4 行目：議員 1 と議員 3 は知り合いである。

出力例.1

3

議員 1、議員 2、議員 3 は互いに知り合いなので、この 3 人は派閥を構成することができる

入出力のサンプル 2

入力例.2

5 3
1 2
2 3
3 4

出力例.2

2

議員数 2 の派閥として
議員 1 と議員 2 の派閥
議員 2 と議員 3 の派閥
議員 3 と議員 4 の派閥
の 3 通りが考えられます。

入出力のサンプル 3

入力例.3

7 9
1 2
1 3
2 3
4 5
4 6
4 7
5 6
5 7
6 7

出力例.3

4

入出力のサンプル 3

入力例.4

12 0

出力例.4

1

たとえ
12人の議員がいても、誰も知りあいでなければ
1 人からなる派閥しか作成することはできません。

解答ロジック

シンプルに分けると以下の三つのステップになるかと思います。
入出力サンプル１を例として考えます。
議員数は5人、関係性は3つです。

①入力から議員の関係性を配列に落とし込む

• 議員1が知り合いなのは[議員2,議員3]
• 議員2が知り合いなのは[議員1,議員3]
• 議員3が知り合いなのは[議員1,議員2]

上記を配列に格納します。
二次元配列で
1番目の配列は議員１が知り合いの議員
2番目の配列は議員２が知り合いの議員
3番目の配列は議員３が知り合いの議員となっています。

array = [ [2,3], [1,3], [1,2] ]

②派閥の組み合わせを網羅的に洗い出す。

次に組み合わせの洗い出しです。
現状は以下の派閥の組み合わせが考えられます。

・３人の時　(1-2-3)
・2人の時　(1-2),(1-3),(2-3)
・1人の時　(1),(2),(3)

３人しかいない場合は手作業でも網羅できると思います。
しかしもしこれが12人いたら。。？(1-2-3-4-...)なんてやってられませんよね。。

規則を見つけ出してルール化することが必要です。
自分は上記の組み合わせを以下のルールに落とし込みました。
・0と1で表現する。
・必ず人数分の桁を確保する。

(1-2-3)→(1-1-1)
(1-2)  →(1-1-0)
(3)    →(0-0-1)
数字がある時は1で表現します。
数字の大きさは左から数えた時の添字で判断します。
こうすれば派閥が1人の時でも3桁のデータになります。
プログラミングではデータの形が揃っている方が繰り返し処理とかも実行しやすいです。

入出力サンプル1を網羅的に書き出すと以下になります。
上の規則性の見出しづらいものよりも規則は見えそうです。
上から1の数が1つずつ減っている。０の数が1つずつ増えている。そんな規則が見えてくるとおもいます。

(1-1-1)
(1-1-0),(1-0-1),(0-1-1)
(1-0-0),(0-1-0),(0-0-1)

③網羅的に洗い出した②と①を照らし合わせていく

次に①と②を照らし合わせていきます。
以下の網羅的に洗い出した表は上から下に派閥のサイズが小さくなっています。
今回の問題では組みうる派閥の最大の人数を出力するのが目的です。
なので上から順番にループを回して(1-1-1)が実現できるか？(1-1-0)が実現できるか？(1-0-0)が...
と確認していけば良さそうです。

(1-1-1)
(1-1-0),(1-0-1),(0-1-1)
(1-0-0),(0-1-0),(0-0-1)

(1-1-1)と(1-0-1)が実現できるかの確認方法

議員1と議員２と議員３から見た時に知り合いが誰なのか？を確認する必要があります。
それぞれの立場に立って考えていく必要があります。
その人の立場の箇所を星★にして見ていきます。

(1-1-1)に対しての議員１からの視点.

(★-1-1)
議員１からのみると他の議員２と議員３の場所は１になっています。
つまり２と３は知り合いということになります。

(1-0-1)に対しての議員１からの視点.

(★-0-1)
議員１からのみると
議員２の場所は０つまり「知り合いではない」
議員３の場所は１つまり「知り合い」
と判断することができます。

上記の考え方を元に(1-1-1)に対しての確認を行います。

(1-1-1)の時は言い換えると
・議員1から見て議員2と議員３が知り合い
・議員2から見て議員1と議員３が知り合い
・議員3から見て議員２と議員1が知り合い
の３パターンを満たす必要があります。

プログラム的に考えると
以下の議員の組み合わせ表(①で出したもの)において

array = [ [2,3], [1,3], [1,2] ]

sample.rb

・配列の1番目に2と3があること → array[0].include?(2) and array[0].include?(3)
・配列の2番目に1と3があること → array[1].include?(1) and array[0].include?(3)
・配列の3番目に1と2があること → array[2].include?(2) and array[0].include?(1)

になります。

まとめると以下のステップになります。

①以下の網羅的な組み合わせをループで回す

(1-1-1),(1-1-0),(1-0-1),(0-1-1),(1-0-0),(0-1-0),(0-0-1)

②(1-1-1)等の要素に対してループを回す。
それぞれのループでtrueかfalseか確認

・配列の1番目に2と3があること→true
・配列の2番目に1と3があること→true
・配列の3番目に1と2があること→true

③　②の結果で分岐
②が全部trueの時
(1-1-1)の配列の１の数が派閥の人数なので出力として返す。

②が一つでもfalseの時
次の(1-1-0)を確認しにいく。

解答のコード

上記全てのロジックを落とし込んだのが以下になります。
returnやnext、breakを用いて適宜ループ処理を抜けて無駄な処理を走らせないことで
実行時間を短縮しています。

answer.rb

congress_number,relations = gets.split(' ').map{|i| i.to_i}
return puts 1 if relations == 0

# 議員の組み合わせの表を作成
congress = Array.new(congress_number) { [] }
relations.times do
  men1, men2 = gets.split(' ').map{|i| i.to_i}
  congress[men1 - 1] << men2
  congress[men2 - 1] << men1
end

ans = -1

# 存在しうる組み合わせを01で表現しループ
[0,1].repeated_permutation(congress_number).reverse_each do |permutation|
  next if ans > permutation.count(1) #派閥のサイズが今より小さいものは調べない
  result = true #組み合わせを確認した結果

  permutation.each_with_index do |p1, index1|
    next if p1 == 0

    permutation.each_with_index do |p2, index2|
      next if p2 == 0 or index1 == index2
      unless congress[index1].include?(index2 + 1)
        result = false
        break
      end
    end
  end
  ans = permutation.count(1) if result
end

puts ans