/\/\/\/ [AtCoder Beginner Contest 111 C]

atcoder.jp

与えられた数列の項を書き換えて [a,b,a,b,a,b,a,b] のような形にするときの、操作回数の最小値を求めよ、という問題です。

与えられた数列の偶数番目だけを抜き出した偶数列と、奇数番目だけを抜き出した奇数列にわけて考えます。偶数列・奇数列内の要素は全て同じでなければならず、また偶数列の要素と奇数列の要素は異なっていなければなりません。それを表したのが [a,b,a,b,a,b,a,b] という数列です。

偶数列内の要素を一つに統一するにあたっては、もっとも多く出現している要素に統一すべきです。そのほうが操作回数が少なくなります。奇数列でも同様です。したがって、まず最初に偶数列・奇数列の最頻値をそれぞれ求めます。

偶数列と奇数列の最頻値が異なっていれば、すなわち偶数列の最頻値がa 、奇数列の最頻値が b ならば、偶数列内にある a でない要素を a に、奇数列内にある b でない要素を b にすることで答えが求まります。このときの答えは、n - (偶数列の最頻値の個数) - (奇数列の最頻値の個数) です。

偶数列と奇数列の最頻値が同じ場合は、どちらかの列を2番目の最頻値に統一することによって a = b になることを回避します。どちらの列で2番目の最頻値を採用するかということについては、min(偶数列で採用する場合の操作回数, 奇数列で採用する場合の操作回数) とすればよいです。

例外として、偶数列と奇数列の最頻値が同じ、かつ2番目の最頻値も同じ場合が考えられます。これはつまり、与えられた数列が [a,a,a,a,a,a,a,a] のように全て同じ数字から構成されている場合です。このときの操作回数は明らかに n/2 です。

といったような手順を実装することで AC できましたが、コードがやたら長くなってしまいました。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {

		int n = sc.nextInt();
		HashMap<Integer, Integer> even = new HashMap<>();
		HashMap<Integer, Integer> odd = new HashMap<>();

		//偶数列Map、奇数列Mapにそれぞれ数字の出現回数を記録する
		for (int i=0; i<n; i++) {
			int temp = sc.nextInt();
			if (i%2 == 0) {
				even.put(temp, even.getOrDefault(temp,0)+1);
			}
			else {
				odd.put(temp, odd.getOrDefault(temp,0)+1);
			}
		}

		//偶数列Map、奇数列Mapのそれぞれの最頻値を求める
		int evenMode = -1;
		int evenModeNum = -1;
		for (Map.Entry<Integer, Integer> e: even.entrySet()) {
			if (e.getValue() > evenModeNum) {
				evenModeNum = e.getValue();
				evenMode = e.getKey();
			}
        }
		int oddMode = -1;
		int oddModeNum = -1;
		for (Map.Entry<Integer, Integer> e: odd.entrySet()) {
			if (e.getValue() > oddModeNum) {
				oddModeNum = e.getValue();
				oddMode = e.getKey();
			}
		}

		//最頻値が違う場合は、偶数列Map、奇数列Mapのそれぞれの最頻値に合わせる
		if (evenMode != oddMode) {
			System.out.println(n-evenModeNum-oddModeNum);
		}
		else {
			//最頻値が同じ場合は、2番目の最頻値を求める
			int evenMode2 = -1;
			int evenMode2Num = -1;
			for (Map.Entry<Integer, Integer> e: even.entrySet()) {
				if (e.getValue()>evenMode2Num && e.getKey()!=evenMode) {
					evenMode2Num = e.getValue();
					evenMode2 = e.getKey();
				}
	        }
			int oddMode2 = -1;
			int oddMode2Num = -1;
			for (Map.Entry<Integer, Integer> e: odd.entrySet()) {
				if (e.getValue()>oddMode2Num && e.getKey()!=evenMode) {
					oddMode2Num = e.getValue();
					oddMode2 = e.getKey();
				}
			}
			
			//最頻値が偶奇列で同じ、かつ2番目の最頻値がない、すなわち数列が全て同じ数字の場合は、
			//n/2を例外として出力する
			if (evenMode2==-1 && oddMode2==-1) {
				System.out.println(n/2); return;
			}
			
			//偶数列で2番目の最頻値に合わせる場合と、奇数列で2番目の最頻値に合わせる場合を比べて、
			//操作回数の少ないほうを出力する
			System.out.println(Math.min(n-evenMode2Num-oddModeNum, n-evenModeNum-oddMode2Num));
		}

	}
}