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

はじめに

くちもちとくらです！

けんちょんさんの記事のAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
これを(便乗して)Nim langで解いてみました
個人的にNim langは気になっていたのでとてもいい機会だと思って解きました
なので、あまりよくない書き方もあるかもしれませんが、よろしくお願いします
バージョンはNim0.13.0です

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

0.はじめてのあっとこーだー(Welcome to AtCoder)

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

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

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

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

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

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

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

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

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

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

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++のコード
Nim langのコード

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

感想

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

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

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

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