意外と罠にはまりやすい問題かもしれない！！！
この手の問題は「最適解の形を考える」という意識で解くと良さそう。

そして、コーナーケースがサンプルにあるのが親切。

問題概要

長さ $N$ ( $N$ は偶数) の数列 $a_{0}, a_{1}, \dots, a_{N-1}$ が /\/\/\/ であるとは

任意の $i$ に対して $a_{i} = a_{i+2}$

を満たすことをいう。与えられた数列 $v_{0}, \dots, v_{N}$ に対して、いくつか値を書き換えて /\/\/\/ となるようにしたい。書き換える要素の最小値を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le v_i \le 10^{5}$

考えたこと

少し考えると

偶数番目に登場する数値のうち、最も頻度が高いものを残して、他をそれに合わせる
奇数番目に登場する数値のうち、最も頻度が高いものを残して、他をそれに合わせる

という風にしたくなる。ほとんどの場合、それで正解になる。しかし、

偶数番目の最頻値
奇数番目の最頻値

が等しい場合には、両方ともそれに合わせてしまうと、 /\/\/\/ ではなく --- になってしまう。よって、偶数番目か奇数番目か、どちらかが妥協する必要がある。

結局

難しく考えてしまいそうになるが、結局、その場合は

偶数番目に登場する数値のうち、最も頻度が高いものを残して、他をそれに合わせる
奇数番目に登場する数値のうち、2 番目に頻度が高いものを残して、他をそれに合わせる

か、もしくは

偶数番目に登場する数値のうち、2 番目に頻度が高いものを残して、他をそれに合わせる
奇数番目に登場する数値のうち、最も頻度が高いものを残して、他をそれに合わせる

のどちらかにすればよいことがわかる。このうちのより答えが小さくなる方を選べば OK。偶数番目か奇数番目のどちらかが妥協すれば十分で、両方とも最頻値を諦める必要はない。

なお注意点として、「最頻値」が複数通りある場合もある。「7」と「10」が両方とも 1000 回ずつ登場して、それが最多だというような場合だ。しかしこの場合、どちらかを便宜的に最頻値と考えて、どちらかを便宜的に 2 番目に頻度が高い値、として問題ない。どちらを最頻値を考えても問題ない。

実装

よってこの問題は、「数列が与えられたときに、その最頻値と、二番目に頻度が高い値を求めよ」という問題に帰着された。これを考える。ここでは

まず、各値 v が何回登場したかを表すヒストグラムを作る
(頻度、値 v) をペアにした配列を新しく作り、頻度順にソートする

という風にすることにした。本当はソートしなくても 2 番目までなら $O(N)$ で求めることができるが、何も考えずにソートしてしまうもの簡単かなと思う。その場合は $O(N\log{N})$ 。好みの問題かなと。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pint = pair<int,int>;
const int MAX = 110000;

int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // 偶数番目、奇数番目について
    // どの数がどれだけあるかのヒストグラムを作る
    vector<int> odd_hist(MAX, 0), even_hist(MAX, 0);
    for (int i = 0; i < N; ++i) {
        if (i & 1) odd_hist[a[i]]++;
        else even_hist[a[i]]++;
    }

    // 頻度順にソート
    vector<pint> odd, even;
    for (int i = 0; i < MAX; ++i) {
        odd.push_back(pint(odd_hist[i], i));
        even.push_back(pint(even_hist[i], i));
    }
    sort(odd.begin(), odd.end(), greater<pint>());
    sort(even.begin(), even.end(), greater<pint>());

    // お互いの最大が異なればそれが答え、そうでなかったら 2 番目を持ち出す
    if (odd[0].second != even[0].second) {
        cout << N - (odd[0].first + even[0].first) << endl;
    }
    else {
        cout << N - max(odd[0].first + even[1].first,
                        odd[1].first + even[0].first) << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 111 C - /\/\/\/ (ARC 103 C) (緑色, 300 点)

問題概要

制約

考えたこと

結局

実装