はじめに

競技プログラミング、全国統一プログラミング王決定戦予選
 C - Different Strokes
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

高橋くんと青木さんの前にN皿の料理が置かれています。
便宜上、これらの料理を料理1、料理2、…、料理Nと呼びます。
高橋くんが料理iを食べると彼はAiポイントの 幸福度を得ます。
また、青木さんが料理iを食べると彼女はBiポイントの幸福度を得ます。

彼らは、高橋くんから始めて交互に、料理を1皿ずつ選んで食べることを料理が尽きるまで続けます。
ただし、彼らはともに、
「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を
引いた値を最大化するように料理を選びます。

このとき、「最終的に高橋くんが得る幸福度の総和」から
「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？

制約

・1≤N≤10^5
・1≤Ai≤10^9
・1≤Bi≤10^9
入力される値はすべて整数である。

入力

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

N
A1 B1
:
AN BN

出力

「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値を出力せよ。

解き方

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

高橋さんと青木さんは順番に料理を
「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を
引いた値を最大化するように料理を選びます。

まず高橋さんだけの場合を考えます。
料理を仮に以下の二つだとします。

A B
C D

このとき、Aを選ぶとすると
「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を
引いた値を最大化するように料理を選ぶので
以下の式が成り立っていることになります。

A-D>C-B

この式を変形すると以下のようになります。

A-D>C-B
A+B>C+D

つまり、
「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を
引いた値を最大化するように選ぶとすると
各料理に対して
高橋さんと青木さんが得られる幸福度の和が高いものからとることになります。

そして、この行動は高橋さんだけでなく青木さんも同じように考えて動くので
両者の選びたい料理は常に同じとなります。

よって、
高いものから順番に高橋さんと青木さんに料理を割り振り
最後にポイントの差を出せば答えが出ます。

証明については以下の記事が分かり易いです。
qiita.com

コード

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

class Cmondai
{
    static void Main()
    {
        var count = Int32.Parse(Console.ReadLine());
        //各料理の両者の幸福度の和、高橋さんの幸福度、青木さんの幸福度を保存
        var list = new List<long[]>();
        for (int i = 0; i < count; ++i)
        {
            var line = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
            list.Add(new long[3] { line[0] + line[1], line[0], line[1] });
        }
        //各料理の両者の幸福度の和が大きい順に並び替え
        list = list.OrderByDescending(x => x[0]).ToList();
        //高橋さんの幸福度の和
        var takahashi = 0L;
        //青木さんの幸福度の和
        var aoki = 0L;
        //料理を順番に取っていった際の幸福度を割り振る
        for (int i = 0; i < count; ++i)
        {
            if (i % 2 == 0) takahashi += list[i][1];
            else aoki += list[i][2];
        }
        //差を出す
        Console.WriteLine(takahashi - aoki);
    }
}