ABC を bash で解いた話
この記事は Competitive Programming Advent Calendar 2015 の 10 日目の記事です。
はじめに
ここ最近はあまりやっていないのですが、ABC（AtCoder Beginner Contest）の過去問を bash で解くという謎の縛りプレイをやっています。一応、競技プログラマとしての経験があるにはあるので、普通の言語でよければ ABC の問題ぐらいは解けるのですが、bash 縛りとなると一筋縄ではいきません。それでも 30 問以上は解いていて、C 問題、D 問題もそれなりに解いています。
実際に書いたコードに関しては、こちらのリポジトリ（github.com）にリンクがあるのでそちらを参照してください。Wiki にも少しだけページがあって Tips 等が書いてあります。この記事ではもう少し背景寄りの話をしようかと思います。
あちこちで話はしている気がするので、聞き覚えのある人もいるかもしれません。
きっかけ
ある日、通勤電車の中だったか、TL を眺めていたらこんな Tweet が。
すごい→ Bashで競技プログラミング #w8lt #w8lt4 #w8lt http://t.co/usUsyEhk1Q
— 高橋 直大(chokudai) (@chokudai) 2015, 7月 30僕は bash が大好きなので「おおっ」と思ったわけです。ちょっとしたライバル心みたいなものも芽生えました。ところが、実際にその中身を見てみると、
- 単に awk または bc を呼んでいるだけの解答が結構な割合で存在する
- 使われている文法がおしなべて古い（後述）
- スライドに嘘が書いてある（「ビット演算がない」とあるが実際は存在する）
というように、bash を十分に使いこなしていない様子がうかがえました。「bash の実力はこんなものではない。」ライバル心（?）はむしろある種の危機感へと変わっていったのであります。
〔おことわり〕この記事に jmatsu さんを貶める意図はありません。むしろ一方的に攻め立てる感じになってしまって申し訳ないです。
文法が古い？
いわゆる if 文などで条件判定をするとき、
[ "$a" = hoge ] [ "x$a" = xhoge ]
のように書く人が多いと思いますが、bash では
[[ "$a" = hoge ]]
のように書くべきだろうと思います。[ ... ] は基本的にコマンドなので引数解釈が発生しますが、[[ ... ]] は bash のビルトインなので空文字列の扱いといった罠にはまることがありません。
コマンド展開も `...` ではなく $(...) のほうが便利だし安全です。前者はネストできませんが、後者ならばできます。途中に括弧があっても適宜解釈してくれるので「うっかり括弧を閉じてしまった」といった心配をする必要もありません。
算術演算に expr を使うのもやめるべきでしょう。代わりに $((...)) という組み込みの機能があるのでそちらを使いましょう。expr だと整数は 32 ビットになりますが、$((...)) ならば 64 ビットです。言うまでもなく、競技プログラミングでこの差はとても重要です。
ほかにもいろいろありますが、とりあえずこのぐらい抑えておけば十分でしょう。ちなみに、[[ ... ]] は bash にしかありませんが、$(...) と $((...)) は (d)ash にもあります。
〔追記〕何かの理由で expr は 32 ビットで計算されると勘違いしていましたが、改めて確認したところ、手元でも AtCoder の環境でも 64 ビットで計算されるようです。ここにお詫びして訂正します。（12/15）
使っているコマンド
厳格にやるならば bash の内部コマンドのほかは使わないということになるでしょうが、さすがにそれでは何かとしんどいので、いかにも /bin に入っていそうなコマンドは基本的に使っています。ただ、awk、bc に関しては、無制限に許すとそれだけで事足りてしまうので、以下のような制限を設けています。
- awk は引数抽出（e.g.
'{ print $3 }'）に限って使用を認める - bc は小数計算と多倍長計算に限って使用を認める
もっとも bc はあまり積極的には使っていません。出力として小数を要求されていても、値を適当に嵩上げするだけでたいてい事足ります。たとえば、値が 0.5 単位で変わるのであれば、常に値を 10 倍（あるいは 2 倍とか）しておけばいいわけです。固定小数点と言うこともできますね。AtCoderプログラミング講座（解答）はこの方法で解いています。
シェル芸
bash といえばいわゆるシェル芸…と言いたいところですが、実のところ出番はあまりありません。ほとんどのスクリプトは C++/Java と相互に直訳できるのではないかと思うほどで、そういったスクリプトでは bash らしさはまったく見当たりません。禁止された数字に対するこの解答は典型的な一例です。
もちろん、時にはシェル芸が使えることもあって、jmatsu 氏のスライドにも紹介されているような罠（解答）、回転（解答）などは好例です。あと、満点解法ではないけれどトランプ挿入ソートの部分点解法も bash でなければできない芸当だろうと思います。
つらみ
何がつらいって遅くて遅くてしょうがない。よくある計算時間の見積もりとして「繰り返しが 10^8 回ぐらいならば基本的にセーフ、10^9 回だとかなり危険」みたいなものがあると思います。Ruby とか Python とかだと 2 桁ぐらい下がって 10^6〜10^7 あたりが判断基準になりますね。bash ではさらに 2 桁下がります。つまり 10^4 は大丈夫だけど 10^5 は基本的にまずい。
これはとても大変です。トリボナッチ数列（解答）は普通にループを回していたのでは間に合わないので、行列の累乗という何ともオーバースペックな手法にお出まし願うことになります。感雨時刻の整理（解答）は入力に 10 万個の要素があって読み込むことすらままならないので、sed などで前処理をして bash で処理する入力の量を減らす必要があります。トランプ挿入ソート（解答）の満点解法となるともはや手段がなくて bc に魂を売らざるを得ません。
ほかには実数演算がないという問題がありますが、これは前出のとおり回避策があるし、いざとなれば bc を使えばいい話なので、ABC に限ればあまり困ることはありません。あとは文法に癖があるというぐらいで、道具立ては（ABC のレベルの問題に限れば）だいたい揃っているという印象があります。
やってよかったこと
易しく解ける問題でも解法をきちんと考えるようになったおかげで、以前に比べると、アルゴリズムを考えることに比重のあるタイプの問題がいくらか多く解けるようになった気がします。あと、有用かどうかは別として、今までほとんど知られていなかった知見が得られたというのは悪い話ではないでしょう。
