競プロ向けNim記述

入門用メモ。

散発的になりそう。

import

Nim Standard Library

競プロで使いそうなモジュール

module名	主な機能	公式Doc
strutils	文字列全般: 各種parse, split, join, 検索, format etc.	Module strutils
sequtils	map, zip, filter, fold etc.	Module sequtils
math	三角関数, gcd, lcm, pow, sqrt, binom, factorial etc.	Module math
algorithm	sort, reverse, 二分探索(lowerBound, upperBound), 順列イテレータ	Module algorithm
tables	ハッシュマップ(Table, OrderedTable, CountTable)	Module tables
sets	集合(HashSet, OrderedSet)	Module sets
lists	単方向リスト, 双方向リスト	Module lists
queues	キュー	Module queues
intsets	ビットセット	Module intsets
critbits	crit-bit木(効率のよい文字列検索木)	Module critbits
future	実験的な機能(リスト内包表記 etc.)	Module future

まとめて

import strutils, sequtils, math, algorithm, tables, sets, lists, queues, intsets, critbits, future

入力

let
    # 文字列
    s = stdin.readLine
    
    # 単一数値
    n = stdin.readLine.parseInt
    
    # 数列
    a = stdin.readLine.split.map(parseInt)
    
    # n行にわたる単一数値
    b = (0..<n).mapIt(stdin.readLine.parseInt)
    
    # n行にわたる数列
    f = (0..<n).mapIt(stdin.readLine.split.map(parseInt))

Nimでは 何か.関数(A, B) という記述で 関数(何か, A, B) が呼ばれるので、関数の入れ子を極力避ける書き方ができる。

# 複数の数値の分割代入
var
    a, b, c: int
(a, b, c) = stdin.readLine.split.map(parseInt)

分割代入（Destructuring assignment）は、直接行うにはこうするしかない？

関数を定義しておけば、letでも受け取れる（参考: somq14様）

proc readSeq(): seq[string] =
    stdin.readLine.split

proc readInt1(): int =
    stdin.readLine.parseInt
proc readInt2(): (int, int) =
    let a = readSeq().map(parseInt)
    return (a[0], a[1])
proc readInt3(): (int, int, int) =
    let a = readSeq().map(parseInt)
    return (a[0], a[1], a[2])
proc readInt4(): (int, int, int, int) =
    let a = readSeq().map(parseInt)
    return (a[0], a[1], a[2], a[3])

let
    (a, b, c) = readInt3()
echo a, b, c

出力

# 単一数値
echo n

# 配列スペース区切り('$'で文字列に出来る型なら可)
echo a.join(" ")

# 配列スペース区切り(ver.0.13)(明示的に文字列に変換の必要あり)
echo a.map(proc (x: int): string = $x).join(" ")

# 複数数値スペース区切り
echo n, " ", m, " ", k
# または
echo "$1 $2 $3" % [$n, $m, $k]

リストの作成

arrayが固定長配列（コンパイル時に長さがわかっている必要がある）、seqが可変長リスト

# 空の1次元Seq
var aaa: seq[int] = @[]  # 型の自動推定が働かないため明言する必要がある
# または
var aaa = newSeq[int]()

# N要素の1次元Seq(その型のデフォルト値で初期化)
var aaa = newSeq[int](N)

# N要素の1次元Seq(その型のデフォルト値以外で初期化)
var aaa = newSeq[int](N)
aaa.fill(x)

# N行M列の2次元Seq
var aaa = newSeq[seq[int]](N)
aaa.fill(newSeq[int](M))
# または
var aaa = newSeqWith(N, newSeq[int](M))

配列の値埋めについては、newSeqWithより、fillした方が速いらしい。これは、randなどが渡されたとき、fillだと引数として渡す際に評価された1つの値が全て入ってしまうが、newSeqWithは毎回initして別々の要素を作成するなどの挙動の違いにより、1要素の生成コストがfillの方が小さいため。

newSeqWith is 3 times slower than fill · Issue #7295 · nim-lang/Nim

import sequtils, algorithm, random

var aaa = newSeq[int](10)
aaa.fill(rand(100))
echo $aaa
# => @[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

var bbb = newSeqWith(10, rand(100))
echo $bbb
# => @[89, 18, 2, 95, 20, 9, 54, 37, 80, 51]


# 2次元配列の作成などは、fillでも独立した要素が作られる模様
# （参照が同じでccc[0][0]を変更したらccc[1][0], ccc[2][0]も変更されてしまう、ということはない）

var ccc = newSeq[seq[int]](3)
ccc.fill(newSeq[int](3))
ccc[0][0] = 5
echo $ccc
# => @[@[5, 0, 0], @[0, 0, 0], @[0, 0, 0]]

var ddd = newSeqWith(3, newSeq[int](3))
ddd[0][0] = 5
echo $ddd
# => @[@[5, 0, 0], @[0, 0, 0], @[0, 0, 0]]

要素数の数え上げ

Pythonのitertools.Counterみたいな。

[1, 2, 3, 2, 3, 3, 3]
↓
{1: 1,  2: 2,  3: 4}

CountTableが使える。

import tables

let
    a = @[1, 2, 3, 2, 3, 3, 3]
    b = a.toCountTable
echo b

# {1: 1,  2: 2,  3: 4}

注意点1

AtCoderのver.0.13では、toCountTable() が要素を数え上げない（存在する要素のkeyは作られるが、全てのカウントが1になる）

最近のver.では修正済み

[1, 2, 3, 2, 3, 3, 3]
↓
{1: 1,  2: 1,  3: 1}

仕方ないので、イテレートしてinc(key)でそのキーのカウントを1増やしていく。（Pythonの defaultdict(int) みたいな使い方ができる）

let a = @[1, 2, 3, 2, 3, 3, 3]
var b = initCountTable[int]()
for v in a:
    b.inc(v)

注意点2

要素を多い順に並べ替えるsort()があるが、要素数が増えると妙に遅い。（シェルソートしてるらしいんだけど……）

ソートは自前実装した方がよい。

最も多い物が欲しいだけなら、largest()が使える。

version

現状のAtCoderのバージョン0.13では、正直コンテスト本番に使うのは難しい感触。（記述時の最新は0.19.0）

上記CountTableのようなバグが潜んでいたり、下記のようにうっかりミスしやすい処理の優先順位となっていたりする。

let n = 10
echo (n - 1) * 100

# このコードがコンパイルエラーになる

# Error: type mismatch: got (empty, int literal(100))
# but expected one of: 
# system.*(x: T, y: T)
# system.*(x: int16, y: int16)
# ...

# echo も関数なのでカッコが「echo(n - 1)」と先に評価されている
# 0.19では解消され、通る
# 0.13では明示的にカッコでくくってあげる必要がある

let n = 10
echo((n - 1) * 100)

目次