読者です 読者をやめる 読者になる 読者になる

SRM696 div2 med

自分が参加した部屋(room19)がこの惨劇であったのでとりあえずどういう解法で解いたかを書いていきます。
ちなみに自分は見事に落ちました。

f:id:Matchald:20160812213810p:plain

問題概要

配列Aを配列Bと同じにするために、Aの値を配列Fの値で置き換える。しかし、置き換えられるのは1つの要素につき1回のみです。
Fの値は全て使わなければなりません。
最善の手を尽くした時にAとBの違いはどれだけあるかを数える。

例)
A = {2,2,2}
B = {2,2,2}
C = {1,2,3}

この時は以下のように値を変えたときがAとBとの差が一番小さくなります。
f:id:Matchald:20160812214848p:plain

解法

とりあえずA[i] != B[i]でA[i]をF[j]で置き換えた時にA[i] == B[i] となるようなF[j]があればその値にしてあげるとAとBとの違いが少なくなるのでこれを行います。
ただし、Fの値は一回しか使えないこととに注意する必要があります。

これが終わったらA[i] == B[i] == F[j] を A[i] = F[j] とします。この操作ではA[i]の値は変わりませんが、使わなければならないFの値を少なくするのが目標です。

ここまででFで使っていない値というのはAのどの要素に対してもF[i]の値で置き換えるとA[i] != B[i] となってしまう値の集合です。

あとは残っているFの要素数と,A[i] != B[i] の数の大きい方を答えとして出力するだけです。

C++のコード

#include<iostream>
#include<vector>
#include<algorithm>

class Arrfix {
public:
	int mindiff(std::vector<int> A, std::vector<int> B, std::vector<int> F) {
		std::vector<int> diff_pos, same_pos;

		for (int i = 0; i < A.size(); i++) {
			if (A[i] != B[i])
				diff_pos.push_back(i);
			else
				same_pos.push_back(i);
		}

		std::sort(F.begin(), F.end());

		// ラベルを貼り直してBと同じにできるならラベルを貼る
		for (int i = 0; i < diff_pos.size(); i++) {
			if (F.empty()) break;
			auto f = std::find(F.begin(), F.end(), B[diff_pos[i]]);
			if (f != F.end()) {
				F.erase(f); // 使ったラベルは削除
				diff_pos[i] = -1;
			}
		}

		// 余ったラベルで合ってる奴に貼っつけても大丈夫なら貼る
		for (int i = 0; i < same_pos.size(); i++) {
			if (F.empty()) break;
			auto f = std::find(F.begin(), F.end(), B[same_pos[i]]);
			if (f != F.end()) {
				F.erase(f); // このラベルは使ったので削除
			}
		}

		// A[i] = B[i] にしたところはdiff_posから削除
		std::sort(diff_pos.begin(), diff_pos.end());
		while (true) {
			auto a = std::find(diff_pos.begin(), diff_pos.end(), -1);
			if (a != diff_pos.end()) {
				diff_pos.erase(a);
			} else {
				break;
			}
		}

		return std::max(diff_pos.size(), F.size());
	}
};