CommonLispでAtCoderを100問くらい解いたので纏める

Nov 15, 2020
Lisp

とりあえずAtCoderを100問(A 60問、B 30問、C 10問)くらい解いたので纏めておく。ちなみにブログ記事も100記事目。

CommonLispでAtCoderをやってる人は10人以下というくらい超マイナー言語だけど普通に解き易いし他言語と比べて高速且つ簡潔に記述できるので本当に良い。

atcoder problems で進捗を確認できるのはとても便利。

競技プログラミングでCommon Lispを使っている人とこれから使うかもしれない人のためにやAtCoderはじめたといった記事はあるけど、難しいことはわかんないのでとりあえず始めてみた。

エディタ

やはりEmacs、断トツで使い勝手が良い。

直にLemにしてもいいなと思っている。

適当にjunk fileを作成してslimeを起動して適当に書くようにしている。

Emacsで競技プログラミング | ojのラッパーパッケージを書いた話のようにojを使おうかなと思ったが、個人的にはoj自体がイマイチ使い勝手が悪いので見送った。

入出力

CommonLispでの入出力は簡単で大体2種類。この辺を使えば大体の問題はいける。

入力が固定長の場合

A B C K

(defun main (a b c k))

(main (read) (read) (read) (read))

入力が可変長の場合

N
A1 A2 ... AN

(defun main (lst))

(main (loop :repeat (read) :collect (read)))

組み込み函数

CommonLispは標準でかなり多くの便利な組み込み函数を提供してくれている。mapやreduceなどは重宝するが、一番便利なのはloop macro。

loop macroがあれば正直ほとんどの悩みが解決するレベルで便利だ。

ライブラリ

takeokunn/atcoder に自作のmacroや函数を追加するように運用しはじめた。

例えば、loop macroを二重に書くのが嫌だったので nested-loops というmacroを作り、簡潔に記述できるようにした。

(defmacro nested-loops (vars values &rest body)
  (if vars
      `(loop :for ,(first vars) :from ,(car (first values)) :to ,(cdr (first values))
             :do (nested-loops ,(rest vars) ,(rest values) ,@body))
      `(progn ,@body)))

(nested-loops (x y) ((1 . 2) (1 . 2))
              (princ (* x y)))

他にも、anaphoric macroや文字列操作など汎用的に使えそうなものを纏めてorgで管理している。

(defmacro areduce (form list &key initial-value)
  `(reduce #'(lambda (it-accum it) ,form) ,list :initial-value ,initial-value))

(areduce (* it-accum it) '(1 2 3 4) :initial-value 1)

使用時はペタペタ貼り付けて運用している。

また、takeokunn/atcoderにさくっと登録できるように以下のようなsnippetも作成した。

# name: atcoder
# key: atcoder
# --
** ${1:name}
*** definition
    #+name: $1
    #+BEGIN_SRC lisp :noweb yes
    #+END_SRC
*** usage
    #+BEGIN_SRC lisp
    #+END_SRC

問題の解き方に関して

コーディング部分で詰まることはそんなにないが、そもそもどういう実装をすれば良いのか、どういう発想で問題に取りくむべきなのかがよくわからないことが多い。

問題を解く量を増やす必要があるのが今の課題。

AB問題は全然問題ないが、計算量が必要な問題から途端に時間がかかってしまうということがわかった。

macroをもっとうまく使って効率よくコードを書けるようにしたい。