Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What are the problem?

posted at

updated at

Organization

毎日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()

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
1
Help us understand the problem. What are the problem?