SRM 381 500pt: TheHomework

問題概要

ふたつの集合A, Bが与えられる。集合Aに、値を加える、値を減らす、値を変えるなどの操作をして最短手数でBと等しくなるようにする問題。

後から考えたこと

• 何か全然やる気が出なくてさっさと答えを見てしまった…。
• 何があっているか、は重要ではなく、いくつ合っているか、が重要なので状態は(今の個数、合っている個数)で表される。
• 今の個数はあまり多くしても意味が無い。2*Nくらいあれば多分十分なので、状態数は全部で2*N^2くらい。
  • もちろん全部の状態がvalidな訳ではない。
• で、ひとつの状態から遷移するのはN通りくらいなのでBFSで十分間に合う。

practiceで通ったコード

計算量O(N^3)。

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1<<29;
const int MAX_N = 55;

int dist[2*MAX_N][MAX_N+1];

struct TheHomework {

	int transform(vector <int> first, vector <int> second) {
		int correct = 0, N = second.size();

		//初期化
		for(int i=0; i<2*MAX_N; i++){
			fill(dist[i], dist[i]+MAX_N+1, INF);
		}

		//いくつ一致しているか数える
		for(int i=0; i<(int)first.size(); i++){
			for(int j=0; j<(int)second.size(); j++){
				if(first[i] == second[j]){
					correct++;
					second[j] = -1;
					break;
				}
			}
		}

		queue< pair<int,int> > que;
		que.push( make_pair(first.size(), correct) );
		dist[first.size()][correct] = 0;

		while(!que.empty()){
			pair<int,int> tp = que.front(); que.pop();
			int num = tp.first, cor = tp.second, nd = dist[num][cor] + 1;

			//増やす
			for(int a=1; a <= num; a++){
				add(que, num+a, min(cor+a, N), nd);
			}

			//減らす
			for(int d=1; 2*d <= num; d++){
				add(que, num-d, min(cor, num-d), nd);
			}

			//変える
			for(int c=1; 2*c <= num; c++){
				add(que, num, min(cor+c, N), nd);
			}
		}

		return dist[N][N];
	}

	void add(queue<pair<int,int> >& que, int num, int correct, int d){
		if(num<0 || correct<0 || num >= 2*MAX_N || correct > MAX_N || dist[num][correct] != INF){
			return ;
		}

		dist[num][correct] = d;
		que.push( make_pair(num, correct) );
	}
};