ABC111 C問題

問題概要

数列 \(a_1\), \(a_2\), ... , \(a_n\) が次の条件を満たす時、/\/\/\/と呼ぶことにする。

  • 各 \(i = 1, 2, ... n - 2 \) について、 \( a_i = a_{i+2} \)

  • 数列に現れる数はちょうど２種類

偶数長の数列 \(v_1, v_2, ... , v_n\)が与えられる。要素をいくつか書き換えることでこの数列を /\/\/\/ にしたい。この時、書き換える要素の数の最小値を求めよ。

制約

  • 2 ≤ n ≤ 105
  • n は偶数
  • 1 ≤ \(v_i\) ≤ 105
  • \(v_i\) は整数

問題へのリンクはこちら

考えたこと

  • 与えられる数列がちょうど偶数長なので、奇数番目と偶数番目に分けて考える。
  • 基本的には、奇数番目、偶数番目それぞれの最頻値を求め、その出現回数を n から引いて算出する。
  • 最頻値が一致する時、数列に現れる数がちょうど２種類という制約に違反するので、２番目に出現回数の多い数の要素数を計算しておき、偶数番目、奇数番目の配列でどちらを採用すべきかを計算する。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;


int main() {
  int n; cin >> n;
  vector<int> e(n), o(n);
  int maxn = 1000001;
  int ev[maxn] = {0}, od[maxn] = {0};
  for(int i = 1; i <= n; i++) {
    if(i%2==0) {
      cin >> e[i/2];
      ev[e[i/2]]++;
    }
    if(i%2==1){
      cin >> o[i/2];
      od[o[i/2]]++;
    }
  }
  int maxEv = 0;
  int secEv = 0;
  int maxEvN = 0;
  int maxOd = 0;
  int secOd = 0;
  int maxOdN = 0;
  for(int i = 1; i < maxn; i++) {
    if(ev[i] >= maxEv) {
      secEv = maxEv;
      maxEv = ev[i];
      maxEvN = i;
    } else if(ev[i] >= secEv) {
      secEv = ev[i];
    }
    if(od[i] >= maxOd) {
      secOd = maxOd;
      maxOd = od[i];
      maxOdN = i;
    } else if(od[i] >= secOd) {
      secOd = od[i];
    }
  }
  if(maxEvN == maxOdN) {
    cout << min((n-maxOd-secEv), (n-secOd-maxEv)) << endl;
  } else {
    cout << n - maxEv - maxOd << endl;
  }

  return 0;
}