C - /\/\/\/

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 112
C - /\/\/\/
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

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

・各 i=1,2,...,n−2について、i=ai+2
・数列に現れる数はちょうど 2種類

偶数長の数列 1,v2,...,vnが与えられます。 
要素をいくつか書き換えることでこの数列を /\/\/\/ にしたいです。
書き換える要素の数は最小でいくつになるか求めてください

制約

・2≤n≤10^5
・nは偶数
・1≤vi≤10^5
・viは整数

入力

入力は以下の形式で標準入力から与えられる。

n
v1 v2 ... vn

出力

書き換える要素数の最小値を出力してください。

解き方

こちらの解き方を参考にしています。
https://img.atcoder.jp/arc103/editorial.pdf
atcoder.jp

問題文の以下の条件から

・各 i=1,2,...,n−2について、i=ai+2
・数列に現れる数はちょうど 2種類

入力で与えられる配列を
偶数番目を全て同じ値、奇数番目を全て同じ値にすれば
「/\/\/\/」になるということが分かる。

また、
この問題で答えることは
「/\/\/\/」にするために
元の配列の要素を書き換える最小個数なので
元の配列の偶数番目と奇数番目、それぞれで
一番出てくる頻度が高い数字に書き換えたほうが
書き換える数字の数は少なくなる。

そのため、
基本的には
偶数番目と奇数番目で
「それぞれの一番出てくる頻度の高い数字」ではない要素の個数
（書き換えなければいけない個数）を数えて足せば答えになる。

しかし、偶数番目と奇数番目で
それぞれの一番出てくる頻度の高い数字が同じだった場合は
もしその数字に書き換えてしまうと
配列が全て同じ数字で構成されることになるので
もう一手間かける必要がある。

全てを一番頻度の高い数字に書き換えられないとなると
次に候補として上がるのは二番目に出てくる頻度の高い数字である。
そして、この二番目の候補が
偶数番目と奇数番目で二つあるので
偶数番目と奇数番目、
どちらをそれぞれの二番目に出てくる頻度の高い要素に書き換えれば
より書き換える数字の個数が少なくなるかを計算し、
少なくなる方で書き換えた要素の個数が答えになる。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        var v = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        if (v.Distinct().Count() == 1)
        {
            Console.WriteLine(N / 2);
            return;
        }
        //偶数番目用のDictionary(keyが要素、valueが出てくる回数)
        var evenDic = new Dictionary<int, int>();
        //奇数番目用のDictionary(keyが要素、valueが出てくる回数)
        var oddDic = new Dictionary<int, int>();
        for (int i = 0; i < N; ++i)
        {
            //偶数番目
            if (i % 2 == 0)
            {
                if (evenDic.ContainsKey(v[i])) evenDic[v[i]]++;
                else evenDic.Add(v[i], 1);
            }
            //奇数番目
            else
            {
                if (oddDic.ContainsKey(v[i])) oddDic[v[i]]++;
                else oddDic.Add(v[i], 1);
            }
        }
        //出てくる頻度の高い順に並び替え
        evenDic = evenDic.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
        oddDic = oddDic.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
        //書き換える数字の数
        var cost = 0L;
        //偶数番目で出てくる頻度の最も高い数
        var evenFirst = evenDic.First();
        //奇数番目で出てくる頻度の最も高い数
        var oddFirst = oddDic.First();
        //偶数番目、奇数番目、それぞれの要素の個数
        var half = N / 2;
        //偶数番目と奇数番目で最も出てくる頻度の高い要素が同じとき
        if (evenFirst.Key == oddFirst.Key)
        {
            //偶数番目で出てくる頻度が二番目に高い数
            var evenSecond = 1 < evenDic.Count() ? evenDic.Skip(1).First().Value : int.MinValue;
            //奇数番目で出てくる頻度が二番目に高い数
            var oddSecond = 1 < oddDic.Count() ? oddDic.Skip(1).First().Value : int.MinValue;

            //偶数番目、奇数番目のどちらかを二番目に出てくる頻度の高い数に書き換える

            //偶数番目が最も出てくる頻度の高い数、奇数番目が二番目に出てくる頻度の高い数　
            //に書き換えた場合の
            //書き換えなければいけない要素の個数
            long plan1 = (half - evenFirst.Value) + (half - oddSecond);
            //偶数番目が二番目に出てくる頻度の高い数、奇数番目が最も出てくる頻度の高い数　
            //に書き換えた場合の
            //書き換えなければいけない要素の個数
            long plan2 = (half - evenSecond) + (half - oddFirst.Value);

            //上の二つで書き換えなければいけない要素の数が小さいほうを採用
            cost = Math.Min(plan1, plan2);
        }
        //偶数番目と奇数番目で最も出てくる頻度の高い要素が違うとき
        else
        {
            cost = (half - evenFirst.Value) + (half - oddFirst.Value);
        }
        Console.WriteLine(cost);
    }
}