Codeforces ECR #135 : F. Fishermen

本番中のAC数が妙に少ない。
https://codeforces.com/contest/1728/problem/F

問題

N要素の整数列Aが与えられる。
このAをシャッフルしたものに対し、Bを以下のように定める。

• B[0]=A[0]
• B[i+1]は、B[i]より大きなA[i+1]の倍数の最小値

Aを任意にシャッフルできる場合、Bの総和の最小値を求めよ。

解法

鳩ノ巣原理により、A[i]に対しBにはk*A[i] (1≦k≦N)の範囲しか現れない。
このN^2通りの値を、N個のA[i]の値とマッチングを取ることを考える。
あとは最小コストフロー＋二部マッチングを考えると解が求まるが、これだとO(N^4)とかかかり間に合わない。

k*A[i]の値の小さい順に、フローを流してみて、マッチングが増えるごとに解に計上していくとO(N^3)程度で済むようだ。

int N;
int A[1010];
vector<int> Vs;
vector<int> E[1<<20];
int vis[1<<20];
int op[1010];

int dfs(int cur) {
	if(vis[cur]) return 0;
	vis[cur]=1;
	FORR(e,E[cur]) if(op[e]==-1||dfs(op[e])) {
		op[e]=cur;
		return 1;
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		FOR(j,N) Vs.push_back(A[i]*(j+1));
	}
	sort(ALL(Vs));
	Vs.erase(unique(ALL(Vs)),Vs.end());
	
	FOR(i,N) FOR(j,N) {
		x=lower_bound(ALL(Vs),A[i]*(j+1))-Vs.begin();
		E[x].push_back(i);
	}
	int NV=Vs.size();
	ll ret=0;
	MINUS(op);
	FOR(i,NV) if(dfs(i)) {
		ret+=Vs[i];
		ZERO(vis);
	}
	cout<<ret<<endl;
	
}

まとめ

これは知らないテクだなぁ。