競プロ初中級者100問

ABC002D 派閥

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc002/tasks/abc002_4

この問題は全探索を用いて解くことができます。

方針

  • 議員の集合を考えます。その集合内で考どの二人を選んでも二人が知り合いである場合、その集合は派閥にすることができます。
  • 議員の集合として考えられる組み合わせは2^N-1通りとなります。
    • 理由は、集合に所属する議員を1、そうでない議員を0として表現するとわかりやすいでしょう。

ポイント

議員の集合として考えられる組み合わせを列挙する方法として、ループを回して二進数に変換する方法が考えられます。

（例）N=5の場合

1
2
3
4
5
1 -> 00001
2 -> 00010
3 -> 00011
...
31 -> 11111

しかし、Pythonの場合は標準ライブラリitertools.combinationsを使うと楽に実装できます。

以下のように、組み合わせを簡単に列挙することができます。

1
2
for comb in combinations(range(3),2):
    print (comb)
1
2
3
(0, 1)
(0, 2)
(1, 2)

コード

それでは実装にうつりましょう。

知り合いであるかどうかをlinkを使って表します。

1
2
3
4
5
6
7
from itertools import combinations
N, M = map(int, input().split())
link = [[0 for i in range(N)] for j in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    link[x-1][y-1] = 1
    link[y-1][x-1] = 1

続いて、議員の集合として考えられる組み合わせを列挙します。

最大の派閥に属する議員数を求めたいので、議員数が多くなるような集合から先に考えます。

1
2
3
ans = 1
for i in range(N,1,-1): # N, N-1, N-2, ... 2
    for comb in combinations(range(N),i):

議員の集合に対して考えられるペアを列挙し、知り合いかどうかをチェックします。

一つでも知り合いでない組があれば、その集合は派閥にはなり得ません。

ここで、またcombinationsが有効です。

1
2
3
4
5
6
for c in combinations(comb, 2): # 議員の集合に対して考えられるペアを列挙
    if (link[c[0]][c[1]] == 0): # 一つでも知り合いでない組があればNG
        break
else: # 派閥が作れた段階でプログラムを終了
    print (i)
    exit()

最後にコード全体を載せておきます。

コード（全体）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from itertools import combinations
N, M = map(int, input().split())
link = [[0 for i in range(N)] for j in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    link[x-1][y-1] = 1
    link[y-1][x-1] = 1

for i in range(N,1,-1): # N, N-1, N-2, ... 2
    for comb in combinations(range(N),i):
        for c in combinations(comb, 2): # 議員の集合に対して考えられるペアを列挙
            if (link[c[0]][c[1]] == 0): # 一つでも知り合いでない組があればNG
                break
        else: # 派閥が作れた段階でプログラムを終了
            print (i)
            exit()
print (1)

記事情報

  • 投稿日：2020年4月14日
  • 最終更新日：2020年5月8日