zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC111-C「/\/\/\/」です。
ポイント
与えられた数列の要素がそれぞれ何回ずつ出ているかを管理していく問題です。mapを使ったりpairを使ったり，様々な方法が考えられますが，ここは<int, int>を管理すれば良いだけですので，一次元配列を利用するのが最もシンプルだと思います。
つまり，一次元配列のindexが与えられた数列の要素，一次元配列の要素がそれぞれの出現回数を表すというアイディアです。添字を情報として扱うという点で少し賢い方法になっています。
問題の解法はシンプルです。偶数要素と奇数要素に分けてそれぞれの要素の出現回数を一次元配列に格納し，最も多く現れた回数をそれぞれ「n/2」回から引くというものです。これは，「n/2」個の要素のうち最も多く現れた要素「以外の」要素を書き換えるという操作を表しています。
この問題のポイントは，「1111」というような場合に上記解法では答えが0となってしまうことです。問題文の条件には「数列に現れる数はちょうど２種類」がありますので，偶数番目の数列と奇数番目の数列で最も多く現れた要素が同じである場合には，どちらかを2番目に多く現れた要素で書き換える必要があります。ここは，if文を用いて素直に条件分岐してあげましょう。
最も多く出現した要素を求めるためにはmax_element，逆順にソートするためには.rbegin()と.rend()を利用しましょう。
<int, int>は一次元配列で管理する
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int n;
int main(){
cin >> n;
vector<int> V(n);
rep(i, n) cin >> V[i];
// 偶数番目の出現回数を管理する一次元配列
vector<int> A(100010);
// 奇数番目の出現回数を管理する一次元配列
vector<int> B(100010);
rep(i, n){
if (i%2==0) A[V[i]]++;
else B[V[i]]++;
}
int max_a, max_b;
// 最大値のインデックス（=与えられた数列で最も多く現れた要素）
max_a = max_element(A.begin(), A.end()) - A.begin();
max_b = max_element(B.begin(), B.end()) - B.begin();
// もし最も多く現れた要素が異なる場合にはそれぞれの数列においてそれ以外を書き換えればOK
if (max_a != max_b) cout << (n/2-A[max_a]) + (n/2-B[max_b]) << endl;
// もし最も多く現れた要素が同じ場合にはどちらか一方を2番目に出現回数が多い要素に書き換えて結果が小さい方を出力すればOK
else{
sort(A.rbegin(), A.rend());
sort(B.rbegin(), B.rend());
cout << min((n/2-A[0]) + (n/2-B[1]), (n/2-A[1]) + (n/2-B[0])) << endl;
}
}
コメント