AtCoderはじめた

アルゴリズムの勉強も兼ねて2019年末からAtCoderをはじめました。今はレーティング208の灰色コーダーです。

AtCoderのレーティング推移

12/22のAtCoder Beginner Contest 148 (以下ABC) からRatedなコンテストは全参加で6回出場しました (ただし2回は運営上の問題でUnratedになった)。ABCに参加するとC問題までは安定して解けるがD問題が解けるか解けないかくらいの感じなので、続けていれば緑コーダーくらいはいけるのかなーと思っています。もうちょい勉強してその上の水色くらいは目指したいところです。

参加所感

AtCoderの問題はアルゴリズムを知っているかだけでなく、そもそも問題文を正しく読んで、どういったアルゴリズムを適用しうるかから考える必要があります。まあ競プロやっている人は有名アルゴリズムは一通り知っているわけで、どう書けば解けるか自明な問題だと差が出ないだろうから当たり前といえば当たり前のような気がしますが、このため単純な能力測定というよりはゲーム的な要素が高くなっています。

問題文を読み間違っていたり、適用するアルゴリズムを間違って実装に走ってしまったりすると致命的になる感じです。なのでアルゴリズムやプログラムの勉強だけでなく、ある程度の過去問での反復練習で慣れておく必要がありそうです。この辺は好き好きありそうですが今のところ楽しく参加できています。

Common Lisp

一番得意なCommon Lispでコンテスト参加しています。

提出状況を見ると他に5〜6人くらいがCommon Lispで参加しているようです。けれど、ABCのE, F問題を解けるくらいの人は1人 (sansaquaさん) くらいしかいなさそうです。この方、Qiitaの記事でCommon Lispで競プロするTipsを紹介してくれていてとても参考になります。コンテスト終了後に回答を見て学ばせてもらったりしています。

qiita.com

懸念点

Common LispでAtCoderに参加する懸念点もいくつかあります。

たとえば、AtCoderでオンラインジャッジされるSBCLは1.1.14という6年前にリリースされたバージョンです。さらにテストは sbcl --script で実行しているためコンパイル時間も実行時間として扱われます。そのためCommon Lispの真価が発揮できていないという声もちらほら見聞きします。*1

けれど僕が参加してみた感じとしては、これらは些事です。少なくとも、ABCのDを解けない程度の僕のレベルではあまり問題にはなっていません。

TLE (実行時間オーバー) になって「まじかよ…Common Lispはもうだめか…」と思ったときもあるにはありますが、終了後に解答を見ると、そもそも効率の悪いアルゴリズムで実装していたと気づきました。まっとうな実装なら最適化オプションをつけなくてもすんなり通ります。その経験があってから、TLEになったらAtCoderが悪いというより自分が悪いのだと思って反省しています。

解いていて提出したらWA (不正解、ただしスタックサイズが足りずに死んだデバッガ出力が認識されている) とかもありました。が、これは解決策があるので再帰を使うときは定型文一個貼り付けるのを忘れないようにしようということでまあよいと思います。

もちろん、バージョンは新しいほうがいいですし、コンパイルフェーズもあったほうがいいのですが、今のところは僕は不自由していないです。

使ってるもの

競プロ参加する上で開発環境を整えたので、簡単にそのツール紹介をして終わろうと思います。エディタはNeoVimです。

• online-judge-tools
  • CLIでの問題とサンプルのDLとテスト実行、提出までできてしまう最高のプロダクト
• atcoder-cli
  • 上記と組み合わせてAtCoderに特化して簡易なコマンドインターフェイスを提供している
  • あんまり使いこなせていない
    • コンテスト開始時に acc new abc151 するためだけに使ってる
• getac ※自作
  • テスト実行
  • online-judge-toolsでもテスト実行できるけど、存在に気づかずに作ってしまった
  • 捨てようと思ったがテスト結果の出力がコンパクトだったり、WA時のdiffの色付けがあったり自分好みなので継続利用している
• vim-quickrun
  • NeoVimで簡単にテストを走らせるために使ってる
  • <C-x><C-x> で getac が走って結果を表示してくれる
• neosnippet.vim
  • (Neo)Vimの定型文補完プラグイン
  • 簡単な問題は早解きでレーティングがかなり変わるので入力時間短縮のために入れた
  • kyopro<C-k> とやるとテンプレート展開する
  • その他 la<C-k> で lambda 式に展開するように設定したりした
    • 普通に業務コーディング効率も上がりそう
• smartcd
  • 特定のディレクトリにcdしたときに実行するコマンドを設定できるシェルのツール
  • AtCoderの実行環境に合わせて ros use sbcl-bin/1.1.14 するのを忘れないように入れてる

あとツールではないですが、AtCoderのコンテスト開催に気づけるように「from:atcoder コンテスト開催のお知らせ」のTwitter検索をIFTTTでメールで飛ばすようにしています。公式のカレンダーが機能していないので…。GAS使えば自動でGoogleカレンダーに入れるとかもできるかもしれない。 → した。AtCoder Contest Calendar

その他、便利ツールがあったら教えてください。

*1:https://blog.3qe.us/entry/2019/05/26/235835 など