'(you lisp me)

Lispって何だ

Lispで競技プログラミングしてみた話

もうすぐ2016年も終わりですね。
この1年の所感としては、色んな面で去年に比べて大分成長出来たかな、というところです。

今月始めはアドベントカレンダーの記事を書くのに大忙しでした。
調子に乗って5つも参加登録したせいなのですが、もしかしたらこの期間が一番成長に寄与したのでは…。
しかし1人で25日分の記事を書くような人もいるので、5つではまだ甘いようです。

せっかくなので、以下に書いた記事を並べておきます B^)

Common Lispに1年間入門して思ったこと - Qiita
過去に作ったノベルゲームエンジンの解剖 - Qiita
Common LispでOpenID Connect - Qiita
OCamlのSedlex+Menhir+LLVMでLispコンパイラを作ろうとしたが行き詰まった件 - Qiita
Common LispでGPUベクトルベースフォントレンダリング - Qiita

競プロやってみた

先日初めて、競技プログラミングというものをやってみました。
ちなみにアルゴリズム力には全く自信がありません。

競技プログラミングと言ったらAtCoderだろうということで、登録した後にまず過去問を解いてみました。
競プロ童貞なので、とりあえずAtCoder Beginner Contest(ABC)の方を何個か。

例えばこれなんかだと以下のコードでAC(accept)。

;;; AtCoder Beginner Contest 049-B Thin

(defun split (str delim)
  (let ((res (make-array 1 :element-type 'string
                           :fill-pointer 0
                           :adjustable t)))
    (loop for i from 0 below (length str)
          with start = 0
          when (eq (char str i) delim)
          do (vector-push-extend (subseq str start i) res)
             (setf start (1+ i))
          finally (let ((tail (subseq str start)))
                    (when tail
                      (vector-push-extend tail res))))
    res))

(let* ((in (split (read-line) #\Space))
       (h (parse-integer (aref in 0))))
  (loop for i from 0 below h
        for line = (read-line)
        do (format t "~A~%~A~%" line line)))

※ちなみにsplit関数は予め別のファイルに用意して、問題に手を付ける度にコピペして使いまわしています。
※自前でsplitを実装すると結果をlistで返してしまいがちですが、多くの場合は速度低下に繋がって、競プロではTime Limit Exceededとなってしまうので配列で返すようにしましょう。

まあこんな感じに、Common Lispだからと言って大きなディスアドバンテージがあったりはしないようです。
本来なら事前に色々なマクロを組んでガチガチに固めた状態で臨むべきなのでしょうが、初回なので普通に組んでみました。

コンテストに出てみた

丁度良いタイミングで土日にコンテストが控えていたので、両方共参加してみました。
※普段はAtCoder Regular Contest(ARC)とABCが毎週土曜日に行われています。

まずは第3回 ドワンゴからの挑戦状 予選に参加しました。
僕にとってはこれがリアルタイムで参加する初めてのコンテストとなりました。

一応過去問も解いてはみたのですが、これがなかなか難しい。難易度はARCぐらいでしょうか。
結果は1/5問で、A問題しか解けませんでした。B問題に膠着しすぎたのかな…。
目標はB問題まで解くことだったので結構悔しかったです。

翌日はAtCoder Beginner Contest 050に参加しました。
こちらは初心者向けのコンテストなので、それほど苦戦はしませんでした。
が、しかしD問題だけ解けず…解説を見てもいまいちピンと来ません。おそらくこの辺りが自分のアルゴリズム力の閾値なのでしょう。
ちなみにABC全体でもD問題を解けた人は居なかったようです…。

あと、Common Lispで参加したのはどのコンテストを見ても僕だけでした:<

感想

思ったより楽しかったです。特に自分のコードに点数が付くのが新鮮でした。
まだ競プロを始めたことで新たに得た教訓はありませんが、今後も暇さえあれば挑戦してみたいと思います。

Lispで競プロをやるにあたっての奨め

  • 出力はformatで、複数の時は(format "~{~A~^ ~}~%" list)などを活用
  • splitはarrayで返す
  • dotimes・loopマクロを活用
  • 使える武器(マクロ)は予め作っておく

近況

そういえば最近lemを使い始めました。

github.com

ずっとVimを使ってきたのでEmacsキーバインドはあまり馴染まないのですが、動作が軽快なので結構気に入ってます。
何よりCommon Lisp製なのが良いですね！その恩恵でREPLも内蔵されていて良い感じです。
そのうちプラグインも作ってみたいな。