Nim で競プロがやりたい！

この記事は？

この記事は、Nimで競プロをやる50のTipsアドベントカレンダーの1日目の記事です。 このシリーズでは、Nim言語を使って競技プログラミングの問題を解く際に役立つTipsを紹介していきます。

1日目の今回は、そもそも競技プログラミングとは何かと、Nimで競技プログラミングをするメリットについて解説します。

競技プログラミングとは

競技プログラミング自体については、例えばAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～などの優れた解説記事がすでに複数あるため、ここでは軽く触れるにとどめます。

競技プログラミングとは、端的には効率的に動作するプログラミングを「早く」「正確に」行う能力を競う競技です。上の記事では、

プログラミングを使って、パズル的な問題を、制限時間内に出来るだけ多く解くスポーツ

と紹介されています。
AtCoderをはじめとして、プログラミングコンテストを主催する団体は複数あり、近年では参加者も増加傾向にあるため、やったことは無くとも名前を聞いたことがある、という方もいらっしゃるかもしれません。

具体的な例を見てみましょう。例えば、競技プログラミングでは以下のような問題が出題されます。

AtCoder Beginner Contest 294 - A: Filter

長さ $N$ の整数列 $A=(A_1, A_2, \cdots ,A_N)$ が与えられます。$A$ から偶数だけすべて取り出し、もとの順番を保って出力してください。
$1\le N \le 100, 1\le A_i \le 100, A$には $1$ つ以上偶数が含まれる。

この問題では、例えば条件分岐を使って条件を満たすもののみが含まれる配列を作って出力する以下のようなコードで正答することができます。

import strutils, sequtils

var n = stdin.readLine.parseInt
var a = stdin.readLine.split.map parseInt
var ans = newSeq[int]()
for i in 0..<n:
    if a[i] mod 2 == 0:
        ans.add(a[i])
echo ans.join(" ")

このようなコードを正確に、かつ他のコンテスタントよりも早く書くことで、より上位の成績を取ることができます。

Nim で競技プログラミングをするメリット

個人的に感じる、Nimで競技プログラミングをするメリットは3つあります。順にあげていきます。

コードを短く、シンプルに記載するための記法が揃っている

競技プログラミングにおいて、コードを書くためにかかる時間を短縮することは非常に重要です。例えば、先程上で紹介した問題ですが、最速の正答はコンテスト開始からわずか17秒後に出ています。（当然、問題文の読解、サンプルケースの確認、コードを書く時間をすべて含めてこの時間です。）

コードを早く書く、という観点で見ると最も単純な解決方法は、より簡潔な書き方を身に着けて実装に必要なタイプ数や文字数を減らすことです。例えば上に上げたコードも filterIt テンプレートを用いることで実装量を減らすことができます。

import strutils, sequtils
discard stdin.readLine
echo stdin.readLine.split.map(parseInt).filterIt(it mod 2 == 0).join(" ")

競技プログラミングでよく用いられる C++ などの言語と比較して、このように実装をシンプルにする記法が多く用意されていることは、Nim で競技プログラミングをするモチベーションとなると感じます。

実行が高速である

競技プログラミングにおいては、しばしばコードの実行速度が問題となることがあります。というのも、問題ごとに提出したコードの実行時間制限が設けられており、この制限内に実行が完了しない場合は、たとえ実装に誤りがなくとも誤答として扱われてしまうためです。

多くのコンテストサイトでは複数の言語の中から提出言語を選んで提出し、実行速度が遅い言語であっても著しく不利にはならないようなルールとなっていることが多いものの、Pythonなどの低速な言語でコンテストに参加した場合に、これらの制限によって不利益を被ることが稀にあります。（もちろん、Pythonはコードをシンプルに書くという観点で非常に優れているので、そのメリットと天秤にかけることになり、Pythonで競技プログラミンをすることが不利である、というものではありません）

私は Nim で580問以上の問題を解きましたが、その中で言語の実行速度によって不利益を被ったと感じた問題は10問もなく、また、それらもほとんどは、書き方を改善することで一般的に高速と言われる言語（C++、Rustなど）と比較して遜色ない速度とすることができました。競技プログラミングで利用する上で実行速度が本質的に問題となるケースは、Nim においては無いと考えています。

有志が整備したライブラリによって、基本的なデータ構造が利用可能

競技プログラミングにおいては、難易度の高い問題になるにつれ、言語の標準ライブラリに含まれないような特殊なデータ構造などを用いる問題が出題されることがあります。特に、競技プログラミングにおいてよく利用されるライブラリを集めたライブラリとして、有名なものとしてAtCoder Library (ACL)があります。

これはC++で実装されたものですが、Nim にはこれを移植したライブラリとしてNim-ACLがあり、AtCoder, yukicoderのコンテストサイトで利用可能です。
また、このNim-ACLは、元々のACLに含まれないようなさらに特殊なデータ構造も実装されており、実際にそれを用いて本番中に問題に回答できたこともあります。（例： https://atcoder.jp/contests/abc328/submissions/47494241 、ポテンシャル付きUnion-Find）

このような便利なライブラリが利用可能である、ということは他言語にはないメリットです。

まとめ

今回の記事では、Nim で競技プログラミングをするメリットについてまとめました。私は元々Pythonを使って競技プログラミングをしており、その後C++を使って現在はNim、と3つの言語を使用してきました。Python から C++ への移行は主に実行時間を懸念してのものでしたが、私はタイピングがそこまで早くないこともあり、実装量が多くなりがちな C++ での実装に苦しさを感じることもありました。
Nim に移行してからはコードをシンプルに書くことができることに非常に満足しています。

また、Nim でのプログラミングはとても楽しいです。C++ ではあまり便利な記法がなく愚直な書き方が求められることが多く、あまり実装の振れ幅が大きくないように感じていましたが、Nimでは色々な記法があるため「どのようにすればシンプルに書けるだろうか」「こんな便利な記法があったのか、使ってみたいな」というように、ワクワクしながらコードを書くことがてきています。書いていて、とても楽しい言語なので、ぜひこのシリーズを通して、皆さんにもNimの楽しさを知ってもらえればと思います。

次：TBD