I love:
- 👑 Nim 👑
-
$\lambda$ Haskell$\lambda$
- git-hs: A toy git implementetaion written in Haskell
- Matsuri: Useful Variant Types and Powerful Pattern Matching for Nim
- My library for competitive programming
- nim-curry: Easy currying library for Nim
ACL (AtCoder Library) implementation in Nim
License: Creative Commons Zero v1.0 Universal
I love:
ac-library-nim/src/atcoder/extra/graph/dijkstra.nim(33, 28) Error: undeclared field: 'inf'
import sequtils,strutils,sugar
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld",addr result)
proc nextFloat(): float = scanf("%lf",addr result)
import atcoder/extra/graph/graph_template
import atcoder/extra/graph/dijkstra
template times(n: int, body: untyped) =
for _ in 0..<n:
body
proc `$` [T](x: seq[T]): string = x.mapIt($it).join(" ")
proc `ceilDiv`[T: SomeInteger](x, y: T): T = x div y + ord(x mod y != 0)
proc main():void =
let N, Q = nextInt()
var g = initGraph[int](N)
(N - 1).times:
let a, b = nextInt() - 1
g.addBiEdge(a, b)
let dist = dijkstra[int](g, 0)[0]
main()
dijkstra.nimの中でatcoder/extra/other/inf
がimportされていない
when not declared ATCODER_EXTRA_DIJKSTRA_HPP:
const ATCODER_EXTRA_DIJKSTRA_HPP* = 1
import std/heapqueue, std/sequtils, std/algorithm
import std/deques
import atcoder/extra/graph/graph_template
+ import atcoder/extra/other/inf
proc dijkstra01*[T](g:Graph[T], s:int): (seq[T],seq[int]) =
var
n = g.len
dist = newSeqWith(n,T.inf)
prev = newSeqWith(n,-1)
Q = initDeque[Edge[T]]()
dist[s] = T(0)
Q.addFirst(initEdge[T](-2,s,T(0)))
while Q.len > 0:
var e = Q.popFirst()
if prev[e.dst] != -1: continue
prev[e.dst] = e.src;
for f in g[e.dst]:
var w = e.weight + f.weight;
if dist[f.dst] > w:
dist[f.dst] = w;
if f.weight == 0:
Q.addFirst(initEdge[T](f.src, f.dst, w))
else:
Q.addLast(initEdge[T](f.src, f.dst, w))
return (dist,prev)
proc dijkstra*[T](g:Graph[T], s:int): (seq[T],seq[int]) =
var
n = g.len
dist = newSeqWith(n,T.inf)
prev = newSeqWith(n,-1)
Q = initHeapQueue[Edge[T]]()
dist[s] = T(0)
Q.push(initEdge[T](-2,s,T(0)))
while Q.len > 0:
var e = Q.pop()
if prev[e.dst] != -1: continue
prev[e.dst] = e.src;
for f in g[e.dst]:
var w = e.weight + f.weight;
if dist[f.dst] > w:
dist[f.dst] = w;
Q.push(initEdge[T](f.src, f.dst, w))
discard
return (dist,prev)
proc path*(prev: seq[int], t:int): seq[int] =
var u = t
while u >= 0:
result.add(u)
u = prev[u]
result.reverse()
# }}}
おそらく、こんなことを気にしているのは拙者くらいであろうが、nimにおいてobjectのstaticメンバー関数をどう定義するかで悩んでいました。ac-libraryのsegtreeのop, eあたりがC++のstaticメンバー関数で書かれていて合わせられると嬉しいです。現状
があって、1. で頑張っています。
import times, math
# ジェネリクスに無理やり入れる1
block:
let time = cpuTime()
type S[f:static[proc(a, b:int):int]] = object
discard
var s0:S[proc(a, b:int):int = a + b]
var s = 0
for _ in 0 ..< 10^9:
s += s0.f(3, 4)
echo s, " ", cpu_time() - time
# ジェネリクスに無理やり入れる2 (1.0.6ではコンパイルできないが1.6.14ではコンパイルできる模様)
block:
let time = cpuTime()
type S[T;f, g:static[auto]] = object
discard
var s0 = S[int, proc(a, b:int):int = a + b, proc(a, b:int):int = a * b]()
var s = 0
for _ in 0 ..< 10^9:
s += s0.f(3, 4)
echo s, " ", cpu_time() - time
# procで定義
block:
let time = cpuTime()
proc f(a, b:int):int = a + b
var s = 0
for _ in 0 ..< 10^9:
s += f(3, 4)
echo s, " ", cpu_time() - time
# メンバ変数で動的に定義
block:
let time = cpuTime()
type S = object
f:proc(a, b:int):int
var s0 = S(f:proc(a, b:int):int = a + b)
var s = 0
for _ in 0 ..< 10^9:
s += s0.f(3, 4)
echo s, " ", cpu_time() - time
Apple siliconだと動かない
Nim-ACL/src/atcoder/extra/math/modint_chaemon.nim
Lines 54 to 58 in 80bbcde
2023年1月から言語アップデートがあるようです。
バージョンが1.6.10にできます。
Nim-ACLもライブラリとして追加できるかもです。
その場合、expanderと競合するのを防ぐとかいろいろ考えないといけないかもです。
Nim1.6.14環境下で、extra/structure/set_mapをインポートすると、sequtilのtoSeqが上手く動かなくなるようです。
例えば下記のコードをAtCoderのコードテストに投げると再現可能です。
import sequtils
import atcoder/extra/structure/set_map
echo((0..10).toSeq)
ambiguous call; both iterators.items(s: Slice[items.T]) [iterator declared in C:\Users\una.choosenim\toolchains\nim-1.6.14\lib\system\iterators.nim(126, 10)] and set_map.items(s: Slice[items.Node]) [iterator declared in C:\Users\una.nimble\pkgs\atcoder-0.1.0\atcoder\extra\structure\binary_tree_node_utils.nim(72, 12)] match for: (HSlice[system.int, system.int])
コンパイル時にこのようなエラーが出ます。
toSeq以外でも、変数に入れたイテレータを順に見ていく系の処理全般で引っかかるようです。
let iter = (0..10)
for i in iter:
echo(i)
これでも同じことが起きます。
詳しい原因や解決方法はわからないのですが、最新版のNimで動かすと正常な出力が得られました。
なのでAtCoderの次の言語アップデートが来れば自動的に解決するかもしれないです。
現状ではexpanderはそのまま展開するので、ローカル変数に同名の変数やobjectが別のファイルにあるとエラーが起こるかと思います。したがって、ローカル変数のimportは全体に公開されないようにしたいと思っていました。つまり、expanderで書いたimportは事実上includeになっています。
前にzer0starさんがblockを使った方式を提案していただきましたが、expanderが関数名を全部把握しなくてはならない点や同名で引数だけが違う関数が使えないといった問題がありました。
これについていろいろ調べてみたところ、genSym, injectプラグマを利用してtemplateの形で展開すると良さそうだということがわかりました。現状、ローカル変数のバッティングがあまり起こらないので、expanderにわざわざその機能を入れる必要があるかというところではあります。
% ulimit -s 65000
% oj-verify run verify/extra/math/pow_of_formal_power_series_test.nim
(略)
[INFO] slowest: 0.780420 sec (for M_zero_00)
[FAILURE] test failed: 4 AC / 32 cases
(略)
結構失敗しちゃいます
これは手強そう
ドキュメントを充実させないと。。。
objectで静的変数を使いたい場合、type S[N:static[int]]といった具合にジェネリクスに入れてやってます。したがって、ジェネリクスが冗長になってしまいます。
そのジェネリクスが関数だったりするとややこしく、それをいろいろ動作確認してて1日くらいはつぶれました。そのノウハウがsegtreeやlazysegtreeにありますので実装をごらんください。
ジェネリクスに入れる以外のもっとよい手法があるといいのですが。。。
oj-verifyでインクルードパスが指定できないことから、Nim-ACLのインクルードパスであるsrc/でoj-verifyを実行するか、src/以下をoj-verifyの実行場所に移動しなくてはなりません。
現状は後者でやっていますが、以下のような問題があります。
前者の場合はsrcディレクトリに.verify-helperができてしまってソース以外のものがあるあたりが見栄えが悪いです。
どちらがいいですかね。
形式的べき級数がものすごく入り組んでいて難解なので整理したい。
また、echoしたときに以下のように多項式表示されると嬉しい。
type mint=modint998244353
f:FPS[mint] = @[3, 1, 4, 1, 5]
echo f # 5x^4+x^3+4x^2+x+3
pushしたときに起こるtravisのtestに時間制限があって、現状すべてのverifyが動かせない状況にあります。
travisでやってるのは、ドキュメントの生成・testの実行(oj-verifyのverifyとnimble testの実行)なので、ドキュメントだけでいいかもです。
グラフのデータ構造について以下のようなものを考えており、dijkstra等のグラフ処理はできるだけすべての場合に対応させたいです。(すべてのアルゴリズムに対応させるのが結構大変。。。)
Twitterでも提起したconverterの問題です。例えばジェネリクスを使ってライブラリを使うときに、整数nをジェネリクスTに変換したい場面がよく出てきます。TはModInt以外にもfloatやint自身だったり行列だったりいろいろ考えられます。通常T(n)を呼ぶとこの変換ができるという風にするのが自然です。
このとき、modintをdistinctで定義すると、converterが勝手に定義され、ModIntMを呼んだとき、initModIntが呼ばれず、n>=Modだったりn<0だったりするときに、バグを発生させる危険があります。
実はdistinctを用いない場合でもconverterを定義しても下記のような不具合があります。
modintのコンストラクタのルールとしては以下が考えられるのですが、どれがよろしいですかね!?
distinctを用いる
利点: ModIntMが自動で定義され、そのまま呼べる
欠点: 利点で定義したものから変更できない。特にnが0..<Mに含まれないときは要注意
distinctを用いない
利点: Mごとに個別に定義すればconverterが定義できる
欠点: バグなのかわからないが、ModIntMが呼べない。type mint=ModInt[M]としてmintに対するコンバータを定義すれば大丈夫。
コンストラクタにconverterを用いない
ModInt[M].init(n)でintからModInt[M]に変換できるようにする。
利点: 新たな関数を定義するためconverterの不具合とは無縁である
欠点: ジェネリックプログラミングをする際、int型やfloat型でもint.initやfloat.initを定義しないといけない
いまのところ検討しているもの
src/nim_acl.nim
を削除して、src/nim_acl/
を atcoder/
にする
src/nim_acl/modint
と書かないといけないなら、同じかもatcoder
にして、src/nim_acl/
を src/atcoder/
にする
atcoder/modint
で OKatcoder/
で始まるパスに対応すればいいmv src/atcoder ./
とする後者の方が圧倒的によさそう
こちらの多倍長整数のライブラリをatcoderに搭載しているのですが、GMPが呼べないことでatcoderでは使えないことがわかりました。libgmp.soへのパスが通っていないことが原因です。
https://github.com/FedeOmoto/bignum
どちらかというとNim-ACLの問題ではなくatcoderの問題ですが、ご注意ください。次の言語アップデートまでに修正しなければ・・・
前にバージョン管理でやってくれという要望があったのですがまだできていないので、次のatcoderの言語アップデートに採用されるところあたりでバージョンを一つ発行しましょう。
oj-verifyが失敗していました
環境
% nim --version
Nim Compiler Version 1.6.14 [MacOSX: amd64]
Compiled at 2023-10-17
Copyright (c) 2006-2023 by Andreas Rumpf
active boot switches: -d:release
失敗したverify
% oj-verify run -j 8
(略)
ERROR:onlinejudge_verify.verify:11 tests failed
ERROR:onlinejudge_verify.verify:failed: verify/extra/geometry/aoj_cgl_2_d_distance_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/graph/centroid_decomposition_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/math/pow_of_formal_power_series_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/math/yosupo_factorization_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/aoj_grl_5_a_tree_diameter_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/aoj_grl_5_c_2_heavy_light_decomposition_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/rerooting_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/yosupo_lowest_common_ancestor_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/yosupo_tree_diameter_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/scc_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/twosat_test.nim
標記の通り、現在、ACLにないものでなおかつ基本的そうなものの追加を検討しています。例えば以下のようなものがあると思います。おそらく、カテゴリ分けすると以下のようになるかと思います。他にあった方が良さそうなものがありましたら、お申し付けください!
標記の通り、ACLにmath.nimというファイルがあると、Nimの標準ライブラリのmathが読めないようですがどうしますかね。
以下のようなNimのコードをexpander.pyを使って展開させると最後にdiscardが追加されるためコンパイルエラーが起きる
またこのようなことが競技プログラミング中に起きるとパフォーマンスに影響が出るためこのような点を減らして欲しい
問題が起きた際に対応しやすいようRelease機能を使ってバージョン管理してほしい
import sequtils,strutils,sugar, algorithm, tables
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld",addr result)
proc solve(A:int, B:int):string = ""
proc main():void =
var A = nextInt()
var B = nextInt()
echo solve(A, B)
return
main()
出力
import sequtils
import strutils
import sugar
import algorithm
import tables
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld",addr result)
proc nextFloat(): float = scanf("%lf",addr result)
proc nextString(): string =
var get = false
result = ""
while true:
var c = getchar()
if int(c) > int(' '):
get = true
result.add(c)
else:
if get: break
get = false
template cfor(init, comp, incr, body: untyped) =
block:
init
while comp:
body
incr
template times(n: int, body: untyped) =
for _ in 0..<n:
body
proc `$` [T](x: seq[T]): string = x.mapIt($it).join(" ")
proc `ceilDiv`[T: SomeInteger](x, y: T): T = x div y + ord(x mod y != 0)
proc solve(A:int, B:int):string =
if A > 0 and B == 0:
return "Gold"
elif A == 0 and B > 0:
return "Silver"
else:
return "Alloy"
proc main():void =
var A = nextInt()
var B = nextInt()
echo solve(A, B)
return
main()
discard
エラー
Error: invalid indentation
本家のC++はsnakecaseでクラス名mcf_graph[Cap, Cost], 関数名init_mcf_graphなどと書かれていますが、Nimではcamelcaseが推奨されているようでどっちに統一しようか迷っています。関数名は_や大文字小文字が区別されないので、どっちでも呼び出し可能なのでひとまずC++表記のままにしておきました。
問題は_と大文字小文字が区別されるobject名です。今のところ全部camelcaseでMCFGraphなどと書くようにしています。そういえばMCF(Min Cost Flow)などのように略語の場合はどうするかも迷っています。
どうしましょうかね。。。
segtree系やextraのgraph系に見られるように現在のACLではtemplate等を多用して抽象化したり多くのタイプに対応できるようにして、機能性を高めています。
その結果のデメリットとしてコードが読みにくくなったり、ダイクストラ法等でそのまま使用するのではなくコードの一部を改変して提出したくなったときにACLをベースに改変するのが難しくなってしまいます。
「コードの一部を改変して提出」の場合はACLではなく他のものを使ってもらうということでいいですかね。。。
% oj-verify run verify/extra/math/yosupo_factorization_test.nim
(略)
[INFO] fixed_RNG_buster_00
[INFO] time: 60.003001 sec
[INFO] $ /Users/kazusaku/Library/Caches/online-judge-tools/library-checker-problems/math/factorize/checker /Users/kazusaku/ghq/github.com/zer0-star/Nim-ACL/src/.verify-helper/cache/63dcd6151007c9a7ae546792ae5f0b96/test/fixed_RNG_buster_00.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpdr42ag6l/actual.out /Users/kazusaku/ghq/github.com/zer0-star/Nim-ACL/src/.verify-helper/cache/63dcd6151007c9a7ae546792ae5f0b96/test/fixed_RNG_buster_00.out
wrong answer Unexpected EOF in the participants output
judge's output:
(empty)
[FAILURE] TLE
input:
1
124376107291
output:
(empty)
expected:
2_352523_352817
(略)
1.6.14のstd/mathではceilDivが使えますが、ceilDiv(-3, -4)みたいに負の数を入れるとエラーになりますのでご注意ください。しかも前々からNim-ACLで同名で実装していたのでバッティングして面倒。。。
そういえば、気づいたんですが、インクルードガードするとき、
when not defined HOGE_HPP:
const HOGE_HPP = 1
when not defined HOGE_HPP:
const HOGE_HPP = 1
だと、二番目でredefinition errorになるようです。つまり、一回目のconstで定義してもそれが検知されていないです。definedはコンパイルオプションか何かで指定されたものがあるかみたいなコマンドで正しくはdeclaredにしないといけないっぽいです。
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.