Nim で yukicoder の最短時間を取って遊ぶ

はじめに

最近 Nim で yukicoder をやっています. 競技プログラミングとしてアルゴリズムを考えて楽しむのもいいのですが, 個人的にはどれだけプログラムをチューンできるかというISUCON的な遊び方をして楽しんでいます. yukicoder では最短実行時間をとるとゆるふわポイントが貯まり,ポイントランキングが可視化されるため,やりがいがあります. 現在やるだけの問題(☆2以下)を yukicoder で250問程解き,25問について最短時間を取得しました.

yukicoder.me

というわけで,この記事では,アルゴリズム的な改善は全て済んでおり,後は I/O など競技プログラミング的には問題の本質ではないところに改善の余地があるコードを想定し,これを 1ms でも速くして最短時間をとるメモを書きました.

自然数入力

proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    var k = getchar_unlocked()
    if k < '0' : break
    result = 10 * result + k.ord - '0'.ord
let n = scan()

自然数の入力の取得には,Nimの場合 stdin.readline().parseInt() が, C++の場合 std::cin >> n や scanf("%d",&n) などがありますが,速ければ正義なので,スレッドセーフを気にしない getchar_unlocked を使って自分で自然数を組み立てる手があります.感覚的には,1000個以上変数があると効いてくる様子.

自然数出力

proc putchar_unlocked(c:char){.header: "<stdio.h>" .}
proc printInt(a:int32) =
  template div10(a:int32) : int32 = cast[int32]((0x1999999A * cast[int64](a)) shr 32)
  template mod10(a:int32) : int32 = a - (a.div10 * 10)
  var n = a
  var rev = a
  var cnt = 0
  while rev.mod10 == 0:
    cnt += 1
    rev = rev.div10
  rev = 0
  while n != 0:
    rev = rev * 10 + n.mod10
    n = n.div10
  while rev != 0:
    putchar_unlocked((rev.mod10 + '0'.ord).chr)
    rev = rev.div10
  while cnt != 0:
    putchar_unlocked('0')
    cnt -= 1

# 直で書いたほうが速い
  proc printInt(a0:int32) =
    template div10(a:int32) : int32 = cast[int32]((0x1999999A * cast[int64](a)) shr 32)
    template put(n:int32) = putchar_unlocked("0123456789"[n])
    proc getPrintIntNimCode(n,maxA:static[int32]):string =
      result = "if a0 < " & $maxA & ":\n"
      for i in 1..n: result &= "  let a" & $i & " = a" & $(i-1) & ".div10\n"
      result &= "  put(a" & $n & ")\n"
      for i in n.countdown(1): result &= "  put(a" & $(i-1) & "-a" & $i & "*10)\n"
      result &= "  return"
    macro eval(s:static[string]): auto = parseStmt(s)
    eval(getPrintIntNimCode(0,10))
    eval(getPrintIntNimCode(1,100))
    eval(getPrintIntNimCode(2,1000))
    eval(getPrintIntNimCode(3,10000))
    eval(getPrintIntNimCode(4,100000))
    eval(getPrintIntNimCode(5,1000000))
    eval(getPrintIntNimCode(6,10000000))
    eval(getPrintIntNimCode(7,100000000))
    eval(getPrintIntNimCode(8,1000000000))

getchar_unlocked の対として putchar_unlocked があり,これを使う手があります. 32bit整数xを (int32)(0x1999999A * (int64)(x)) で x / 10 相当のことが出来るのは知らなかったです...

配列確保

# x = newSeqWith(n,stdin.readLine().parseInt()) 相当
var x : array[100010,int32]
for _ in 0..<n : x[i] = stdin.readLine().parseInt().int32

yukicoder の実行時間の結果はテストケースで最も時間のかかったものとなります. 最も時間のかかるテストケースは,制約ぎりぎりのサイズの配列が必要になることが多いです. そのため,実行中に動的に配列を確保するよりも,始めからグローバル変数として制約の限界まで固定長の配列を確保しておく方が高速なことが多いです. 制約的に32bitで済むなら配列を int (64bit) から int32 (32bit) に変更しておくことで更に高速化できる可能性があります.

コンパイル時計算

let X = (proc() : seq[int] =
  return @[] # ... 実行時に計算される
)()
const X = (proc() : seq[int] =
  return @[] # ... コンパイル時に計算される
)()

素数表など,コンパイル時に予め計算しておくことが出来る場合があります. Nim の場合, 定数代入 let ではなく, コンパイル時定数代入 const を使って代入するだけでコンパイル時に計算してくれます.

(/^^)/⌒●~*$ a(){ a|a& };a

\e[i