こんにちは。ふぁんたです。

AtcoderBeginnerContest 127に出ていました。



その中に、こんな問題が出ました。

https://atcoder.jp/contests/abc127/tasks/abc127_d

概要

数字の書いてあるカードで遊ぶ。

最初にカードがN枚配られる。

その後、L枚のカードをRに書き直して良い、というチャンスがMセット与えられる。

操作によって総和を最大にし、総和を出力せよ。

考え方

L枚のカードをRに書き直す、じゃなくて、Rと書いたL枚のカードを山札に加える、と読み替える。

総和を最大にするには、その中の数字が大きい方からN枚取る。

書いた

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

public class ABC

{

    public static void Main()

    {

        int[] ab = Console.ReadLine().Split().Select(int.Parse).ToArray();

        int N = ab[0];

        int M = ab[1];

        Hashtable cards = new Hashtable();

        long[] A = Console.ReadLine().Split().Select(long.Parse).ToArray();

        List<long> keys = new List<long>();

        for (int i = 0; i < N; i++)

        {

            add(ref cards, A[i], 1);

            if (!keys.Contains(A[i]))

            {

                keys.Add(A[i]);

            }

        }

        for (int i = 0; i < M; i++)

        {

            long[] BC = Console.ReadLine().Split().Select(long.Parse).ToArray();



            add(ref cards, BC[1], BC[0]);

            if (!keys.Contains(BC[1]))

            {

                keys.Add(BC[1]);

            }

        }

        keys.Sort();

        keys.Reverse();

        long added = 0;

        long sum = 0;

        int counter = 0;

        while (added != N)

        {

            //cards[looking]は、lookingが書かれたカードの枚数

            //card は カードに書かれた整数

            long card = keys[counter];

            long quantity = (long)cards[card];

            if (added + quantity < N)

            {

                if (card != 1)

                {

                    added += quantity;

                    sum += quantity * card;

                }

                else

                {

                    added++;

                    sum += quantity;

                }

            }

            else if (added + quantity == N)

            {

                added += quantity;

                sum += quantity * card;

                break;

            }

            else

            {

                long this_quantity = N - added;

                sum += this_quantity * card;

                break;

            }

            counter++;

        }

        Console.WriteLine(sum);

    }





    public static void add(ref Hashtable cards, long B, long C)

    {

        if (cards.ContainsKey(B))

        {

            cards[B] = long.Parse(cards[B].ToString()) + C;

        }

        else

        {

            cards[B] = C;

        }



    }





}

結果

TLE(実行制限時間オーバー)

結果を受けて

…昔、こんな問題やらなかったっけ？

たくさんある候補を効率が良い順番にソートして、満足するまで上から入手していく…



！！



/posts/2019/03/11/abc121c/

この問題だ！！！！

同じようなコードをC++で書き直す

#include<iostream>

#include<string>

#include<algorithm>

#include<vector>

#include<map>

#include<queue>

#include<list>

using namespace std;





int main()

{

\tint N, M;

\tcin >> N >> M;

\tvector<pair<int, int>> cards(N + M);

\tfor (int i = 0; i < N; i++)

\t{

\t\tint temp = 0;

\t\tcin >> temp;

\t\tcards[i] = make_pair(temp, 1);

\t}

\tfor (int i = N; i < M + N; i++)

\t{

\t\tint a, b;

\t\tcin >> a >> b;

\t\tcards[i] = make_pair(b, a);

\t}

\tsort(cards.begin(), cards.end());

\treverse(cards.begin(), cards.end());

\tN = N;

\tlong long added = 0;

\tlong long sum = 0;

\tint counter = 0;

\twhile (added != N)

\t{

\t\t//cards[looking]は、lookingが書かれたカードの枚数

\t\t//card は カードに書かれた整数

\t\tlong long card = cards[counter].first;

\t\tlong long quantity = cards[counter].second;

\t\tif (added + quantity < N)

\t\t{

\t\t\tif (quantity != 1)

\t\t\t{

\t\t\t\tadded += quantity;

\t\t\t\tsum += quantity * card;

\t\t\t}

\t\t\telse

\t\t\t{

\t\t\t\tadded++;

\t\t\t\tsum += card;

\t\t\t}

\t\t}

\t\telse if (added + quantity == N)

\t\t{

\t\t\tadded += quantity;

\t\t\tsum += quantity * card;

\t\t\tbreak;

\t\t}

\t\telse

\t\t{

\t\t\tlong this_quantity = N - added;

\t\t\tsum += this_quantity * card;

\t\t\tbreak;

\t\t}

\t\tcounter++;

\t}

\tcout << sum << endl;

}

while文の中身は思いっきりコピペです。

結果

AC

この結果を受けて

昔、手も足も出ずにやられた（負けイベント）相手に、経験値を積んで再び戦いを挑むみたいなイベントでめっちゃくちゃ興奮しました。





でも、C#だと2秒超えでTLE食らうのに、C++だと0.2秒もかかってない、みたいな結果が出力されて。

困ったらC++を使うようにしようと思いました。TLEが来たらC++。

---

追記

Hashtableに値を突っ込むところが大きなボトルネックとなっていました。

手元の環境で動かして、そこだけでおよそ2000ms。TLEです。



データ構造による処理速度をきちんと把握しないといけないですね。