競技プログラミング
Nim

競技プログラミングのためのNim

この記事はSPC同好会 Advent Calendar 2017の3日目の記事です。

Nimとは

 Nimは手動でのメモリ制御が可能1で、C/C++と同等の速度を持っているマルチパラダイム言語です。pythonに近い文法を持っていて、効率的で表現力が高い言語を目指して作られています。システムも開発できると謳っていて、最適化のための様々な機能が用意されていたりします。

 pythonと似た見た目ですが、哲学は良くも悪くも自由な文法が認められているので、頭の中にあるものをそのまま、書きたいように書けます。大規模開発に向いているかはともかく、競プロに合っていると思いませんか?ここから、Nimの機能を競プロで使いそうな機能に絞って紹介します。

 なお、標準ライブラリは公式のドキュメントに載ってます。関数ごとにGithubのソースコードへのリンクが貼ってあって簡単に中身を確認できます

基本構文

# import(bits/stdc++.hにあたるものは無いです。ここに書いてあるもので殆どの場合事足りると思います。)
import system, macros, algorithm, tables, sets, lists, queues, intsets, critbits, sequtils, strutils, math, future

# 変数宣言
var a :int32 = 1'i32

# (省略)
var a = 1

# 定数
let a = 1

# コンパイル時定数
const a = 1

# if
if a == 1:
  echo "One"
elif a == 2:
  echo "Two"
else:
  echo "Otherwise"

# for
for i in 0..<vec.len:
  echo i

# range based for
for a in vec:
  echo a

# enumerate
for i,a in vec:
  echo i," : ",a

# 配列
var
    a = [1,2,3,4,5] # array
    v = @[1,2,3,4,5] # seqence(C++で言うvectorです)
var
    v1 = v[0..1] # Slice -> @[1,2]
    v2 = lc[x | (x <- v, x mod 2 == 0), int] # -> @[2,4] (リスト内包表記です)

# タプル
var
    t = (0,0,0)
    point = (x:0,y:0,z:0) # 名前がつけられます
    people = (name:"Alice", age:12)
    (x,y,_) = point # 分けて受け取れます

### 関数 ###

# 関数定義
#    関数名 引数 返り値型
proc add(a,b:int):int = a + b

proc add2(a,b:int):int = # returnで返る
    return a + b
proc add3(a,b:int):int = # resultに入れるとその値が返る
    result = a + b
proc add4(a,b:int):int = # 最後に評価された式が返る
    a + b

# Generic param(第一級オブジェクトではない)
proc add5(a,b:auto):auto = a + b
#     (数字でないなら、(=not SomeNumber),文字列に変換して(=$),結合する(=&))
proc add(a,b:not SomeNumber):string = $a & $b
#echo add(3,4) # -> 7
#echo add("a","b") # -> ab

# C++でいう関数テンプレート
proc add6[T](a,b:T):T = a + b

# C++でいうテンプレート特殊化
proc f[T](a,b:T):auto =
    when T is int:
        result = "int"
    when T is string:
        result = 765
echo f(1,2) # -> int
echo f("a","b") # -> 765

# コンセプト
type IsIntMatrix = concept m
    for v in m:
        for x in v:
            x is int
proc g[T:IsIntMatrix or int](x:T):int =
    when T is IsIntMatrix:
        result = len(x)
    when T is int:
        result = x
echo g(@[@[1,2,3],@[4,5,6],@[7,8,9]]) # -> 3


### テンプレート ###
# 構文を維持したままのマクロ,,,みたいな感じ…?テンプレートを呼んだ場所がテンプレートの中身に入れ替わります。

# repの実装例
#     untypedは定義されて無い変数を受け取れます。(cnt)
#     インデントで分けられた文をそのまま受け取れます(act)
template rep(cnt:untyped, size:SomeOrdinal, act:untyped):untyped =
    for cnt in 0..<size:
        act
# var
#    n = 3
#    v = @[1,2,3]
#
# rep(i,n):
#     echo v[i] # この文がactに入る

templateの他に,macroという機能があり,ASTを直接操作できる、とても強力で自由度が高いマクロです。便利ですが少し複雑な上に競プロで使うことは無さそうなので今回は省略します

入力

stdin.readLineで標準入力から一行づつ取り出せます。

var
    n = stdin.readLine.parseInt
    v = stdin.readLine.split.map(parseInt)
    f = (0..<n).mapIt(stdin.readLine.split.map(parseInt))

echo n
echo v
echo f

# input
# 3
# 1 2 3 4 5
# 1 2 3 4
# 5 6 7 8
# 9 10 11 12
#
# output
# 3
# @[1, 2, 3, 4, 5]
# @[@[1, 2, 3, 4], @[5, 6, 7, 8], @[9, 10, 11, 12]]

ソート

intstringであればcmpで比較してくれます。

var s = @[3,5,1,2,4]

echo s.sorted(cmp)
echo s.sorted(cmp, Descending)
echo s.sorted((a,b) => (if a < b: -1 elif a > b: 1 else: 0))
#↑と同じ
# echo s.sorted(
#     proc(a,b:auto):auto =
#         if a < b: -1
#         elif a > b: 1
#         else: 0
# )

#
# output
# @[1, 2, 3, 4, 5]
# @[5, 4, 3, 2, 1]
# @[1, 2, 3, 4, 5]

高階関数

var v = @[1,2,3,4,5]
echo v
echo v.filter(x => x<4)
echo v.filter(x => x<4).map(x => x^2)
echo v.filter(x => x<4).map(x => x^2).foldr(a+b)
echo v.filterIt(it<4).mapIt(it^2).foldr(a+b)
echo sum lc[x^2 | (x <- v, x < 4 ) , int]   # リスト内包表記


# output
# @[1, 2, 3, 4, 5]
# @[1, 2, 3]
# @[1, 4, 9]
# 14
# 14
# 14

公式のドキュメントに色々な関数が載ってます。

順列生成

var v = @[1,2,3]
while true:
    echo v
    if v.nextPermutation() == false:
        break

# output
# @[1, 2, 3]
# @[1, 3, 2]
# @[2, 1, 3]
# @[2, 3, 1]
# @[3, 1, 2]
# @[3, 2, 1]

検索

var v = @[1,2,4,5,7,9]

echo v.binarySearch(4)
echo v.lowerBound(6)

# output
# 2
# 4

Queue

const Q_SIZE = 10_000
var q = initQueue[int](Q_SIZE)
q.add(1)                    # 追加 O(1)
q.add(2)
q.add(3)
dump q
dump q[0]                   # ランダムアクセス O(1)
dump q.front                # 先頭を見る O(1)
dump q.back                 # 後尾を見る O(1)
dump q.contains(0)          # 検索 O(n)
dump q.pop()                # 取り出す O(1)
dump q

# q = [1, 2, 3]
# q[0] = 1
# front(q) = 1
# back(q) = 3
# contains(q, 0) = false
# pop(q) = 1
# q = [2, 3]

Set

const S_SIZE = 1024
var s = initSet[int](S_SIZE)# 2^n
s.incl(1)                   # 追加 O(1)
s.incl(toSet([0,1,2,3,4]))
dump s
dump s.contains(3)          # 検索 O(1)
s.excl(3)                   # 取り出す O(1)
dump s

# s = {1, 2, 3, 4, 0}
# contains(s, 3) = true
# s = {1, 2, 4, 0}

List

var l = initDoublyLinkedList[int]()
l.append(1)                 # 前に追加 O(1)
l.append(3)
l.append(5)
l.prepend(7)                # 後ろに追加 O(1)
dump l
var node = l.find(5)        # 検索 O(n)
l.remove(node)              # 取り出す O(1)
dump l
for i in l.items():
    echo i

# l = [7, 1, 3, 5]
# l = [7, 1, 3]
# 7
# 1
# 3

ちなみにNimでl(エル)を変数名にすると,変数を使うごとに見づらいよ!ってWarningが飛んできます。か,かわいい…


  1. ただ、デフォルトはGCありなので、言語設計上どうしてもGCを優先した設計になることがある