AtCoder

ABC318 D問題(General Weighted Max Matching)を解く

AtCoder_ABC318_D

AtCoder が提供しているABC(AtCoder Beginner Contest)318 のD問題をC++とPythonで解いてみました。ABC318は、2023年9月2日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 General Weighted Max Matching(Difficulty : 1017)

問題はリンク先をご覧ください。

ABC318 D問題 General Weighted Max Matching

DFSで全探索することで解くことができます。AtCoder Problems による Difficulty は 1017 でした。

解答案

頂点の数 $N$ には、$2 \leqq N \leqq 16$ という制約があります。

頂点が最大の16個ある場合を考えます。最初に選ぶ頂点を仮に1とします。 残りの頂点は15個あり、そこから一つの頂点を選ぶことによって辺を選ぶことになります。残りの頂点は14個あり、そこからもう一つの頂点を選ぶことによって、もう一つ辺を選びます。結果的に16個ある頂点から、8個の辺を選びます。この選び方は、

$$15 \times 13 \times 11 \times 9 \times 7 \times 5 \times 3 \times 1 = 2027025 $$

通りとなります。計算量的には間に合います。この8重ループは、バックトラックと呼ばれる再帰関数を使う手法で実現します。ABC310D解説記事)でも使いました。

C++ プログラム例(ABC318D)

プログラムの解説です。

  • 再帰関数 dfs の引数は、それまでの辺の重みの総和です。
  • 頂点が使われているか配列 used で管理します。その配列を用いて、番号が一番小さい未使用の頂点 i を選びます(16ー20行目)。未使用の頂点が無くなれば戻ります。
  • 残りの未使用の頂点 j を選び、次の辺を選ぶために再帰関数 dfs を呼びます(26ー32行目)。
  • 未使用の頂点を「使用」にしてdfsを呼び出し、戻ってきたら「未使用」に戻します(バックトラック)。
  • 頂点が奇数の場合は、すべて使い切るように頂点数を増やして偶数にします(46、47行目)。これは辺の重みがすべて0の頂点を加えることになるため総和に影響を与えません。

以下が、C++プログラムとなります。キーとなる行の背景行を変更しました。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

int n;
ull result = 0;
vector<vector<ull>> d(16 + 1, vector<ull>(16 + 1, 0));
vector<bool> used(16 + 1, false);

void dfs(ull w)
{
	result = max(result, w);

	int i, j;
	for (i = 1; i <= n; ++i) {
		if (!used[i]) {
			break;
		}
	}
	if (i > n) {
		return;
	}

	used[i] = true;
	for (j = i + 1; j <= n; ++j) {
		if (!used[j]) {
			used[j] = true;
			dfs(w + d[i][j]);
			used[j] = false;
		}
	}
	used[i] = false;

	return;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n - 1; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			cin >> d[i][j];
		}
	}
	if (n % 2 == 1) {
		++n;
	}

	dfs(0);

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC318D)

C++のプログラムを移植しました。Python は再帰関数の呼出回数に1000回という制限がありますが、この問題ではその制限を拡張する必要はありませんでした。

以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。

"""AtCoder Beginner Contest 318 D"""


def dfs(w):
    global n
    global result
    global d
    global used

    result = max(result, w)

    for i in range(1, n + 1):
        if not used[i]:
            break
    else:
        return

    used[i] = True
    for j in range(i + 1, n + 1):
        if not used[j]:
            used[j] = True
            dfs(w + d[i][j])
            used[j] = False
    used[i] = False

    return


n = int(input())
result = 0
d = [[0 for j in range(16 + 1)] for i in range(16 + 1)]
used = [False] * (16 + 1)
for i in range(1, n):
    a = list(map(int, input().split()))
    for j in range(i + 1, n + 1):
        d[i][j] = a[j - (i + 1)]
if n % 2 == 1:
    n += 1

dfs(0)

print(result)

こちらも「AC」と判定されました。

最後に

公式解説は、bitDP で解く方法を紹介していました。今の私では、bitDPの解説が腹落ちせず、解説放送で紹介されている方法を紹介しました。バックトラックのよい復習になりました。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA