D - Various Sushi

はじめに

競技プログラミングAtCoder Beginner Contest 116
D - Various Sushi
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

N個の寿司があり、それぞれの寿司には
「ネタ」tiと「おいしさdiのパラメータが設定されています。
あなたはこのN個の寿司の中からK個を選んで食べようとしています。
この時のあなたの「満足ポイント」は、以下のようにして計算されます。

・「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。
・「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。
・「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数をxとしたとき、x∗xである。

あなたは、「満足ポイント」をできるだけ大きくしたいです。 
この時の「満足ポイント」の値を求めてください。

制約

・1≦K≦N≦10^5
・1≦ti≦N
・1≦di≦10^9
・入力はすべて整数である。

入力

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

N K
t1 d1
t2 d2
.
.
.
tN dN

出力

あなたの得られる「満足ポイント」の最大値を出力してください。

解き方

こちらの解き方を参考にしています。 goo.gl goo.gl

全体の流れ

「満足ポイント」を最大化したいので、
「おいしさポイント」と「種類ボーナスポイント」を大きくすることを目指します。

①基準を作る
まず、解答を考えるうえで基準を作ります。
入力された寿司をおいしさポイントが高い順に並び替えて、
上から寿司をK個選びます。
ここで、選んだ寿司からより「満足ポイント」が大きくなるように考えていきます。

②「満足ポイント」を最大化するために基準を入れ替える
先程選んだK個の寿司は
おいしさポイントを最大としたものでした。
そのため、ここからさらに
「満足ポイント」を大きくしていこうと思うと
おいしさポイントは既に最大を選んでいるので
「種類ボーナスポイント」を増やしていくことを考えていきます。

ここで寿司を入れ替えていき、
「満足ポイント」の最大値を更新していき
最終的に最も大きい値が答えとなります。

具体的に入力例2でやってみる

上の流れを入力例2でやってみると以下のようになります。

入力

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

①基準を作る
上の入力を「おいしさポイント」順に並べ替えます

4 6
4 5
4 5
4 5
1 1
2 1
3 1

この時点での「満足ポイント」は
「おいしさポイント」6+5+5+5=21
「種類ボーナスポイント」1*1=1
「満足ポイント」21+1=22

②「満足ポイント」を最大化するために基準を入れ替える
寿司を入れ替えて、
①で出した「満足ポイント」の22を
さらに大きくしていくことを考えます。

「おいしさポイント」は既に①で最大のものを選んでいるので
「種類ボーナスポイント」を増やすことを考えていきます。

まず、①で選んだネタの種類は「4」だけです。
これを他のネタと入れ替えていくことを考えていきます


ネタを入れ替えていくことに気をつけることは以下の二点です。
1.既に選んでいる寿司から、ネタが重なっているものを入れ替えること
2.ネタを新しく選ぶ際は、ネタの中で最も「おいしさポイント」が大きいものを選ぶこと

1.既に選んでいる寿司から、ネタが重なっているものを入れ替えるこ
「種類ボーナスポイント」を増やす=ネタの種類を増やす、
ことが目的なので
既に選んでいる寿司からは
ネタが複数選ばれているものだけを入れ替え対象とします。
その際、対象とするものは「おいしさポイント」が低いものです。

例:①で選び出した寿司を以下とする

1 9
1 7
2 6
1 5

この際、入替対象となるのは
まず、ネタが重なっているものは「1」である。
「2」は一つしかないので入替対象にはならない。
「1」の中で「おいしさポイント」を低い順に並べると
「9,7,5」となる
この中で「9」は最もおいしさポイントが高いので
入替対象から外れ、
入替対象の寿司は以下の二つになる。

1 7
1 5

この二つの中でも「5」の方が小さいので、
入れ替える順番は「5,7」となる。

2.ネタを新しく選ぶ際は、ネタの中で最も「おいしさポイント」が大きいものを選ぶこと
選ばれていなかった寿司から入れ替える寿司を選定する際にも
「おいしさポイント」を考慮して、
同じネタの寿司でも「おいしさポイント」の高いものを選ぶようにします。

例:①で選ばなかった寿司を以下とする。

1 9
1 7
2 6
1 5

まずここからネタの重複を取り除きます。
(「種類ボーナスポイント」を増やしたいので同じネタの寿司は選ばない、
同じように、既に①に入っているネタも対象にはなりません。)
「2」は一つしかありませんが、「1」は3つあるので
この中から一番「おいしさポイント」が高い「9」が入替対象となります。

さらに「1」の「9」と「2」の「6」を比べると
「1」の「9」の方が「おいしさポイント」が高いので
入れ替える順番と対象は
上のものを優先度を高いとすると以下のようになります。

1 9
2 6



この1,2を踏まえて入力例2を進めると
まず①で選ばれている寿司は以下です。

4 6
4 5
4 5
4 5

1より入替対象となる寿司は「おいしさポイント」が「5」のものです。

4 5
4 5
4 5

そして、①で選ばれなかった寿司は以下です。

1 1
2 1
3 1

2より「おいしさポイント」が高い順に優先度をつけたいですが、
3つとも同じ「おいしさポイント」なので優先度はありません。

まず、
一つだけ入れ替えてみます。
選ぶネタを以下のように入れ替えます。

4 6
4 5
4 5
1 1

このとき「満足ポイント」は
「おいしさポイント」6+5+5+1=17
「種類ボーナスポイント」2*2=4
「満足ポイント」17+4=21
となります。

①で選んだ寿司の「満足ポイント」は22なので
①の方がポイントが高いです。
次に進みます。

寿司をもう一つ入れ替えます。

4 6
4 5
1 1
2 1

このとき「満足ポイント」は
「おいしさポイント」6+5+1+1=13
「種類ボーナスポイント」3*3=9
「満足ポイント」17+4=22
となります。

①で選んだ寿司の「満足ポイント」は22なので
①とポイント数は同じです。

さらに、次に進みます。

寿司をもう一つ入れ替えます。

4 6
1 1
2 1
3 1

このとき「満足ポイント」は
「おいしさポイント」6+1+1+1=9
「種類ボーナスポイント」4*4=16
「満足ポイント」9+16=25
となります。

①で選んだ寿司の「満足ポイント」は22なので
今回入れ替えたポイントの方が高いです。
ここで「満足ポイント」の最大値を更新します。

全てのネタが違う種類となり、
入れ替えられる寿司がなくなったので
入替はここで終了します。

ここでの最大値が「25」なので
入力例2の答えは「25」になります。

コード

コードで書くと以下のようになります。

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

class Dmondai
{
    static void Main()
    {
        var line = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var N = line[0];
        var K = line[1];
        //寿司を保存するリスト
        //ネタ、おいしさの順に格納
        var list = new List<long[]>();
        //入力から寿司の情報を保存
        for (int i = 0; i < N; ++i)
        {
            var line1 = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
            list.Add(new long[2] { line1[0], line1[1] });
        }
        //各ネタの中で一番「おいしさポイント」が高いものを保存しておく
        //寿司をネタの番号が小さい順、かつネタの中でも「おいしさポイント」が高い順に並び替える
        list = list.OrderBy(x => x[0]).ThenByDescending(x => x[1]).ToList();
        //各ネタの中で一番「おいしさポイント」が高いものに1、そうではないものに1を入れる
        for (int i = N - 1; 0 < i; --i)
        {
            if (list[i][0] != list[i - 1][0])
            {
                list[i][0] = 1;
            }
            else list[i][0] = 0;
        }
        //[0][0]には必ずネタの中で一番「おいしさポイント」が高いものがくる
        //上のループの中では判断できないので後で個別に1を入れる
        list[0][0] = 1;
        //①基準を作る
        //「おいしさポイント」が高い順に並び替える
        list = list.OrderByDescending(x => x[1]).ThenByDescending(x => x[0]).ToList();
        //上からK個寿司を選ぶ
        var selectedList = list.Take(K).ToList();
        //選んだネタの数(種類ボーナス)
        var selectedNeta = 0L;
        //選んだ寿司の「おいしさポイント」の合計
        var selectedOishisa = 0L;
        //入替の準備
        //選んだ寿司の中でネタが被った寿司の「おいしさポイント」を保存しておく
        var stack = new Stack<long>();
        //現在の「満足ポイント」の算出と、ネタがかぶった寿司の「おいしさポイント」の保存
        for (int i = 0; i < K; ++i)
        {
            selectedNeta += selectedList[i][0];
            selectedOishisa += selectedList[i][1];
            //ネタのかぶり
            if (selectedList[i][0] == 0) stack.Push(selectedList[i][1]);
        }
        //現在のポイント
        var ans = selectedOishisa + selectedNeta * selectedNeta;
        //②寿司を入れ替える
        //上のK個は既に選択済みの寿司なので、その次の寿司(index=K)の寿司から入れ替える
        for (int i = K; i < N; ++i)
        {
            //ネタの中で「おいしさポイント」が一番高くない寿司はスキップ
            if (list[i][0] == 0) continue;
            //入れ替える寿司がなくなったら、入替は終了
            if (stack.Count() < 1) break;
            //選んだネタの数を一つ増やす
            selectedNeta += list[i][0];
            //「おいしさポイント」を入れ替える
            selectedOishisa = selectedOishisa + list[i][1] - stack.Pop();
            //入れ替えた寿司の「満足ポイント」を算出
            var temp = selectedOishisa + selectedNeta * selectedNeta;
            //現時点での最高点を更新
            ans = temp < ans ? ans : temp;
        }
        Console.WriteLine(ans);
    }
}

メモ:Array.Sort(array,array)はタイムアウトしました。