逆算的な発想をする

はじめに

言葉にするのは難しいが、最終的にこういった答えになってほしいから、てことはこれに当てはまる数を求めればいいよねといった発想を求められるとき。

配列を２種類の数字にしたい

代表問題

引用元（ABC111-C）
https://atcoder.jp/contests/abc111/tasks/arc103_a

数列 a1,a2,...,an が以下の条件を満たすとき、/\/\/\/ と呼ぶことにします。

• 各 i=1,2,...,n−2 について、ai=a(i+2)
• 数列に現れる数はちょうど 2 種類
  偶数長の数列 v1,v2,...,vn が与えられます。
  要素をいくつか書き換えることでこの数列を /\/\/\/ にしたいです。
  書き換える要素の数は最小でいくつになるか求めてください。

考え方

実際に上記の問題を解いた時のコードは以下となる。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // sort

using namespace std;

int main()
{
	long n;
	cin >> n;

	// 奇数番目の項で１番出現する数を求める
	// 同じく、偶数番目の項で１番出現する数を求める

	long itr_max = 100001;
	vector<long> even(itr_max, 0);
	vector<long> odd(itr_max, 0);

	long v;
	for (long i = 0; i < n; i++)
	{
		cin >> v;

		if (i % 2 == 0) odd[v]++;
		else even[v]++;
	}


	long max_e = -1, max_o = -1;
	long itr_e = 0, itr_o = 0;
	for (long i = 0; i < itr_max; i++)
	{
		if (even[i] > max_e)
		{
			max_e = even[i];
			itr_e = i;
		}

		if (odd[i] > max_o)
		{
			max_o = odd[i];
			itr_o = i;
		}
	}

	// 数字１種になっちゃうとき
	if (itr_e == itr_o)
	{
		long max_e2 = -1, max_o2 = -1;

		even[itr_e] = -1;
		odd[itr_o] = -1;
		
		for (long i = 0; i < itr_max; i++)
		{
			if (even[i] > max_e2) max_e2 = even[i];
			if (odd[i] > max_o2) max_o2 = odd[i];
		}

		if (max_e2 > max_o2) max_e = max_e2;
		else max_o = max_o2;
	}

	long ans = n - max_e - max_o;
	cout << ans;
}