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

前回競技プログラミングの問題を解いたという記事を書いたら、書いたことで一層記憶に残り、新しくTupleとかKeyValuePairとかいうデータ型を知ることができました。

今回はそれを使って、昔解けなかった問題を復習していきたいと思います。

Atcoder Beginner Contest 061 C

問題概要

最初にデータの数Nとほしい順番Kを与えます。

配列に入れる数字と個数のペアをN個与えるので、それらの数を配列に入れたあと、前からK番目の数字を出力してください。

最大で10^10個にもなる数列を作っていてはおしまいなので、そうしない方法を考えます。

結果思いついた方法は、読んだ配列情報をHashtable（連想配列）に格納し、最近勉強したKeyValuePair<int,long>に変換して解くというやり方です。

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;



namespace Atcoder

{

    class Program

    {

        static void Main(string[] args)

        {

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

            Hashtable h = new Hashtable();

            for (int i = 0; i < NK[0]; i++)

            {

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

                if (h.Contains(ab[0]))

                {

                    long temp = long.Parse((h[ab[0]].ToString()));

                    temp += ab[1];

                    h[ab[0]] = temp;

                }

                else

                {

                    h[ab[0]] = ab[1];

                }

            }

            KeyValuePair<int, long>[] pairs = new KeyValuePair<int, long>[h.Count];



            int counter = 0;

            foreach (int key in h.Keys)

            {

                pairs[counter] = new KeyValuePair<int, long>(key, long.Parse(h[key].ToString()));

                counter++;

            }

            pairs = pairs.OrderBy(x => x.Key).ToArray();

            ;

            long answercount = NK[1];

            for (int i = 0; i < pairs.Length; i++)

            {

                answercount -= pairs[i].Value;

                if (answercount <= 0)

                {

                    Console.WriteLine(pairs[i].Key);

                    break;

                }

            }



            ;

        }

    }

}

結果、謎のランタイムエラーが出て不正解となりました。

TLEだったら遅いとか、WAだったら考え方が間違っていたりどこかでオーバーフローが起こっていたりとかわかるんですが、REだけはどうも。

何を間違ってこうなっているのかわからず、修正しようもなく、過去の自分の回答を見たら、ほとんど同じことやってました。

しかも、同じテストケースで同じRE出してました。

解説を見ると、普通に配列でやってました。

「なぜ、配列を使わなかったか」

この疑問に対する答えなのですが、メモリ制限が怖かったと見えます。

今まで一度も引っかかったことないくせに。

longの配列だといくつぐらいの配列が作れるのかな、と思って計算して出てきた1600万が全く信じられず、試しにPractice Contestでどれぐらいのメモリ量を食うのかやってみたところ、1600万のlongの配列で130メガバイトほど消費していたので、これからはもっと貪欲にメモリを使っていってやろうと思います。

メモリ制限がメガバイトあれば、1メガバイトあたりlong 10万の配列が作れるぐらいだと覚えておくことにします。これからは視野に入れてやるからな。

…で、配列使って作ったこの問題の解法も、全く同じREを出したんですが。

RE嫌いだ！

ふぁんたすてぃっく

【競プロ】ランタイムエラー、手詰まりの問題、成長していない自分

Atcoder Beginner Contest 061 C