nim言語で競プロをしたときに、HashSetでメモリ超過(MLE)が起きる

初めに

• nimのversion: 1.6.14

• この問題がMLEしました: https://atcoder.jp/contests/abc277/tasks/abc277_c

• MLEした提出のページ: https://atcoder.jp/contests/abc277/submissions/47724145

nim言語を使ってatcoderで問題を解こうとしているときに、HashSetを使うとMLEが起きる状況に遭遇しました。

なぜMLEしたのか

• なぜ？: 初期化サイズが大きすぎた
  • initHashSet[int]()のように引数0個での呼び出しを行った際、要素64個分のメモリを確保してしまう。
    • 実装がそうなっているため
      • initHashSetのマニュアルページ: https://nim-lang.org/docs/sets.html#initHashSet
      • ソースコードにおいて64個と指定している行: https://github.com/nim-lang/Nim/blob/v1.6.14/lib/pure/collections/sets.nim#L84

解決法

• 引数なしでの呼び出しを定義しなおしておく

proc initHashSet[T](): Hashset[T] = initHashSet[T](0)

• これをinitHashSetの呼び出しより上に書いておくことで、引数なしで呼び出した際における初期化のサイズを0にする

  • (スマートな他の方法があるかも)
  • (0でなくてもいいかも)

• 解決した提出のページ: https://atcoder.jp/contests/abc277/submissions/47770081

おわりに

まさかデフォルトで64個にされるとは思いませんでした。 これうれしい瞬間あるんですか？

誤字脱字や内容の間違い、質問などがあればコメントをください。