ABC-081-C Not so Diverse

■■■問題■■■

高橋君は、N個のボールを持っています。
最初、i番目のボールには、整数Aiが書かれています。

高橋君は、いくつかのボールに書かれている整数を書き換えて、
N個のボールに書かれている整数がK種類以下になるようにしたいです。

高橋君は、少なくとも何個のボールの整数を書き換える必要があるでしょうか？

■■■入力■■■

N K
A1 A2 ・・・ AN

●1 <= K <= N <= 20万
●1 <= Ai <= N
●与えられる数値はすべて整数

■■■出力■■■

高橋君が、少なくとも何個のボールの整数を書き換える必要があるかを出力せよ。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 2");
            WillReturn.Add("1 1 2 2 5");
            //1
            //例えば、5番目のボールに書かれている整数を2に変更すると、
            //ボールに書かれている整数は 1,2 の2種類となります。
            //一方、まったく書き換えを行わずに、
            //ボールに書かれている整数の種類数を2以下にすることはできないので、
            //1を出力します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4");
            WillReturn.Add("1 1 2 2");
            //0
            //最初、ボールに書かれている整数の種類数は2なので、
            //まったく書き換えを行う必要はありません。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 3");
            WillReturn.Add("5 1 3 2 4 1 1 2 3 4");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int K = wkArr[1];

        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        int Answer = 0;
        var Query = AArr.GroupBy(X => X).OrderByDescending(X => X.Count()).Skip(K);
        foreach (var EachItem in Query) {
            Answer += EachItem.Count();
        }
        Console.WriteLine(Answer);
    }
}

解説

GroupByメソッド、OrderByDescendingメソッド、Skipメソッドを組み合わせてます。