エラー

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. ジェネリクスに無理やり入れる→デメリット：いろいろとコツがいる、Nimの公式の手法ではなさそう
2. dynamic変数で我慢する→デメリット：遅い

があって、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だと動かない

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の実行場所に移動しなくてはなりません。

現状は後者でやっていますが、以下のような問題があります。

1. 一部のテストが実行されない不具合がある。(原因はよくわかっていませんがmvをするとタイムスタンプが変わるところが怪しいです)
2. 生成されたドキュメントのリンク先のgithubページに飛べない

前者の場合は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等のグラフ処理はできるだけすべての場合に対応させたいです。（すべてのアルゴリズムに対応させるのが結構大変。。。）

1. 整数のノード, 配列による隣接ノード(達成)
2. 整数に限らないノード, 配列による隣接ノード, 整数のid関数を指定(達成)
   • id関数によってノードの一次元配列での管理が可能
   • idの逆関数が必要かも。。。
3. 整数に限らないノード, 関数による隣接ノード, 整数のid関数を指定(達成)
   • 隣接点は到達したときにはじめて呼ばれるため、最初から配列を用意する必要がない。各種のアルゴリズムで到達しない点の分だけ高速化が期待される。
4. 整数に限らないノード, イテレータによる隣接ノード, 整数のid関数を指定(達成)
   • 関数指定と似ているがイテレータの方が指定がしやすい。
   • イテレータはclosureでないとだめそう。closureのイテレータのリセットはdeepCopyでやった（これが最善か？）。しかし遅いかも？
5. 整数に限らないノード, 関数・イテレータによる隣接ノード, idなし(未達)
   • ノードの構造が複雑でidを振ることが難しい場合に使うことを想定
   • ノードはTableで管理する。その際の性能低下は許す

Twitterでも提起したconverterの問題です。例えばジェネリクスを使ってライブラリを使うときに、整数nをジェネリクスTに変換したい場面がよく出てきます。TはModInt以外にもfloatやint自身だったり行列だったりいろいろ考えられます。通常T(n)を呼ぶとこの変換ができるという風にするのが自然です。

このとき、modintをdistinctで定義すると、converterが勝手に定義され、ModIntMを呼んだとき、initModIntが呼ばれず、n>=Modだったりn<0だったりするときに、バグを発生させる危険があります。
実はdistinctを用いない場合でもconverterを定義しても下記のような不具合があります。
modintのコンストラクタのルールとしては以下が考えられるのですが、どれがよろしいですかね！？

1. distinctを用いる
   利点: ModIntMが自動で定義され、そのまま呼べる
   欠点: 利点で定義したものから変更できない。特にnが0..<Mに含まれないときは要注意

2. distinctを用いない
   利点: Mごとに個別に定義すればconverterが定義できる
   欠点: バグなのかわからないが、ModIntMが呼べない。type mint=ModInt[M]としてmintに対するコンバータを定義すれば大丈夫。

3. コンストラクタにconverterを用いない
   ModInt[M].init(n)でintからModInt[M]に変換できるようにする。
   利点: 新たな関数を定義するためconverterの不具合とは無縁である
   欠点: ジェネリックプログラミングをする際、int型やfloat型でもint.initやfloat.initを定義しないといけない

いまのところ検討しているもの

• src/nim_acl.nim を削除して、src/nim_acl/ を atcoder/ にする
  • これをすると、nimble で管理できなくなる
    • 現状手元でも src/nim_acl/modint と書かないといけないなら、同じかも
• package 名を atcoder にして、src/nim_acl/ を src/atcoder/ にする
  • import のときは atcoder/modint で OK
  • expander.py では atcoder/ で始まるパスに対応すればいい
  • verify のときは事前に 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にないものでなおかつ基本的そうなものの追加を検討しています。例えば以下のようなものがあると思います。おそらく、カテゴリ分けすると以下のようになるかと思います。他にあった方が良さそうなものがありましたら、お申し付けください！

1. C++, pythonなどの主要な言語の標準ライブラリとしてすでに用意されているが、Nimにはないもの
   std::set, std::mapのような二分探索木, bitset,
2. ACLに用意されていない基本的なライブラリ
   ダイクストラ法、Prim法、深さ優先・幅優先探索、ローリングハッシュ、modintのcombination、素因数分解、約数列挙

標記の通り、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ではなく他のものを使ってもらうということでいいですかね。。。

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にしないといけないっぽいです。