Qiitaからこちらに転載した。AtCoderの環境の更新に合わせて、転載当時の内容から多少の変更を加えている。
表題の通り、競技プログラミングに参加しているLisperとこれから参加するかもしれないLisperのために、必要な情報を一通りまとめています。
コンテストサイトの選択
AtCoderではCommon Lispが使えますし、CLで投稿できる大手コンテストサイトはCodeChefやyukicoder、CS Academyなど他にもいくつかあります。日本語の問題文があって運営の質が高くてコンテストが頻繁に開催されていて……というような点を考えていくと、競プロに興味を持った日本語圏のLisperにとってAtCoderは第一の選択肢といってよいでしょう。第二はyukicoderとCodeChefです。以下の解説は、特に断りがなければAtCoderを前提にしています。
Lispで競プロすることについて
本題ではありませんが、セクションを立てて言及しておくことにします。というのも、競技プログラミングに熱心なLisperはほぼ皆無に見えるからです。競プロに興味のある人の中にも、そもそもLispに向いているジャンルなのかどうか不透明に思う人がいるかもしれません。
端的に言うと、わたしのレベルではパフォーマンスの面でデメリットを感じたことはありません。より高レートの状況でどうなるかは知りえないことですが、悲観する材料は特に見つかっていません。終わり。
……でもよいのですが、いくつかのポイントに絞って説明してみます。
○: 柔軟な構文
素早く・簡潔に・柔軟にDSLを生やすことにかけてはLispは今なお優れた言語であると言えるでしょう。競プロの文脈でもそれは役には立ちます。もっとも、そういったものは競プロにおけるパフォーマンスにさほど影響しないとも思います。競プロで大事なのは考察力です。
○: スピード
最良ではないが、悪くもないです。AtCoderにおける速さという観点で言語を雑に分類すると
- A群: C/C++/Rustなどの、システムプログラミングのための言語
- B群: OCaml/Haskellなど、ネイティブコードへのAOTコンパイルを前提とするその他の言語。Java/C#などの高速VMを持つ言語。
- C群: Python/Ruby/PHPなどのスクリプト言語
で性能はおおむねA>B>Cということになりますが（あくまで雑な分類です）、LispはBの中で速いほう、くらいの位置づけです。状況にもよるので絶対的な比較は難しいですが、速度面では「Java/C#と同程度かわずかに有利」くらいの認識を持っています。そして、Java/C#専のまま強くなる人は特に珍しくもありませんから、スピードの問題はさほど心配しなくてよいです。
実情を言うと、ビギナーコンテストの問題では正しいロジック（＝最悪計算量が制約に適っているロジック）で書けていればTLE(Time Limit Exceeded)することはめったにありません。TLEするのは、最適化が足りないからではなく、計算量の考察がおかしいからと思ってほぼ間違いないです。ほとんどの場合、最適化のための基本的な宣言すら必要ないと思います。それ以上のレベルの問題でも、SBCLが遅くて通せないとか、あるいは最適化しても制限時間ぎりぎりになるという事態に陥ったことは一度もありません。そもそもAtCoderではJavaで通らない問題は出題されないそうなので、SBCLで通せないというケースは考えにくいです。
CS AcademyやHackerEarthなど、事前コンパイルなしで--scriptで実行されるサイトではその分の時間（おおむね50ms～200ms程度）が上乗せされますが、このような環境でも問題になることはまれです。
△: 標準機能・ライブラリの充実度
Common Lispの標準ライブラリは貧弱です。平衡二分木もなければ、優先度付きキューも両端キューもないし、それどころかただのキューすらないので、あらゆるデータ構造をいちいち用意しなければなりません。 良い所もそれなりにはあって、多倍長整数が自然に扱えるのでオーバーフローの処理をちょっとくらいサボってもOKなのは悪くない点ですし、有理数や複素数も競プロでは活躍します。stringが単に文字の配列であるという時代遅れな仕様も、競プロではむしろ望ましいです。しかし、総合的に見てやや不十分なのは否めないでしょう。
もっとも、競プロerはどの言語を使っていてもけっきょくは自前実装のデータ構造を少しは用意することになるので、二分ヒープを自分で書くことくらいは誤差レベルとも言えます。ただ、自分でデータ構造を書く場合に、効率のために要素型で静的ディスパッチするようなコードを書くのが大変という別の問題はあります。CLにはパラメータ多相を自然に導入する方法の決定版がいまだにないので…… （競プロに限った話ではありませんが、ジェネリクスのデファクトがないのはCLのアキレス腱だと思っています。）
△: コンテストサイト・オンラインジャッジの選択肢
Common Lispは最大手のCodeforcesで使えませんし、もちろんTopCoderでも使えません。日本の競プロer御用達のAOJも対応していません。したがって、LisperはAtCoder、yukicoder、CodeChefを中心に利用し、Google Code Jamがあれば出て、足りなければCS Academy、HackerRankなどを使うことになります。それが不満ならC++やJavaを選んだほうがよいでしょう。ちなみにわたしはまあまあ不満です。
✕: 言語コミュニティの規模
Lisperの数が極めて少ないため、参考にできるコードがありません。AtCoderで400点以上の問題だとLispの提出はゼロであることが多いです。 困ります。もちろん、根幹のロジックを理解するために読むのはなんの言語でもよいので、C++やPythonの提出コードを見ればよいです。しかし、他人のコードを読むのは、整理された間違えにくい書き方を学ぶためという側面が強いので、言語が同じであるほうが参考にしやすいのも確かです。
もっとも、この問題はあなたが参加すれば解消されるとも言えます。ぜひやってみませんか。
いくつかの問題と解決策
実践で生じるトラブルとその回避方法を挙げます。「いくつか」と題しましたが、今のところ重要なものは最初の１つだけです。また、入出力関係の話題はまとめて後のセクションで扱います。
スタックサイズが足りない（重要度：◎）
SBCLのデフォルトのスタックサイズは2MBであり、コールスタックがこのサイズを超えるとエラーになります。（末尾呼び出しはジャンプに変わるので安全と思ってよいです。）
2MBというサイズですが、目安としては105の深さで再帰すると確実にcontrol-stack-exhaustedする、104ならたぶんOK、くらいです。深さを見積もって無理そうなら再帰を使わなければ良いのですが、DFSなどを手動スタック+ループで書くのはやや面倒と感じる人も多いでしょう。幸運なことに、この問題については解決策が確立しています。スタックサイズを増やしたSBCLを子プロセスとして呼び出せばよいのです。ファイルの冒頭に次のフォームを置きましょう。
#-swank
(unless (member :child-sbcl *features*)
(quit
:recklessly-p t
:unix-status
(process-exit-code
(run-program *runtime-pathname*
`("--control-stack-size" "256MB"
"--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
"--eval" "(push :child-sbcl *features*)"
"--script" ,(namestring *load-pathname*))
:output t :error t :input t))))
こうすればスタックサイズの大きいSBCLが代わりに処理してくれます。
- 終了コード絡みの処理は、子プロセスでエラーが起こった時に親プロセスのエラーにするためにやっています。そうしないと子プロセスでエラーが起こってもREと表示されなかったりします。
#-swankは必要ではありませんが、わたしはSLIMEでコーディングしているので、編集中にこのフォームが評価されないようにするために書いています。- 直接
--scriptで実行する仕様でも、コンパイルしてから実行する仕様でも、どちらでも通るようにしています。ほとんどのコンテストサイトで使えます。forkを呼ぶことになるので、DMOJのようにシステムコールを制限しているジャッジでは使えないようです。
- 使えることを確認: AtCoder、yukicoder、CodeChef、Toph、CS Academy、HackerRank、HackerEarth、SPOJ、Kattis、GCJ
- 使えないことを確認: DMOJ
- 今のところ256MBで足りなかったことはありませんが、128MBで足りなかったことはあります。スタックサイズが足りないとき、必ずしもREと表示されるわけではなく、TLE等になることもあるので気をつけましょう。
やや強引なハックではありますが、2年ほど使ってこの方法の欠陥らしきものは見つかっていません。数ms程度ロスしてわずかにメモリ消費が増えるだけですし、常に置いておいても特に問題ない程度のものです。
また、スタックサイズを書き換えてから新たにスレッドを作るという方法も考えられます:
(defun main () ...)
(setf (sb-alien:extern-alien "thread_control_stack_size" sb-kernel::os-vm-size-t)
(* 256 1024 1024))
(sb-thread:join-thread (sb-thread:make-thread #'main))
ただし、SBCLは起動後にスタックサイズを変更する機能を提供していないので「いちおう動く」だけではあります。最近のランタイムを眺めた限り、普通の使い方では壊れないだろうと思っていますが。（こちらもDMOJでは使えません。）
ベクタのソートが遅い（重要度：〇）
(declare (inline sort))しましょう。SBCLのsortはsb-ext:maybe-inlineなので、デフォルトではインライン化されません。 インライン化されないと、ベクタの要素型を考慮した静的ディスパッチがされないので、常識的なスピードが出ません。
ただ、SBCLのソートはベクタに対してはヒープソートなので、いずれにせよスピード重視ではないし、標準のソートは範囲指定ができないという問題もあります。 マージソートなりクイックソートなりを用意しておくのもよいかもしれません。
リストをsortする場合（マージソート）に関してはさらに(declare (inline sb-impl::stable-sort-list))が必要だったりします。（ソートが間に合うか不安なくらいに入力が大きいケースではリストで持たないほうがよいと思いますが。）
また、普段からSBCLのどの関数がどの場合にインライン化（インライン宣言やdefine-source-transformやdeftransformやdefine-vopによる変換）されるのか、型を考慮した最適化があるのかを気にしておきましょう。SLIME上なら、標準の関数に対してM-. slime-edit-definitionするとSBCLのソースにジャンプできます。
末尾の改行の扱いが一貫していない（重要度：△）
改行の扱いはコンテストによって異なるのですが、AtCoderのratedに出るだけならあまり気にする必要がないでしょう。あらゆるコンテストに出るなら、一般論としては以下のような指針があります。重要な順に
- 出力の末尾に改行がなかったり、余分な改行を入れた時に通るかどうかは不定と思ったほうがよいです。必ず正しい位置に正しい数の改行を送っておきましょう。
- 入力の改行コードが
#\Linefeed限定と思わないほうがよいです。
- 入力の末尾に改行があるという仮定を置かないほうがよいです。
2番目については、CodeChefのようにCRLFが入っているかもしれないことを明言しているサイトもあります。SBCLのread-lineはCRLFをうまく扱えないので、場合によってはstring-trimなどをする必要があるかもしれません。（とはいえ、この辺は「ちゃんとした」コンテストになるほど気にする必要性が下がっていくので、わたしもあまり真剣に対処していません。CodeChefでも最近のratedで困ったことはないです。）
CodeChef: ヒープサイズが小さすぎる（重要度：◎）
CodeChefではメモリは問題に関係なく4GBくらいまで使えるという情報がありますが、SBCLはなぜか--dynamic-space-size 48で起動されているのでそのままだと実用するのが厳しいです。上述のスタックサイズを増やすヘッダでヒープサイズも増やせます。（さすがにまずそうな仕様ですが、わたし以外のLisperを見たことがないので報告をさぼっています。）
AtCoder: MPFRが使えない（重要度：△）
double-float以上の精度が想定される問題はほとんど見ないですが、あれば役に立つことはよくあります。SBCLにはMPFRのモジュール（sb-mpfr）がありますが、AtCoderの環境ではrequireしてもlibmpfrが見つからなくて使えません。ジャッジ環境にlibmpfr自体は存在していて、requireの前に(sb-alien:load-shared-object "libmpfr.so.6")でロードするとよいです。自分が使っているヘッダの例はここにあります。
SBCLのバージョン間の差異について（重要度：△）
サイトによってSBCLのバージョンが異なるので、メモしておきます。該当のバージョンより上にある項目が注意点になります。重要な差異は特にないのですが、ジャッジのバージョンと近いものを使ったほうが細かいトラブルが起こりにくいです。Roswell等で切り替えるのがよいでしょう。
- AtCoder: version 2.0.3
- 負数に対する
modの返り値が正数であると推論されないことがあります。うまくいかない場合はtheを使いましょう。version 1.5.7でたぶん解決。
make-arrayで多次元配列を作る場合、element-typeの推論が正しくできないことがあります。sb-c:make-array-header*のderive-typeをコピペすれば解決しますが、そんなことをしなくても必要なら型を手打ちすればよいです。version 1.5.6で解決。- yukicoder: version 1.5.5
*read-default-float-format*にrationalを指定できない。version 1.5.2で解決。
rationalが使えるのはSBCL独自の仕様ですが、便利なので載せています
maphashが事前指定したサイズに対する${O}(N)$。詳細はここに書きました。version 1.5.5で過去に到達した最大要素数に対する${O}(N)$になりました。どちらの仕様でも、「maphashを何回も呼ぶけど合わせて${O}(N)$」みたいな場合に本当に${O}(N)$かどうか気を付けたほうがよいです。array-element-typeが定数伝搬しません。インライン関数の中で同じelement-typeの配列を作りたい場合等に困るかもしれません。array-element-typeのdeftransformをコピペすれば解決しますが、そんなことをしなくても必要なら型を手打ちすればよいです。version 1.5.0で解決。- CS Academy: version 1.4.16
- HackreRank: version 1.4.15
- CodeChef: version 1.3.13
- HackerEarth: version 1.3.1
SBCLはかなり昔から安定しているので、処理系が落ちるようなバグはまず無いと思っていいです。私自身は、AtCoderでdynamic-extent絡みのバグを踏んだことが1回ある程度です。（詳細を忘れました）
入出力のTips
大量の入出力をこなす場合（目安としては106文字くらいから）、全部(read)して一行ずつ書き出すような素朴すぎる方法を使うと無視できないロスになることがあります。このセクションでは効率をある程度考慮した方法を紹介します。しかし、ベストプラクティスと言えるような方法は特に確立していないので、以下のポイントを頭に入れつつ各自で好きなようにしましょう。
read-lineを高速化する（使用頻度: △）
read-lineは遅いとよく言われます。遅い理由として、read-lineは呼び出すたびにコンシングするからという説明を見たことがありますが、わたしの知る限りでは、律速しているのはマルチバイト文字を考慮したread-charです。AtCoderでは（おそらく）ASCIIしか出ないので、バイト単位で読んでsimple-base-stringのバッファに読みだす関数が役に立つかもしれません。SBCLの標準IOはbivalentなので、read-byteが使えます:
(declaim (inline read-line-into))
(defun read-line-into (buffer-string &key (in *standard-input*) (term-char #\Space))
(declare (inline read-byte))
(loop for c of-type base-char =
#-swank (code-char (read-byte in nil #.(char-code #\Newline)))
#+swank (read-char in nil #\Newline)
for idx from 0
until (char= c #\Newline)
do (setf (char buffer-string idx) c)
finally (when (< idx (length buffer-string))
(setf (char buffer-string idx) term-char))
(return (values buffer-string idx))))
term-charは入力終了を表す文字として使います。例えば#\Spaceの場合、1 2 3という行を読むとbuffer-stringを"1 2 3 "で上書きするわけです。buffer-stringの長さがちょうど5なら"1 2 3"になります。- SWANKの標準IOはbivalentでないため、SLIME上で編集している時は代わりに
read-charを使う必要があります。
- 読み込みの終了位置を多値で返しています。
(declare (sb-kernel:ansi-stream in))を宣言するとさらによいかもしれません。
上の関数はread-lineよりずっと速いですが、いちいちバッファを作るのが面倒であれば、サイズだけ指定してバッファは自動で用意するという方法もあるでしょう:
(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (term-char #\Space))
(let ((buffer (gensym))
(character (gensym))
(idx (gensym)))
`(let* ((,buffer (load-time-value (make-string ,buffer-size :element-type 'base-char))))
(declare (simple-base-string ,buffer)
(inline read-byte))
(loop for ,character of-type base-char =
,(if (member :swank *features*)
`(read-char ,in nil #\Newline) ; on SLIME
`(code-char (read-byte ,in nil #.(char-code #\Newline))))
for ,idx from 0
until (char= ,character #\Newline)
do (setf (schar ,buffer ,idx) ,character)
finally (when (< ,idx ,buffer-size)
(setf (schar ,buffer ,idx) ,term-char))
(return (values ,buffer ,idx))))))
- バッファサイズはコンパイル時に与えるべきなので、マクロにしました。
- （速度を気にしなければ）終了位置は
fill-pointerでコントロールしたいところではあります。読み込み時だけarray-storage-vectorを使う、とかいろいろやり方は考えられますが、今のところわたしはあまり頑張っていません。
read-lineとの比較ですが、105行以上のデータを読み込むなら200msくらいは得できるイメージです。最大で800msほど速くなるパターンを経験しています。
ただ、リードにしろパースにしろ、1文字ずつ読むならストリームから直接処理したほうが良くなりますし、read-sequenceなどを使う手もあるでしょう。以下にそのやり方も紹介しますが、read-lineや上の関数が役に立つこともよくあります。ストリングを介した行単位の処理は柔軟で、変則的な入力にも対応しやすいためです。
整数を高速に読み込む（使用頻度: ◎）
大量の整数を読み込んで処理する問題は頻繁に出ます。整数が$10^5$個を超えたあたりからreadに掛かる時間が無視できなくなってきます。
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
(declare (inline read-byte)
#-swank (sb-kernel:ansi-stream in))
(macrolet ((%read-byte ()
`(the (unsigned-byte 8)
#+swank (char-code (read-char in nil #\Nul))
#-swank (read-byte in nil 0))))
(let* ((minus nil)
(result (loop (let ((byte (%read-byte)))
(cond ((<= 48 byte 57)
(return (- byte 48)))
((zerop byte) ; #\Nul
(error "Read EOF or #\Nul."))
((= byte #.(char-code #\-))
(setq minus t)))))))
(declare ((integer 0 #.most-positive-fixnum) result))
(loop
(let* ((byte (%read-byte)))
(if (<= 48 byte 57)
(setq result (+ (- byte 48) (the (integer 0 #.(floor most-positive-fixnum 10)) (* result 10))))
(return (if minus (- result) result))))))))
(defun read-bignum (&optional (in *standard-input*))
(declare (inline read-byte)
#-swank (sb-kernel:ansi-stream in))
(macrolet ((%read-byte ()
`(the (unsigned-byte 8)
#+swank (char-code (read-char in nil #\Nul))
#-swank (read-byte in nil 0))))
(let* ((minusp nil)
(result (loop (let ((byte (%read-byte)))
(cond ((<= 48 byte 57)
(return (- byte 48)))
((zerop byte) ; #\Nul
(error "Read EOF or #\Nul."))
((= byte #.(char-code #\-))
(setq minusp t))))))
(mid-result 0)
(index-mod18 0))
(declare (fixnum mid-result)
((integer 0 19) index-mod18)
(integer result))
(loop
(when (= index-mod18 18)
(setq result (+ mid-result (* result #.(expt 10 18))))
(setq mid-result 0)
(setq index-mod18 0))
(let ((byte (%read-byte)))
(unless (<= 48 byte 57) (return))
(setq mid-result (+ (- byte 48) (* 10 (the (mod #.(expt 10 17)) mid-result))))
(incf index-mod18)))
(setq result (+ mid-result (* result (expt 10 index-mod18))))
(if minusp (- result) result))))
- 上と同様の理由で、SLIME上とそれ以外で入力方法を変えています。
read-fixnumは、読み込む整数がfixnum(=(signed-byte 63))とわかっている場合のreadの代替であり、わたし自身、ここに挙げた関数の中でもっとも頻繁に使っています。
read-bignumも用意してありますが、ほとんど使ったことがありません。AtCoderでは多倍長整数をそのまま扱えないと厳しい問題はそうそう出ないと思いますし、出ても1つ読むだけならreadが十分速いです。 どのくらい大きな整数を扱えるかは感覚で覚えるしかありませんが、目安としては10100000を読むのに200ms掛かると覚えておくとよいです。
出力をstring-output-streamにためる（使用頻度: ○）
出力データが大量にある場合、一行ずつ*standard-output*に出していくとロスが大きくなることがあります。そういう時はstring-output-streamを使いましょう:
(let ((out (make-string-output-stream :element-type 'base-char)))
(dotimes (i n)
(princ data out)
(terpri out))
(write-string (get-output-stream-string out)))
これは場合によってはかなり効きます。マクロ化したければ次のような感じでしょうか。（わたし自身はマクロではなくスニペットで解決しています。）
(defmacro with-buffered-stdout (&body body)
(let ((out (gensym)))
`(let ((,out (make-string-output-stream :element-type 'base-char)))
(let ((*standard-output* ,out))
,@body)
(write-string (get-output-stream-string ,out)))))
ただし、メモリ制限が厳しい場合は、string-output-streamに全部ためるとMLE(Memory Limit Exceeded)になってしまうことがあります。AtCoderの最近のコンテストでは256MB～1GB以外の制約を見たことがないので、この点を気にする必要はないと思いますが、過去問を解く際には問題になることがあるかもしれません。
小数を出力する（使用頻度: △）
SBCLのformatの~Fや~$は遅いです。特に、~,5Fや~5$のように小数点以下の桁数を指定した場合、出力だけで時間切れするレベルのボトルネックになったりします。
単純な解決策としてはwriteやprincをそのまま使うことが挙げられます。この場合、出力に指数表記が混じることになりますが、AtCoderは基本的には指数表記で回答しても問題なかったはずです。（初期の問題に通らないものがあった気もします。） ただし、指数の記号はもちろんeでないといけません。実数を扱う問題では、精度を考慮するとdouble-floatが必要になることも多いのですが、その場合は*read-default-float-format*を変更する必要があります:
CL-USER> (write 1.4f10)
1.4e10
CL-USER> (write 1.4d10)
1.4d10
CL-USER> (let ((*read-default-float-format* 'double-float))
(write 1.4d10))
1.4e10
なお、わたし自身はdouble-floatを通常の表記で高速に出力する関数も用意してはいます。AtCoder以外のサイトだと、writeでも遅すぎたり、あるいは出力桁数を制限しないと出力サイズが上限を上回ってしまったりという経験があります。
小数を高速に読み込む（使用頻度：✕）
小数を大量に入力する問題は意外にもまれです。SBCLのリーダーをいじったものをいちおう用意していますが、あまり試していません。
なお、readで読む場合、デフォルトではsingle-floatでパースされるので意図せず精度が落ちてしまう可能性はあります。これもやはり*read-default-float-format*を変更すればよいです。
小数を有理数として読み込む（使用頻度：✕）
「浮動小数点数の誤差の扱いが面倒だが有理数を使えば解決」という問題はたまにあります。しかし、入力も小数の場合は、readしてからrationalizeするとそもそもreadの時点で誤差が入るので、それについて考える必要が生まれます。SBCL 1.5.2以降であれば*read-default-float-format*にrationalが指定できるので、これを使うと何も考えなくてすむかもしれません。
