Nimめっちゃ大好きなのでまとめました.
AtCoderでNim使ってる人,全然いないのでもっと広まってくれ〜.
私のNimの競プロライブラリはこちらです
競プロ で Nim を使う利点
Nimは(C++並みの)速さと書きやすさを備えた最強の言語で競プロ向きです.
- 速いので安心. 富豪的な書き方をしても間に合う.
- 静的型付け. 知ってますか,Compile Error は Runtime Error ではないのでペナルティはありません.
- 変数を dump しやすい.
std::vectorをcoutするのはダルいが,Nimならecho @[1,2,3]が動く. - 即時 named tuple が作れる.
let a = (x:100,y:100)みたいな. - 実行時に落ちても落ちた場所を教えてくれる. C++だと
segmentation faultとか出てつらいよね. - メソッドチェーン！
newSeqWith(n,(x:scan(),y:scan())).sortedByIt(it.y).mapIt(it.x*it.x+it.y*it.y)(ベクトル(x,y)を取得してyの順にソートして絶対値に変える例) -
lowerBoundとかnextPermutationとか競プロ的に欲しい関数がちゃんとある.(例:D言語にはindexを取れるlowerBoundが無い) - C++で言う
const autoがletで書ける. 不変性が簡潔に書けて便利.
競プロ で Nim を書く時に気をつけるべきこと
Nimは最強の言語ですが、罠が無いわけではありません.
1. コンテストとローカルのNimのバージョンを合わせる
- Nimは互換性を気にしないタイプの言語なので,思わぬバグが発生しがち。
- 慣れないと毎コンテストで(バージョンに起因する)バグを踏むことが普通に起こるので必ず合わせるべき.
- 2019/10/8 時点で AtCoder:0.13.0 / YukiCoder:0.20.99
- Nimのバージョン変更自体は
choosenimコマンドで簡単にできる。- (MaxOSX では)Nim 0.13.0 は古いので自分でビルドする必要がある可能性がある.
- ビルドを終えたらディレクトリ一式を
~/.choosenim/toolchains/nim-0.13.0/に入れると使えるようになる.
2. AtCoder の Nim0.13.0 でのみ気をつけるべきこと
以下は 最新のNim(>=0.20.0) では修正されている.
-
toSeq(0..<10)とは書けない.- o :
toSeq(0..10-1)
- o :
-
sequtils.deduplicateは O(N^2) かかる. -
random(疑似乱数)モジュールが無い.- o : 自分で書く
-
heapqueue(優先度付きキュー) モジュールが無い.- o : 自分で書く
3. その他たまに困ること
-
sequtils.newSeqWithは便利だが配列のコピーが余分に発生する.- およそ1e6以上の個数を扱うなら
newSeqして代入の方が安心.
- およそ1e6以上の個数を扱うなら
- C++のSTLとの連携は可能だがサポートやドキュメントが不足しがち.
-
intsets使うのはかなり難しい(seq[bool]かHashSet[int]か別のデータ構造を使うと思う).
個人的 Nim 競プロ用テンプレート
# {.checks:off.}
import sequtils,algorithm,math,tables,sets,strutils,times
template stopwatch(body) = (let t1 = cpuTime();body;stderr.writeLine "TIME:",(cpuTime() - t1) * 1000,"ms")
template loop(n:int,body) = (for _ in 0..<n: body)
template `max=`(x,y) = x = max(x,y)
template `min=`(x,y) = x = min(x,y)
proc getchar():char {. importc:"getchar_unlocked",header: "<stdio.h>" ,discardable.}
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
#
let n = scan()
let A = newSeqWith(n,scan())
- import : 競プロでよく使うのはこの7つ. 特に以下は頻出.
- sequtils :
newSeqWith,toSeq,.mapIt - algorithm:
sorted(cmp),sortedByIt,lowerBound,reversed,nextPermutation - math :
n.float.sqrt.int,gcd,lcm - tables,sets:
Table[K,V],HashSet[K]
- sequtils :
- また,何も import しなくても以下の便利機能が使える(systemモジュール)
- seq:
newSeq[T](n),.len,.add,&,x[a..b],.pop,in,@[1,2] - iterator :
a..b,a..<b,(n-1).countdown(0) - 型変換 :
.int,.ord,.chr,$,cast[T](x) - ほか :
max,min,abs,cmp,1e12.int,quit
- seq:
- また,以下の関数を定義しています
-
stopwatch: ...で時間を計測できる.結果は標準エラー出力に流れるのでそのまま提出してもAC可能.スコープも変わらないので元のコードから単純にインデントを深くするだけでよい. -
n.loop: ...で n回ループを回せる.forループに比べてループ変数が増えないため,i番目であるという情報が不要ということが把握しやすい. -
.max=,.min=:dp[i][k] = max(dp[i][k],dp[i][j])が,dp[i][k] .max= dp[i][j]として書ける. 必須. -
getchar: 一文字だけ入力を進めたいとき. グリッド上の探索系の問題とか -
scanfとscan: intを一つ入力から取る. 例えば配列の入力を受け取る際に普通に書くとstdin.readLine.split().map(parseInt)かnewSeqWith(n,stdin.readLine.parseInt)のように書かなければいけないのが, どちらもnewSeqWith(n,scan())と書けて便利.- 例えば三次元の入力でも
newSeqWith(n,(x:scan(),y:scan(),z:scan()))と臨機応変に書けてお得.
- 例えば三次元の入力でも
-
Nimの実行スクリプト
nim c -r hoge.nim でもいいですが,以下を .bashrc にでも書いておくと幸せになれます.
nimcompile() { nim cpp --hints:off --verbosity:0 $@ ; }
nimr() { # 実行後に邪魔な実行可能ファイルを消してくれる
exename="$(echo $1 | sed 's/\.[^\.]*$//')"
nimcompile $NIMR_COMPILE_FLAG -r $@
[[ -f $exename ]] && rm $exename
}
nimrr() { NIMR_COMPILE_FLAG="-d:release" nimr $@ ; }
- 普通に即実行(落ちるとスタックトレースを表示してくれる) :
nimr hoge.nim - デバッグ情報を消して最適化して実行 :
nimrr hoge.nim