nimを競プロで讃える。

#はじめに
この記事はKyoto University Advent Calendar 2019
19日目の記事です。

初めまして、YagiEL(@yagi_el)です。京大工学部建築学科3回生で、来年度から桂に流される民です。昨日は桂キャンパスのクリスマスコンサートを観に行ってました。いい試みだったと思います。

さて、人生初のアドベントカレンダーです。何か自分の専門以外の事を書きたいなーと思っていたので、AtCoderのEducational DP Contestの問題を使ってnimというプログラミング言語を推します。nimはいいぞ。nimを讃えよ。

ﾆﾑﾆﾑ(ノ)・ω・(ヾ)ﾆﾑﾆﾑ

#nimについて
まずnimについての説明を。nimは「効率的で、表現豊か、そしてエレガントな」静的型付け言語です。
速度について言えば、C並みの速度が出ると話題で、ちょくちょく実行速度の比較とかで挙げられることがありますね。

FizzBuzz を無駄にベンチマークしてみた By Nim、golang、Rust、Crystal、その他

構文の見た目はPython風で非常にエレガント

fibona.nim

import strutils
let n=stdin.readline.parseInt
var ans:seq[int]= @[0,1]
if n==0:
    echo ans[0]
elif n==1:
    echo ans[1]
else:
    for i in 2..n:
        ans.add(ans[i-1]+ans[i-2])
    echo ans[n]

入力された数値番目のフィボナッチ数を返すプログラムです。(その他詳しい文法はこちらなどを参照してください。)

インデントでブロックを表現しているあたりとか、if文・for文とか見た目まんまPythonですよね。nimは書きやすさ×見やすさ×速度を兼ね備えた言語です!!
今日はこんなnimさんとAtCoderの問題を解いていきます。各問題の【問題概要】と【制約】はこちらから引用しました。

#A問題 Frog1
###【問題概要】
$N$個の足場があって、$i$番目の足場の高さは$h_i$です。
最初、足場$1$にカエルがいて、ぴょんぴょん跳ねながら足場$N$へと向かいます。カエルは足場$i$にいるときに

• 足場iから足場$i+1$へと移動する(そのコストは$|h_i−h_i+1|$)
• 足場iから足場$i+2$へと移動する(そのコストは$|h_i−h_i+2|$)

のいずれかの行動を選べます。カエルが足場$1$から足場$N$へと移動するのに必要な最小コストを求めよ。
###【制約】
$2≤N≤10^5$
###【解法】
まずは1問目。
リストdpを

dp[i]:=カエルが足場iへと移動するのに必要な最小コスト

とします。
$i$番目の足場には$i-1$番目あるいは$i-2$番目から飛んでくることができるので双方から飛んできた場合に、そこまでかかったコストの内小さい方を$dp[i]$に記録します。

Problem_a.nim

import sequtils,strutils,future
let
 n=stdin.readline.parseInt
 hs=map(split(readline(stdin)),parseInt)
var
 dp:seq[int]=repeat(0,n)#dpテーブルの初期化
dp[1]=abs(hs[1]-hs[0])
for i in 2..n-1:
 dp[i]=min(abs(hs[i]-hs[i-1])+dp[i-1]
 ,abs(hs[i]-hs[i-2])+dp[i-2])#コストの小さい方を記録
echo dp[n-1]

let以下の2行を見てください。nimはスネークでもキャメルでも書けます。んー変態。

#B問題 Frog2
###【問題概要】
$N$個の足場があって$i$番目の足場の高さは$h_i$です。
最初、足場$1$にカエルがいて、ぴょんぴょん跳ねながら足場$N$へと向かいます。カエルは足場$i$にいるときに

• 足場$i$から足場$i+1$へと移動する (そのコストは$|h_i−h_i+1|$)
• 足場$i$から足場$i+2$へと移動する (そのコストは$|h_i−h_i+2|$)
• ...
• 足場$i$から足場$i+K$へと移動する (そのコストは$|h_i−h_i+K|$)

のいずれかの行動を選べます。カエルが足場$1$から足場$N$へと移動するのに必要な最小コストを求めよ。

###【制約】

• $2≤N≤10^5$
• $1≤K≤100$

###【解法】
A問題よりちょっと難しい設定ですね。
$i$番目の足場への飛び方が増えますね。
$i-1$,$i-2$,...$i-min(i,k)$番目の足場から飛ぶことができます。
ので、今回は各足場からのコストを記録したリストを作ってそれの中から最小のものを選びます。

Problem_b.nim

import sequtils,strutils,future
let
 nk=stdin.readline.split.map(parseInt)
 (n,k)=(nk[0],nk[1])
 hs=stdin.readline.split.map(parseInt)
var
 dp=repeat(0,n)
for i in 1..n-1:
 dp[i]=lc[abs(hs[i]-hs[i-m])+dp[i-m]|(m<-1..min(k,i)),int].min
echo dp[n-1]

for文で使っているリスト内包表記(dp[i]=lc[~]の部分)なんですが、ver0.19か0.20あたりでdeprecatedになったので何とか方法はないものかと調べてみたらこんな書き方も(とはいえ、AtCoderのnimはver0.13だからまだ大丈夫)

Problem_b2.nim

for i in 1..n-1:
 dp[i]=(var x:seq[int]= @[]; for m in 1..min(k,i).min:
 x.add(abs(hs[i]-hs[i-m])+dp[i-m]);x).min

こっちの方が見た目はPythonのリスト内包表記に近いか???

#C問題　Vacation
###【問題概要】
$N$日間の夏休みです。$i$日目には、

A: 海で泳ぐ。幸福度 $a_i$ を加算
B: 山で虫取りする。幸福度$b_i$を加算
C: 家で宿題をする。幸福度$c_i$を加算

の三択の中から好きなものを選ぶことができます。ただし、$2$日連続で$A,B,C$のうちの同一種類の活動を選択をすることはできません。この制約下で最終的に得られる幸福度の総和を最大にせよ。
###【制約】
$1≤N≤10^5$
###【解法】
この問題からdpテーブルが2次元になりますね。

dp[i]:=$i$日にそれぞれの活動を行った場合の幸福度の最大値

を記録します。
ここで$dp[i][2]$($i$日目に活動C行ったときの幸福度の最大値)を考えてみます。
$2$日連続で同じ活動をすることはできないので$i-1$日目には活動A,Bのどちらかを行っていたことが分かります。
よって

dp[i][2]=$i-1$日目に活動A,Bを行った場合の幸福度の内大きい方

一般化すれば

dp[i][j]=$i-1$日目に$j$以外の活動を行ったときの幸福度の内大きい方
(ただし$j=0$⇒活動A,$j=1$⇒活動B,$j=2$⇒活動C)

になりますね

Problem_c.nim

import strutils,sequtils,future
let
 n=stdin.readline.parseInt
 abc=lc[stdin.readline.split.map(parseInt)|(m<-1..n),seq[int]]
 #abc=(var x:seq[int];for i in n: x.add(stdin.readline.split.map(parseInt));x)でもいけますね!
var
 dp=repeat(repeat(0,3),n)
for j in 0..n-1:
 if j>0:
  for i in 0..2:
   dp[j][i]=max(lc[dp[j-1][m]|(m<-0..2,i!=m),int])+abc[j][i]
 else:
  dp[0]=abc[0]
echo max(dp[n-1])

そうそう、nimで変数・定数を宣言する時なんですが、キーワードが3種類あります。

###const
コンパイル時定数の宣言に用います。よくある「値をmで割った余りを出力してください」みたいな問題で便利ですね。
###let
　書き換え不能な変数を宣言する時に用います。
　値を入力する時に利用できます。
###var
　書き換え可能な変数を宣言する時に用います。

簡単に宣言できて分かりやすいですね!

#おわりに
うまくnimを布教できたでしょうか?
ﾆﾑﾆﾑ(ノ)・ω・(ヾ)してきたな。って人は是非nimってみてください。そしてnimを讃えるのです。
アドベントカレンダーとは別にD問題以降も解いていきたいですね。

明日のKyoto University Advent Calendar 2019はdragon_taroさんの記事ですね(すでに書き終えているらしい)。あと6日盛り上げていきましょう!!