AtCoder に登録したら解くべき精選過去問 10 問をNimで解いてみた

## はじめに

くちもちとくらです！

けんちょんさんの記事の[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067#c-%E4%BB%A5%E5%A4%96%E3%81%AE%E8%A8%80%E8%AA%9E%E3%81%A7)
これを(便乗して)Nim langで解いてみました
個人的にNim langは気になっていたのでとてもいい機会だと思って解きました
なので、あまりよくない書き方もあるかもしれませんが、よろしくお願いします
バージョンはNim0.13.0です

こちらは公式のマニュアルです(検索しまくりました)

https://nim-lang.org/docs/manual.html

## 0.[はじめてのあっとこーだー(Welcome to AtCoder)](https://beta.atcoder.jp/contests/abs/tasks/practice_1)

```nim
import strutils
import sequtils

proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)

var a = getInt()
var bc = getInts()
var s =  readLine(stdin)
# カンマ区切りで出力を次々にしていく
echo a + bc[0] + bc[1] , " " , s

# https://beta.atcoder.jp/contests/abs/submissions/2237924
```
C++では頭を使わずにstd::cinでできる入力がちょっと大変ですが
getIntは整数が入力一行に１個しか無い時
getIntsは整数が入力一行に2個以上ある時に整数の配列として返す関数です

readLine(stdin)が入力をstringで返しています\

ついつい「;」を押してしまって大変でした...

## 1.[ABC 086 A - Product](https://beta.atcoder.jp/contests/abc086/tasks/abc086_a)

```nim
import strutils
import sequtils
import math 

proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)

var arr = getInts()

if (arr[0] * arr[1]) mod 2 == 0 :
    echo "Even"
else:
    echo "Odd"

# https://beta.atcoder.jp/contests/abc086/submissions/2237964
# 実行時間 1ms
```

if文の登場です
C++のように条件の括弧は必要なく
中括弧もコロンとインデントによって解決されています
(C++の%が使えなくってハマった)

## 2.[ABC 081 A - Placing Marbles](https://beta.atcoder.jp/contests/abc081/tasks/abc081_a)

```nim
import strutils
import sequtils 

var s : string = readLine(stdin)

echo s.count('1')

# https://beta.atcoder.jp/contests/abc081/submissions/2237974
# 実行時間 1ms
```

引きました()
コレクションの操作関数を全く使ったことがなかったので余計にびっくりしました
すごい

## 3.[ABC 081 B - Shift Only](https://beta.atcoder.jp/contests/abc081/tasks/abc081_b)

```nim
import strutils
import sequtils
import math 

proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)

var n = getInt()
var a = getInts()

proc TC(x : int) : int = 
    var now : int = x
    var cou = 0
    while now mod 2 == 0:
        cou += 1
        now = now div 2
    #C++ ... return cou;
    cou

echo a.map(TC).min() 


# https://beta.atcoder.jp/contests/abc081/submissions/2231133
# 実行時間 1ms
```

TC(x : int) は数xについて何回2で割り切れるかをカウントするものです

各iについてTC(A[i])を計算し,その最小値を出せばOKです

関数の値の返し方はreturnも書かずに,変数やリテラルを置くだけです

## 4.[ABC 087 B - Coins](https://beta.atcoder.jp/contests/abc087/tasks/abc087_b)

```nim
import strutils
import sequtils

proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)


var a = getInt()
var b = getInt()
var c = getInt()
var x = getInt()
var res = 0

for i in countup(0,a):
    for j in countup(0,b):
        # 金額がオーバーしているかどうか
        if x < i * 500 + j * 100:
            continue
        # 残りの金額から50円玉の数がわかる
        var k = (x - i * 500 - j * 100) div 50
        # 50円玉の数の上限を超えていないかどうか
        if k <= c:
            res += 1

echo res

# https://beta.atcoder.jp/contests/abc087/submissions/2231160
# 実行時間 1ms
```

for文です
昇順はcountup(from,to)、降順はcountdown(from,to)
わかりやすくていいですね

また continue break もC++や他の言語と同じように使えます

## 5.[ABC 083 B - Some Sums](https://beta.atcoder.jp/contests/abc083/tasks/abc083_b)

```nim
import strutils
import sequtils

proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)

var arr = getInts()
var n = arr[0]
var a = arr[1]
var b = arr[2]

proc digitSum(num : int) : int =
    if num == 0:
        result = 0
    else :
        result = digitSum(num div 10) + (num mod 10)

var res = 0
for i in countup(1,n):
    var t = digitSum(i)
    if a <= t and t <= b : 
        res += i
echo res

# https://beta.atcoder.jp/contests/abc083/submissions/2231201
# 実行時間 1ms
```

DPで解きました
ある数、例えば123の各桁の和をdigit(123)と置くと
```
digit(123) = digit(12) + 3
           = (digit(1) + 2) + 3
```

というように再帰的に求められます

digitSumで使われている resultですが

```
digitSum(3)
   -> 初めて呼ばれたので普通に計算する
...
digitSum(3)
   -> 過去に計算したことがある -> その値を返す(計算しない)
```

ということができdpテーブルを書かずともdpができるみたいです(感動)

## 6.[ABC 088 B - Card Game for Two](https://beta.atcoder.jp/contests/abc088/tasks/abc088_b)

```nim
import strutils
import sequtils
import algorithm
proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)

var n = getInt()
var a = getInts()

sort(a,cmp)
# 降順にする
reverse(a)

var dif = 0
var pro = 1
for i in a:
    dif = dif + pro * i
    # 交互にする
    pro = pro * -1
echo dif

# https://beta.atcoder.jp/contests/abc088/submissions/2231226
# 実行時間 1ms
```

sortはalgorithmモジュールにありました
cmpはintやstringの比較を行ってくれます

foreach文が気軽に使いやすく見やすいのは好きですね

## 7.[ABC 085 B - Kagami Mochi](https://beta.atcoder.jp/contests/abc085/tasks/abc085_b)

```nim

import strutils
import sequtils
import algorithm
import sets
proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)

var n = getInt()
# initSet[type](size...2の冪乗でないとNG)
var st = initSet[int](128)
for i in countup(1,n):
    var a = getInt()
    st.incl(a)

echo st.len()

# https://beta.atcoder.jp/contests/abc085/submissions/2231291
# 実行時間 1ms
```
setを使います
setは同じ値を持たないので、最終的な答えはsetの中に入っている値の種類数になります

C++ でいうinsertはinclでした(include??)

## 8.[ABC 085 C - Otoshidama](https://beta.atcoder.jp/contests/abc085/tasks/abc085_c)

```nim
import strutils
import sequtils
import algorithm
proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)

var arr = getInts()
var n = arr[0]
var y = arr[1]

y = y div 1000

var ansi = -1
var ansj = -1
var ansk = -1

for i in countup(0,n):
    for j in countup(0,n - i):
        var k = n - i - j
        if k >= 0 and i * 10 + j * 5 + k == y:
            ansi = i
            ansj = j
            ansk = k

echo ansi , " " , ansj , " " , ansk

# https://beta.atcoder.jp/contests/abc085/submissions/2231315
# 実行時間 3ms
```
三重ループだと間に合いません！！っていう問題ですね
特に言語的な問題はありません

## 9.[ABC 049 C - Daydream](https://beta.atcoder.jp/contests/abc049/tasks/arc065_a)

```nim
import strutils
import sequtils
import algorithm
import unicode

var s = readLine(stdin)
var str = @["dream","dreamer","erase","eraser"]

s = s.reversed
str = str.map(proc (x : string) : string = x.reversed)

while s != "":
    var update = false
    for now in str:
        if s.len < now.len:
            continue
        elif s.substr(0,now.len - 1) == now:
            s = s.substr(now.len,s.len - 1)
            update = true
    if update == false:
        break
if s == "":
    echo "YES"
else:
    echo "NO"

# https://beta.atcoder.jp/contests/abc049/submissions/2237885
# 実行時間 112ms
```

逆からとくとハッハッハっていう問題です
文字列をreverseするときはimport unicodeして
reversedをします

substrはfrom,to形式でした(C++はpos,len形式)

4つの文字列を使っても取り除けなくなったとき(updateがfalseのとき)breakしています

## 10.[ABC 086 C - Travelling](https://beta.atcoder.jp/contests/abc086/tasks/arc089_a)

```nim

import posix
import strutils
import sequtils
import algorithm
proc getInt() : int =
    parseInt(readLine(stdin))

proc getInts() : seq[int] = 
    readLine(stdin).split().map(parseInt)

var n = getInt()

var t = 0
var x = 0
var y = 0

for i in countup(1,n):
    var temp = getInts()
    var nt = temp[0]
    var nx = temp[1]
    var ny = temp[2]
    var dist = abs(x - nx) + abs(y - ny)
    if not(nt - t >= dist and (nt - t - dist) mod 2 == 0):
        echo "No"
        exitnow(0)
    t = nt
    x = nx
    y = ny
echo "Yes"

        
# https://beta.atcoder.jp/contests/abc086/submissions/2237911
# 実行時間 58ms
```

時刻tのときにいる地点をx,y
時刻ntにいなければならない地点をnx,nyとします
最短で移動すると```abs(x - nx) + abs(y - ny)```の時間がかかります

移動するのにパターンは2つです

・時間が足りねぇ -> 当然時間内に到達出来ないので"No"を出力して終了します
・時間は足りるが```S```だけ時間が余っている

時間を潰す方法は左右に動いていれば良いです(その場所にとどまれないので)
つまり左右に動いて時間がntになった時(nx,ny)にいられるかどうか
これは Sが2で割り切れるかどうかで判定できます

# 気が付きましたか？

実行時間です
すごく早い...
このような書き方の言語は遅いイメージがあったのですが覆されました...

10問目に限ってはほぼ同じ書き方なのにもかかわらずC++14(GCC)の速度を上回っていました

[C++のコード](https://beta.atcoder.jp/contests/abc086/submissions/2000504)
[Nim langのコード](https://beta.atcoder.jp/contests/abc086/submissions/2237911)

早いと好きになっちゃいますね()

## 感想

なかなか競プロにも使いやすい言語かなーという印象を受けました

他にも言語仕様がたくさんあるようなのでもっと詰めて勉強してもいい言語だと思います

ただまだ記事が充実していないような気がします

もっと伸びるといいですね...