SRM 612

250

最初は、文字が1文字だけ書かれている。(クリップボードにはなにもコピーされていない)

• 書かれている文字を全てクリップボードにコピーする。
• クリップボードに書かれている文字を貼り付ける。
• 1文字削除する。

の3つの操作を任意の順番で実行して、文字をS個作りたい。1つの操作に1sかかるとして、最小で何sかかるか。

コピーは2回以上連続で行う必要がなく、貼り付けと削除は順不同であることに注意して、DPすると解ける。

int dp[5000];

class EmoticonsDiv1 {
public:
	int printSmiles( int S ) {

		for(int i = 0; i <= 2000; i++)dp[i] = INF;
		dp[1] = 0;
		for(int i = 1; i <= 1000; i++){
			for(int j = 2; i*j <= 2000; j++){
				dp[i*j] = min(dp[i*j],dp[i]+j);
			}
			for(int j = 1000; j > 1; j--){ //本当はSの上限より少し大きくしなければならない
				dp[j-1] = min(dp[j-1],dp[j]+1);
			}
		}
		return dp[S];

	}
};

450

x座標と、y座標がn個与えられる。但し、同じ点は2回以上出てこない。
x座標とy座標の対応関係がわからない(x座標、y座標がソート/シャッフルされたものが渡されることを想像すればよい)として、n個の点のうちT個当てれば勝ちである。必ず勝てるときのTの最小値はいくつであるか。但し、推測するときは、与えられたデータに矛盾してはならない。
入力は、元のデータであるから、対応関係が分かる。

まず、入力が50以下なので、x,y座標を圧縮して、小さくする。
そのあと、最小費用流を用いると解ける。
例えば、x = {1,1,2}, y = {1,2,1}のときは、以下のようなグラフになる。(容量/コスト となっている)

当てる点のコストを1にして、それ以外の点のコストを0にして、最小費用流の計算をすると、最悪の場合にいくつ当たるかが分かる。これは、最悪の場合になっていないときに、さらにコストを小さくできることから分かる。

まだsubmitしていないので、正解かは分かりません。通しました(03/13)。他の人のコードと、蟻本を参考にして実装しました。

const int INF = 1<<25;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;

class SpecialCells {
public:
	struct edge{
		int dst,cap,cst;
		size_t rev;
	};
	void add(vector<vector<edge> > &g, int a, int b, int u, int c){
		g[a].push_back(edge{b,u,c,g[b].size()});
		g[b].push_back(edge{a,0,-c,g[a].size()-1});
	}
	void init(vector<int> &x){
		map<int,int> dr;
		int p = 1;
		for(int i = 0; i < x.size(); i++){
			if(!dr[x[i]]){
				dr[x[i]] = p++;
			}
			x[i] = dr[x[i]]-1;
		}
	}
	void ct_num(vector<int> &x){
		sort(x.begin(),x.end());
		vector<int> t(x[x.size()-1]+1,0);
		for(int i = 0; i < x.size(); i++){
			t[x[i]]++;
		}
		x = t;

	}
	int solve(vector<int> x, vector<int> y){
		set<pair<int,int> > st;
		for(int i = 0; i < x.size(); i++){
			for(int j = 0; j < y.size(); j++){
				st.insert(make_pair(x[i],y[i]));
			}
		}
		int F = x.size();
		ct_num(x);ct_num(y);


		int n = x.size()+y.size()+2;
		int s = n-2, t = n-1;
		vector<vector<edge> > g(n);
		for(int i = 0; i < x.size(); i++){
			add(g,s,i,x[i],0);
		}
		for(int i = 0; i < y.size(); i++){
			add(g,i+x.size(),t,y[i],0);
		}
		for(int i = 0; i < x.size(); i++){
			for(int j = 0; j < y.size(); j++){
				add(g,i,j+x.size(),1,st.count(make_pair(i,j)));
			}
		}


		int res = 0;
		int h[n];
		int dist[n];
		int prevv[n], preve[n];
		fill(h,h+n,0);
		while(F > 0){
			priority_queue<P, vector<P>, greater<P> > q;
			fill(dist,dist+n,INF);
			dist[s] = 0;
			q.push(P(0,s));
			while(!q.empty()){
				P p = q.top(); q.pop();
				int v = p.second;
				if(dist[v] < p.first) continue;
				for(int i = 0; i < g[v].size(); i++){
					edge &e = g[v][i];
					if(e.cap > 0 && dist[e.dst] > dist[v] + e.cst + h[v] - h[e.dst]){
						dist[e.dst] = dist[v]+e.cst+h[v]-h[e.dst];
						prevv[e.dst] = v;
						preve[e.dst] = i;
						q.push(P(dist[e.dst],e.dst));
					}
				}
			}
			if(dist[t]==INF) break;
			for(int v = 0; v < n; v++) h[v] += dist[v];

			int d = F;
			for(int v = t; v != s; v = prevv[v]){
				d = min(d,g[prevv[v]][preve[v]].cap);
			}
			F -= d;
			res += d*h[t];
			for(int v = t; v != s; v = prevv[v]){
				edge &e = g[prevv[v]][preve[v]];
				e.cap -= d;
				g[v][e.rev].cap += d;
			}
		}

		return res;
	}
	int guess( vector <int> x, vector <int> y ) {
		init(x);init(y);
		return solve(x,y);
	}
};

o-- 159.48 + 50.0 = 209.48
1964 -> 1964