毎日Atcoder #1 ABC-002-d

問題概要

• N人の国会議員とM個の人間関係
  • N <= 12
  • M <= N * (N - 1) / 2
• N人の中で何人かを選び派閥を作る
  • 派閥条件：派閥内の議員はお互いに知り合いである
• 最大派閥の議員数を求める

考え方

まともに考えた場合

• グラフ問題
  • 各関係をグラフにして，一番大きいグラフを求める
  • 最大クリーク問題
  • NP困難問題

真剣に考えるなら論文だったり読みながらやるのかな…？

今回の問題では…？

• N <= 12　M <= 66
• O(NM)，O(N^2)，O(M^2) : OK
• O(2^N) : OK（重要）

N, M共に条件が緩いため，全探索が可能であることに着目する．

解き方

• 国会議員の組み合わせを全て出す
  • 全探索
  • O(2^N)
  • 例：(1), (2), (3), (1,2), (1,3), ...
• その組み合わせが条件に満たしているか比べる
  • O(N^2)
  • 例：(1,2,3,4)の場合：
    • if (1,2) in 条件
    • if (1,3) in 条件
    • etc...

全ての組み合わせが条件を満たしているものの内，最も多い要素数が答え

実際に解いたコード

faction_result = 0


# 深さ優先探索を行う関数
def dfs(xy_list: list, member_count: int, position: int, member_list: list):
    # 探査範囲外に探査した場合
    # 選択した人と人の組み合わせを全てxy_listと比較する
    # xy_list内になければそれは条件に合致しないとわかる
    # print(member_list)
    if member_count < position:
        for first_member in range(len(member_list) - 1):
            for second_member in range(first_member + 1, len(member_list)):
                disc_list = [member_list[first_member], member_list[second_member]]
                # print(Disc_list, xy_list)
                if disc_list not in xy_list:
                    return

        # faction_resultと値を比較して小さい値を代入する
        print(member_list)
        global faction_result
        if faction_result < len(member_list):
            faction_result = len(member_list)

    # dfsを利用する
    # その人を選択しないか，するかの2通り
    else:
        # 選択しない
        dfs(xy_list, member_count, position+1, member_list)
        # 選択する
        dfs(xy_list, member_count, position+1, member_list + [position])


# [1], [2], [3], [1,2], [1,2,5]
def main():
    # 標準入力
    N, M = map(int, input().split())

    # 標準入力を入れる配列
    xy_list = []

    # M回入力を受け付ける
    for _ in range(M):
        xy_list.append(list(map(int, input().split())))

    # 深さ優先探索にて再帰計算
    dfs(xy_list, N, 1, [])

    # 結果出力
    print(faction_result)


if __name__ == '__main__':
    main()