Competitive Programming (その2) Advent Calendar 2015の4日目の記事です
注意、ショートコーディング(コードゴルフ)のテクニックっぽい話はほとんど載っていません
ちょっと2ヶ月ぐらいAtCoderでショートコーディングをがんばってみました。楽しかったので頭の体操としておすすめです
7月に宇宙ツイッタラーXさんのAtCoder ProblemsにAtCoderの問題ごとの最短コードの獲得数のランキングが追加されました
ショートコードを意識して書いているのは10人もいないっぽいので「結構簡単に上位には入れそう」と思って7月から9月の2ヶ月間ぐらいがんばってみました
最初は自分のショートコード数は1問しかなかったけど1位の人でも100問ぐらいしかなくて、1日がんばるだけで1桁順位になれました
AtCoderで1日コードゴルフをして1桁順位になったので満足した。ワンライナー力とショートコーディング力がちょっとついたけど、何に活かせばいいんだろう…… http://t.co/zdx0qM9RQW pic.twitter.com/uH2IXCoGNk
— 無限猿(id:sucrose)@24月病 (@Scaled_Wurm) 2015, 7月 20
AtCoderは他人の提出が見られるので、今の最短の他人のコードをなんとかして1バイト縮めることができれば最短になれます(マナー的にはよくないかも知れませんが(?)
他人のコードを見るのはかなり勉強になるので、最初は「自分でショートコーディングする」「最短あたりの人のコードを見る」「自分のコードを直す」って感じで進めてました
他人のコードを見ると知らないコマンドや関数、文法がたくさん見つかって面白かったです
テクニックをいろいろメモしていたら150行ぐらいになりました
はまってくると数バイト縮めるアイディアを思いつくだけで脳汁が出ます
Beginner ContestのA,B問題などは簡単なので電車通勤の合間にスマホで解くとかできて時間のない社会人にも優しいです(?)
通勤で暇だったのでスマホでAtCoderのショートコーディングを2問解いた(不毛な作業
— 無限猿(id:sucrose)@24月病 (@Scaled_Wurm) 2015, 8月 7
一時はショートコード数140問まで行きました
そういえばAtCoderのショートコード数140になった http://t.co/zdx0qM9RQW pic.twitter.com/ygLuUVCJdK
— 無限猿(id:sucrose)@24月病 (@Scaled_Wurm) 2015, 9月 21
最近はやってないのとPerlゴルフガチ勢の%20(x20)さんの参戦などで109問に減っています
というわけでAtCoderで上位に入れない自分でも、ショートコーディングでは簡単に上位に入れたりして楽しかった、という話でした
本気でやれば1桁順位ぐらいはすぐにいけると思うのでぜひ試してみてください
ランキングができてかなりやる気が出たので宇宙ツイッタラーXさんに感謝!
AtCoder Problemsは他にもいろいろ機能がついていて便利です
おもしろいこととか微妙なハマりどころとか
どの言語がよいか
AtCoderではいろんな言語が使えますが、競技プログラミングなので高速な言語でないと解けない問題があり基本C++で解かれているのが多いです。難しい問題だと最短コードの提出でも最初に大量にマクロが定義されていたり短く書こうとしていないのがほとんどなので、改行を消したりするだけで最短が取れると思います
ショートコーディングをちゃんとしているのだとRuby、Perl、Pythonなどやシェルスクリプト(Bash)が強い感じ
自分は普段はPythonをメインで使っているのですが、ショートコーディングの為にRubyを勉強しました
Perlはかなり短くかけて強いのですが、慣れてないのでまだ他人のコードが読めません><
AtCoder Problemsに載ってた最短コードを適当にクロールして言語別にカウントしました
言語 | ショートコード数 |
---|---|
C++ | 281 |
Ruby | 236 |
C++11 | 149 |
Python | 82 |
Perl | 82 |
Bash | 73 |
C | 29 |
Text | 21 |
Python3 | 15 |
Haskell | 13 |
Java | 6 |
Scala | 2 |
C++14 | 2 |
PHP | 1 |
クロールに使ったソースコード(pyqueryを入れないと動かない)
# -*- coding: utf-8 -*- import pyquery import time import collections if __name__ == '__main__': link_list = pyquery.PyQuery(url='http://kenkoooo.com/atcoder/') for elm in link_list.find('tr td:nth-child(7) a'): a = pyquery.PyQuery(elm) href = a.attr('href') if 'http' not in href: continue solution = pyquery.PyQuery(url=href) lang = solution.find('table:eq(0) tr:nth-child(4) td:nth-child(2)') print lang.text() time.sleep(1.5)
1行毎に言語が出力されるのでuniq -cでカウントして一部手で修正
sort temp.txt | awk '$0=$1' | sed '/^$/d' | uniq -c | sort -nr | awk '$0=$2" "$1'
ついでにpyqueryの使い方の記事を昔書いたので貼っておくsucrose.hatenablog.com
見ていて一番おもしろかったコード
AtCoder Regular ContestのD問題を3バイトで通すSubmissionです
Submission #476526 - AtCoder Regular Contest 026 | AtCoder
改行が2バイトになるか1バイトになるか
改行コードがCR+LFではなくLFだけのコードをsubmitするというしょうもないテクニックでショートコード数を稼ごうと思ったらちょうど昨日leafmoon(cielavenir)さんに先を越されていた(´・ω・`)
— 無限猿(id:sucrose)@24月病 (@Scaled_Wurm) 2015, 8月 24
普通にブラウザから提出すると改行が2バイトになる(環境による?)ので手元で改行が1バイトのファイルを作って下記のツールで提出しましたshindolog.hatenablog.com
変な入力
古い問題だと入力の改行などがおかしい場合がある
入力の末尾に改行が有っても無くても対応できる書き方をすれば AC なのだが、末尾に改行があることを想定してゴルフしているので、こういう場合は困る。
— %20|残り21912日 (@henkoudekimasu) 2015, 9月 23
簡単な問題は正解のチェックがゆるい
A問題などは、題意を満たさないコードでもACになることがあるので、これを利用すると短く書けたりします
@evima0 大したのではないですが末尾に改行がなくても通るとか、nanで通る http://t.co/anJiXpieKU 大文字と小文字を気にしないでも通る http://t.co/7crP97RdAM 文字の途中まで見れば通る http://t.co/zD5nOsZKFX
— 無限猿(id:sucrose)@24月病 (@Scaled_Wurm) 2015, 9月 20