Go to Qiita Advent Calendar 2024 Top
LoginSignup
50
33

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@ishowta

Nimで競プロをするための基本的な機能

Last updated at Posted at 2017-12-03

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

Nimとは

　NimはC#のように手動でのメモリ制御が可能1な静的型付け言語です。Rubyのような自由度と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


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

# 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に入る

他にもパラメーターの制約を指定できるConceptや、ASTを直接操作できるmacroという機能などがあり、どれも強力ですが少し複雑な上に競プロで使うことは少なそうなので今回は省略します。

入力

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]]

ソート

intやstringであれば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

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

50
33
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
50
33

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?