mini notes

競技プログラミングの解法メモを残していきます。

ABC018 D - バレンタインデー

ABC-D AtCoderコンテスト

D - バレンタインデー

概要

女子がN人、男子がM人いる。
女子をP人、男子をQ人選んで集団を作り、この集団に女子xiと男子yiが含まれる場合、女子は男子にチョコレートiを渡すことができ、幸福度がzi増加するものとする。(（xi, yi, zi）はR組与えられる)
女子と男子の組み合わせ方を変えて幸福度を最大化したい。このとき得られる幸福度の最大値を求めよ。

制約

1 ≦ N, M ≦ 18
1 ≦ R ≦ N * M
1 ≦ zi ≦ 10000

方針

考え方
半分全列挙、bit全探索。

女子の組み合わせの通り数は最大で18C9 = 48,620で、男子も同様である。
なので、女子もしくは男子のどちらか片方の組み合わせを全探索することはできるが、女子と男子を合わせた組み合わせを全探索することはできない。

ここで女子の組み合わせを決めたときに、幸福度を最大化する男子の組み合わせ方が勝手に決まらないか考えてみる。
すると、上記組み合わせで女子が渡せるすべてのチョコレートの幸福度を各男子ごとに集計し、その幸福度が大きい順にQ人の男子を選べばよい。

実装
いわゆるbit全探索です。
ただ、私の解答はbitを使わず、下記の方針でdfsで実装しています。

  • 女子の組み合わせを表すvector vをdfsの外に定義
  • dfsの後半には、次のdfsに入る前にvector vに女子を追加し、その後削除するロジックを定義
  • dfsの前半には、vector vにP人の女子が追加されて女子の組み合わせが１つ確定した場合のロジックを定義

感想

最初解いたときは、サンプルは全てACだけどジャッジでWAたくさん出たので疑問に思いましたが、単に全探索がちゃんと書けていないだけでした。その時の気持ち。

解答

Submission #4653205 - AtCoder Beginner Contest 018

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
const int max_R = 400;
int N, M, P, Q, R;
ll x[max_R], y[max_R], z[max_R];
 
ll ans = 0;
vector<int> v;
 
void print(){
	for(int a: v) cout << a << ",";
	cout << endl;
}
 
void dfs(int right, int n){
	if(n == P){
		// print();
 
		vector<ll> hp(M, 0);
		for(int a : v){
			for(int i = 0; i < R; i++){
				if(x[i] == a){
					hp[y[i]] += z[i];
				}
			}
		}
 
		sort(hp.begin(), hp.end(), greater<ll>());
		ll t = 0;
		rep(i, Q) t += hp[i];
 
		ans = max(ans, t);
	}
 
	for(int i = right; i < N; i++){
		v.push_back(i);
		// print();
		dfs(i+1, n+1);
		v.erase(v.end()-1);
		// print();
	}
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> M >> P >> Q >> R;
	rep(i, R) {
		cin >> x[i] >> y[i] >> z[i];
		x[i]--;
		y[i]--;
	}
 
	dfs(0, 0);
	cout << ans << endl;
}