品物の並び替え

• 品物の並び替え

• 愚直で解けるけど暇なので色々遊んでみた

自分の解法(340ms)

• 並び方を全通り試すのが$O(N!)$
• 品物のスコアを判定するのが$O(NM)$
• なので全体の計算量は$O(N!NM)$となる。
• $N=9, M=72$が最大なので当てはめると計算ステップは$235146240$回となる。
• 大体$10^8$回くらいだからギリギリだと思ったけど332msで解けてしまった。$10^8$回のステップが1秒ってのはあてにしすぎない方がいいのかも。

コード

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

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N, M;
int item1[100];
int item2[100];
int score[100];

signed main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> item1[i] >> item2[i] >> score[i];
	}

	// 並び方を定義する配列
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);

	int ans = 0;
	do {
		int sum = 0; // この並びの時の合計スコア

		// その並びになってるかを全て調べる
		for (int i = 0; i < M; i++) {
			int cnt = 0;
			for (int j = 0; j < N; j++) {
				if (cnt == 0 and v[j] == item1[i]) {
					cnt++;
				}
				if (cnt == 1 and v[j] == item2[i]) {
					cnt++;
				}
			}
			// その並びになってたらスコアを足す
			if (cnt == 2) {
				sum += score[i];
			}
		}

		chmax(ans, sum);
	} while (next_permutation(v.begin(), v.end()));

	cout << ans << endl;

	return 0;
}

ちょっと改善する(17ms)

• 2次元配列で持てば判定部分が$O(N^2)$になる
• よって全体的な計算量は$O(N!N^2)$となる
• N=9が最大なので最大の計算ステップは$29393280$回となる。大体$10^7$回なので余裕で間に合う
• これ頭いい。普通に思いつかなくないか？

コード

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

#define int long long

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N, M;
int item[100][100]; // item1, item2, scoreをこれひとつにまとめた

signed main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		item[a][b] = c;
	}

	vector<int> v(N);
	iota(v.begin(), v.end(), 0);

	int ans = 0;
	do {
		int sum = 0;

		for (int i = 0; i < N; i++) {
			for (int j = i+1; j < N; j++) {
				sum += item[v[i]][v[j]];
			}
		}

		chmax(ans, sum);
	} while (next_permutation(v.begin(), v.end()));

	cout << ans << endl;

  return 0;
}

DPを書いてみる(5ms)

• とりあえず再帰で書いてみる。普通の再帰じゃなくてbitDPに寄せた再帰。コードはこんな感じ
• 再帰がかけたらあとはメモ化するだけ
• 計算量はよくわからない。けど早い
• ループでDPを回すのはこんな感じのコード

コード

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

#define int long long

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N, M;
int item[100][100];
int dp[1<<9];

int rec(int mask) {
	if (mask >= (1<<N)-1) return 0;
	if (dp[mask] != -1) return dp[mask];

	int ret = 0;
	for (int i = 0; i < N; i++) { // iは新しく選ぶやつ
		// iを選んだことがあるなら飛ばす
		if (mask & (1 << i)) continue;

		// 新しく選ぶやつに関するスコアを計算
		int score = 0;
		for (int j = 0; j < N; j++) {
			if (mask & (1 << j)) {
				score += item[j][i];
			}
		}

		chmax(ret, rec(mask | (1 << i)) + score);
	}

	return dp[mask] = ret;
}

signed main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		item[a][b] = c;
	}

	fill(dp, dp+(1<<9), -1);

	int ans = rec(0);

	cout << ans << endl;

	return 0;
}

要点

• $N!​$をしたい気持ちになったらbitDPができるって強い人が言ってた