研究室に行ったら後輩達の卒論を応援するためのビックマックが60個も置いてありました(僕も頂きました)、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/nikkei2019-qual)にて開催されました、全国統一プログラミング王決定戦予選の第三回目です。

今回は、第三問「C - Different Strokes」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

高橋くんと青木さんの前に N 皿の料理が置かれています。便宜上、これらの料理を料理 1 、料理 2 、…、料理 N と呼びます。

高橋くんが料理 i を食べると彼は A i ポイントの幸福度を得ます。また、青木さんが料理 i を食べると彼女は B i ポイントの幸福度を得ます。

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

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

2.入力例

入力

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

N
A_1 B_1
..
A_N B_N

出力

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

3.初見の感想

入力の分割とパースが必要
最も幸福度が高いものを求めるのでソートが必要
幸福度の有利さは自分と相手の幸福度の和で計算できる
高い順に選択するので逆ソートしたい
配列の和の求め方

4.実際解いた時の感想

２人の幸福度の和の順で高橋君の幸福度をソートしようとしたが、別配列の要素で配列のソートをする方法がわからなかった…

若干パニックになりましたね(汗)…

5.他の人のコードを読んだ学び

(ソートしたい配列をＣと表記しています)

逆順ソートの方法(使うと降順に並べられる)

Array.Reverse(C);

配列の条件付き加算

C.Where((value, index) => index % 2 == 0).Sum()

すごく勉強になりました…（本番この問題でめっちゃ悩んだ顔）

6.コード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program
    {
    static void Main(string[] args)
        {
        int N_length=int.Parse(System.Console.ReadLine());
        long[] A = new long[N_length];
        long[] B = new long[N_length];
        long[] C = new long[N_length];
        for (int j = 0; j < N_length; j++)
        {
            string[] input = System.Console.ReadLine().Split(' ');
            A[j] = long.Parse(input[0]);
            B[j] = long.Parse(input[1]);
            C[j] = A[j] + B[j];
        }
        Array.Sort(C);
        Array.Reverse(C);
        long ans = C.Where((value, index) => index % 2 == 0).Sum() - B.Sum();
        System.Console.WriteLine(ans);
    }
    }

7.最後に

今回は読みやすくするために入力例を省略してみました！

入力例などの詳しい問題はAtCoder(https://atcoder.jp/contests/nikkei2019-qual)に書かれております！

ツイッター見たら初回挑戦の人はみんなここで苦しんでるらしく安心した…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】全国統一プログラミング王決定戦予選③