【競プロ】ランタイムエラー、手詰まりの問題、成長していない自分
スポンサードリンク
こんにちは。ふぁんたです。
前回競技プログラミングの問題を解いたという記事を書いたら、書いたことで一層記憶に残り、新しくTupleとかKeyValuePairとかいうデータ型を知ることができました。
今回はそれを使って、昔解けなかった問題を復習していきたいと思います。
Atcoder Beginner Contest 061 C
問題概要
最初にデータの数Nとほしい順番Kを与えます。
配列に入れる数字と個数のペアをN個与えるので、それらの数を配列に入れたあと、前からK番目の数字を出力してください。
最大で10^10個にもなる数列を作っていてはおしまいなので、そうしない方法を考えます。
結果思いついた方法は、読んだ配列情報をHashtable（連想配列）に格納し、最近勉強したKeyValuePair<int,long>に変換して解くというやり方です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
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嫌いだ！
スポンサードリンク