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)はタイムアウトしました。