SRM 251 DIV1 Hard MusicCompilation

問題 Editorial

問題

アーティストの名前とその人の曲の数artistsがいくつか与えられる。
各アーティストがその人の曲の数だけ出てくるリストであって、

let d v = sum. map (maybe 0 succ. uncurry elemIndex). zip v. tail. tails$ v

と定義されるd(x)を最大化する必要がある。
そのとき、辞書順最小のものを求めよ

解答

最大化はgreedyで、「最初にcountが大きい方から埋める」「そのあとは、countが大きい順に、また前との距離が大きい順に」やる。これはpriority_queueで上手く書ける。
それで辞書順greedyやった。
Editorialや他の人の解答によると、もっと簡単に規則的に生成できるようだ。
基本的なgreedyと、あとはどうでもいいからソートしてやる！のような感じで。

コメント

コード汚いし遅すぎるし…きれいな解答書きたい

コード

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <sstream>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef vector<string> vs; 
struct MusicCompilation {
	int greedy(int tt, const vi& prev, const vi& count) {
		int n = prev.size();
		vpii v;
		rep(i, n) v.pb(mp(count[i], i));
		sort(all(v), greater<pii>());
		priority_queue<pii> q;
		int r = 0, t = tt;
		rep(i, v.size()) if(v[i].first) {
			if(prev[v[i].second] == -1) {
				++ t;
				if(v[i].first > 1) q.push(mp(v[i].first - 1, -(t - 1)));
			} else if(v[i].first) q.push(mp(v[i].first, - prev[v[i].second]));
		}
		while(!q.empty()) {
			pii p = q.top(); q.pop();
			r += t - -p.second;
			++ t;
			if(p.first > 1) q.push(mp(p.first - 1, - (t - 1)));
		}
		return r;
	}
	vector <string> makeCompilation(vector <string> artists) {
		int n = artists.size();
		if(n == 0) return vs();
		vs name(n); vi count(n); int sum = 0;
		vector<pair<string,int> > v;
		rep(i, n) {
			stringstream ss(artists[i]);
			string s; int x; ss >> s >> x; v.pb(mp(s,x));
			sum += x;
		}
		sort(all(v)); rep(i, n) name[i] = v[i].first, count[i] = v[i].second;
		int mx = greedy(0, vi(n, -1), count);
		vs r;
		vi prev(n, -1); int prevsum = 0;
		rep(t, sum) {
			int mi = -1;
			rep(i, n) if(count[i] > 0) {
				int prevsum_t = prevsum;
				if(prev[i] != -1) prevsum_t += t - prev[i];
				count[i] --; int prev_t = prev[i]; prev[i] = t;
				int x = prevsum_t + greedy(t+1, prev, count);
				if(x == mx) { mi = i; count[i] ++; prev[i] = prev_t; break; }
				count[i] ++; prev[i] = prev_t;
			}
			if(prev[mi] != -1)prevsum += t - prev[mi]; prev[mi] = t; count[mi] --; r.pb(name[mi]);
		}
		return r;
	}
};