NimでAtCoder Beginners Selectionを解いてみた!
はじめに
昔にNimの競プロ記事を書いていたのですが、今改めてNimで競プロを始めるならやっぱりAtCoder Beginners Selectionの解説があった方が便利だよなーと思ったので 、マイナー言語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の使用者が増えてくれるといいな〜〜〜