競プロ で Nim を使う際のまとめ

Nimめっちゃ大好きなのでまとめました.
AtCoderでNim使ってる人,全然いないのでもっと広まってくれ〜.
[私のNimの競プロライブラリはこちらです](https://github.com/Muratam/yukicoder-nim)

# 競プロ で Nim を使う利点
Nimは(C++並みの)速さと書きやすさを備えた最強の言語で競プロ向きです.

1. 速いので安心. 富豪的な書き方をしても間に合う.
1. 静的型付け. 知ってますか,Compile Error は Runtime Error ではないのでペナルティはありません.
1. 変数を dump しやすい. `std::vector` を `cout` するのはダルいが,Nimなら `echo @[1,2,3]` が動く.
1. 即時 named tuple が作れる. `let a = (x:100,y:100)` みたいな.
1. 実行時に落ちても落ちた場所を教えてくれる. C++だと `segmentation fault` とか出てつらいよね.
1. メソッドチェーン！ `newSeqWith(n,(x:scan(),y:scan())).sortedByIt(it.y).mapIt(it.x*it.x+it.y*it.y)` (ベクトル(x,y)を取得してyの順にソートして絶対値に変える例)
1. `lowerBound` とか `nextPermutation` とか競プロ的に欲しい関数がちゃんとある.(例:D言語にはindexを取れるlowerBoundが無い)
1. 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 は古いので自分でビルドする必要がある可能性がある](https://qiita.com/sessions/items/561f8a3aa6eba6d4d7a9).
  - ビルドを終えたらディレクトリ一式を `~/.choosenim/toolchains/nim-0.13.0/` に入れると使えるようになる.

## 2. AtCoder の Nim0.13.0 でのみ気をつけるべきこと
以下は 最新のNim(>=0.20.0) では修正されている.

- `toSeq(0..<10)` とは書けない.
  - o : `toSeq(0..10-1)`
- `sequtils.deduplicate` は O(N^2) かかる.
  - o : [ソートして自分で deduplicate. ](./lib/seq/sequence.nim)
- `random` (疑似乱数)モジュールが無い.
  - o : [自分で書く](./lib/mathlib/random.nim)
- `heapqueue`(優先度付きキュー) モジュールが無い.
  - o : [自分で書く](./lib/datastructure/set/priorityqueue.nim)


## 3. その他たまに困ること
- `sequtils.newSeqWith` は便利だが配列のコピーが余分に発生する.
  - およそ1e6以上の個数を扱うなら `newSeq` して代入の方が安心.
- C++のSTLとの連携は可能だがサポートやドキュメントが不足しがち.
- `intsets` 使うのはかなり難しい(`seq[bool]` か `HashSet[int]` か別のデータ構造を使うと思う).

# 個人的 Nim 競プロ用テンプレート
```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]`
- また,何も 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`
- また,以下の関数を定義しています
  - `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 にでも書いておくと幸せになれます.

```bash
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`