ABC236D - 解説つき！競ってわかる　はじめてpythonプログラミング

ABC236D の解説

解答コード

https://atcoder.jp/contests/abc236/submissions/28784903

問題

2N人を2人1組のNグループに分けたときの組み合わせ全探索する問題です．

解説

所感ですが，考えるのに１時間，コーディングに１時間ほどかかったので，コンテストに参加していたら，高い確率で解けてないだろうなーという問題でした．情けない...

組み合わせの数え方ですが，まずは具体例を用いて考えます．
4人（1, 2, 3, 4）を2グループに分ける場合の数を順列で考えると，
a) [1, 2], [3, 4]
b) [1, 2], [4, 3]
c) [1, 3], [2, 4]
d) [1, 3], [4, 2]
e) [1, 4], [2, 3]
f) [1, 4], [3, 2]
g) [2, 1], [3, 4]
h) [2, 1], [4, 3]
i) [2, 3], [1, 4]
j) [2, 3], [4, 1]
k) [2, 4], [1, 3]
l) [2, 4], [3, 1]
m) [3, 1], [2, 4]
n) [3, 1], [4, 2]
o) [3, 2], [1, 4]
p) [3, 2], [4, 1]
q) [3, 4], [1, 2]
r) [3, 4], [2, 1]
s) [4, 1], [2, 3]
t) [4, 1], [3, 2]
u) [4, 2], [1, 3]
v) [4, 2], [3, 1]
w) [4, 3], [1, 2]
x) [4, 3], [2, 1]

の4!通りになりますが，a)とb)が同じことを表しているように，数字の並ぶ順番が違うだけで，本質的なグループ分け方に違いのない無駄な組み合わせがたくさんあります．これでは計算が間に合いません．

そこで，iとjがペアを示す[i, j]という表記に，i<jの制約を加えてみると，
a) [2, 4], [1, 3]
b) [1, 3], [2, 4]
c) [1, 2], [3, 4]
d) [1, 4], [2, 3]
e) [2, 3], [1, 4]
f) [3, 4], [1, 2]
の場合の数が考えられます．しかし，これでもa)とb)はグループの順番が前後しているだけで，グループの分け方には影響がありません．すなわち無駄なカウントになります．

そこでさらに，各ペアの左側の数字（[i, j]のiの方）が代表者としたとき，代表者の数字が小さい順に並べるという制約を加えると，
a) [1, 4], [2, 3]
b) [1, 3], [2, 4]
c) [1, 2], [3, 4]
に減らすことができます．これで間に合います．

組み合わせの数え方をまとめます．

1つ目のペアを作成するとき，代表者（左側）を候補者の中で最小の数字，つまり1を選ぶ．ペアの相方の選び方は残りの候補者の数だけある（3通り）．例えば2を選んだとすると，1つ目のペアは[1, 2]．

2つ目のペアを作成するとき，代表者は残りの候補者の中で最小．すなわち3．最後に残った人をペアにすれば，2つ目のペアは[3, 4]となります．

こうすることで，順番が違うだけでグループ分けの実質的な意味に違いをなさない無駄な組み合わせを排除できます．

では，実装します．

標準入力を読み込みます．解答となる変数ansも定義しておきます．

N = int(input())
A = [list(map(int, input().split())) for _ in range(2*N-1)]
ans = 0

リストから値を除いたあと，除かれたあとのリストを返す関数を定義します．
理由は，あるリストから特定の値を取り除くremove関数が標準でありますが，returnがNoneなのでこの場合使いづらいためです．後々のコードをスッキリさせるために自作します．
定義する際に，入力のlistをcopyをしてglobalなリストには直接作用しないようにしています．

def removed(l, v):
    l = l.copy()
    l.remove(v)
    return l

深さ優先探索の再帰関数を記述します．
関数の冒頭で，候補者xからまず最小となる数字x_minを除きます（代表者）．
残りの候補者の数だけペアの組み合わせがありますので，for文でループ処理します．
ペアが決まったら，リストxから選んだ候補者xiをremoveして，その場で（注1）排他的論理和を計算し，その段階でのスコアを算出します．
候補者がゼロになったら全てペアを組んだことを意味するので，ansとの大小比較をして終了です．
まだ候補者がいれば，再帰してペアを組み続けます．

def dfs(x, score):
    global ans

    x_min = min(x)
    x.remove(x_min)
    for xi in x:
        x_next = removed(x, xi)
        score_next = score ^ A[x_min][xi-x_min-1]
        if len(x_next) == 0:
            ans = max(ans, score_next)
        else:
            dfs(x_next, score_next)
    return

*注1．排他的論理和をその場で計算しないと，同じ組み合わせのペアの相性を配列Aに何度もアクセスし，同じペア間の排他的論理和を何度も計算することになり非効率になります．例えば，8人を4ペアに分けるとき
a) [1, 2], [3, 4], [5, 6], [7, 8]
b) [1, 2], [3, 4], [5, 7], [6, 8]
では，前半の2ペア間の排他的論理和は同じなので，これを毎回計算しないようにするためです．

関数を実行して終了です．

dfs(list(range(2*N)), 0)
print(ans)

以上，ABC236Dの解法でした．