NimでAtCoder Beginners Selectionを解いてみた!

はじめに

昔にNimの競プロ記事を書いていたのですが、今改めてNimで競プロを始めるならやっぱりAtCoder Beginners Selectionの解説があった方が便利だよなーと思ったので 、マイナー言語Nimを普及させるために解いた記事を書いておきます。 Nimをご存じない方は、この記事を読んで、書きやすそうだなと思ってもらえれば幸いです。

僕のNimの競プロライブラリはこちらにあります。

古いAtCoder用Nim0.13.0のドキュメントやビルド情報はこちらにまとめてあります。

最新のNimの場合は こういう感じで コードの内部実装が手軽に読めるという特徴があります。

また、訳あって入力のとり方はやや非自明な取り方をしていますが、これは自分に合うものを使用してください。

入力のとり方について補足

入力が

n
A1 A2 A3 ... An
B1
B2
...
Bn

とあった時に通常は以下のように書くことが多いです。

let n = stdin.readLine.parseInt()
let A = stdin.readline().split().map(parseInt) # 一行の中で空白で分割して取る
let B = newSeqWith(n,stdin.readLine().parseInt()) # 行ごとに取る

この書き方では、場合に応じて2つの書き方を使い分けないといけない欠点があります。 長いしややこしいですよね。

なので最近ではC言語scanfを使ってこう書いています。

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let A = newSeqWith(n,scan())
let B = newSeqWith(n,scan())

意味が明確かつ簡略になって、かなり見やすくなりました! 便利!

1 Product

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
if (scan() * scan()) mod 2 == 0 : echo "Even"
else:echo "Odd"

ちなみに scan() なしだと let tmp = stdin.readLine.split().map(parseInt);let a = tmp[0];let b = tmp[1] と書かないといけなくてつらいです。

2 Placing Marbles

import sequtils
echo stdin.readLine().filterIt(it=='1').len

配列の操作には なんとかit が便利です。 Nimは fun(a,b,c)a.fun(b,c) と書ける(UFCS)のでメソッドチェイン的なことができて便利です。

あとは getchar を使う解法もあります。

proc getchar():char {. importc:"getchar",header: "<stdio.h>",discardable .}
echo newSeqWith(3,getchar()).filterIt(it=='1').len

3 Shift only

import sequtils
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
var A = newSeqWith(n,scan())
var ans = 0
while A.allIt(it mod 2 == 0):
  A = A.mapIt(it div 2)
  ans += 1
echo ans

allIt などの便利な なんとかIt を使っていきましょう。 定数への代入は let 、変数への代入には var を使います。

while A.all(proc(x:int):bool = x mod 2 == 0):
  A = A.map(proc (x:int):int = x div 2)

のように関数を作成して書いてもOKです。

また、 import future (最新のNimでは import sugar) をすると

while A.all(x => x mod 2 == 0):
  A = A.map(x => x div 2)

みたいな感じにも書けます。 なんとか It は 言語機能にあるわけではなく、配列を操作するタイプで個別に実装しているだけなので、 こういうラムダ式形式の書き方も応用性は広く覚えておいて損はないです。

4 Coins

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let a = scan()
let b = scan()
let c = scan()
let x = scan()
var ans = 0
for ia in 0..a:
  for ib in 0..b:
    for ic in 0..c:
      if 500 * ia + 100 * ib + 50 * ic == x : ans += 1
echo ans

forループは for i in 0..n で n を含み、 for i in 0..<n で n を含まない意味でループを回せます。

5 Some Sums

import sequtils,math
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let a = scan()
let b = scan()
var ans = 0
for i in 1..n:
  let isum = ($i).mapIt(it.ord - '0'.ord).sum()
  if a <= isum and isum <= b: ans += i
echo ans

数字の文字列化は $ 演算子を使います。 文字コードの数値を取得するには ord を使います。

6 Card Game for Two

import sequtils,algorithm
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let A = newSeqWith(n,scan()).sortedByIt(-it)
var alice = 0
var bob = 0
for i,a in A:
  if i mod 2 == 0 : alice += a
  else : bob += a
echo abs(alice - bob)

import algorithm の後、 破壊的にソートする場合は sort() が、新たに作成する場合は sorted が使えます。 今回の場合は、ソートのキーを指定する .sortedByIt(-it) の他に、通常のソート .sorted(cmp,Descending) と書くのもありです。 for a in A ではなく for i,a in A と書くことで、 i に配列のindex を取得することができ、便利なことが多いです。

7 Kagami Mochi

import sequtils,tables
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
echo newSeqWith(n,scan()).toCountTable().len

古いNim 0.13.0では deduplicate がO(N2) かかるので注意が必要です。 最新のではソート済み情報を渡せるので大丈夫ですが。

8 Otoshidama

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let y = scan()
for ia in 0..n:
  for ib in 0..(n-ia):
    let ic = n - ia - ib
    if ic >= 0 and ia * 10000 + ib * 5000 + ic * 1000 == y :
      echo ia," ",ib," ",ic
      quit 0
echo "-1 -1 -1"

proc 内ではないためreturn が書けないのですが、実は quit 0 でプログラムを終了できます。

9 Daydream

import strutils
var S = stdin.readLine()
proc check():bool =
  for word in ["dreamer","eraser","erase","dream"]:
    if S.endsWith(word):
      S = S[0..^(word.len+1)]
      return true
  return false
while S.len > 0:
  if not check(): quit "NO",0
echo "YES"

Nim は文字列操作も割と得意です。

10 Traveling

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
var (ct,cx,cy) = (0,0,0)
for _ in 0..<n:
  let (t,x,y) = (scan(),scan(),scan())
  let (dt,dx,dy) = (t-ct,x-cx,y-cy)
  if dx.abs + dy.abs > dt or abs(dx + dy) mod 2 != dt mod 2: quit "No",0
  (ct,cx,cy) = (t,x,y)
echo "Yes"

Nimはタプルの分割代入が可能なため、必要に応じて使っていきましょう。

最後に

Nimはマイナー言語ですが、AtCoderでも毎回片手では数えられない程度の人数がNimで解いて提出しています! 書きやすくて速い最高の言語であるNimの使用者が増えてくれるといいな〜〜〜