最初に明言しておきますが、この記事は bash による競技プログラミングを勧めるものではありません。
競技プログラミングのコミュニティー向けに ABC を bash で解いた話という記事（以下「元記事」と呼びます）を書いたのですが、折角 bash をネタにした記事を書いたのにこちらのコミュニティーに共有しないのはもったいないと思ったので、競技プログラミングとは無縁だった方々に背景知識を与える意味でこの記事を書くことにしました。「bash で競技プログラミングを始めてみよう」という体で書いていますが、実際のところは元記事に対する補足として機能することを狙っています。
競技プログラミングとは
そもそも競技プログラミング（competitive programming）という言葉を初めて耳にした方もいるかと思いますので、最初にその説明をします。一言で言えば、競技プログラミングとは「プログラミングコンテストでなされるようなプログラミング」を指します。
プログラミングコンテストでは、名前のとおりプログラミングの能力を競い合うわけですが、一口にプログラミングコンテストと言ってもさまざまなタイプのコンテストが存在します。大まかには以下の 3 つのカテゴリーに分けられます。
-
短期決戦型。短時間で複数の問題を解いていくタイプのコンテストです。たとえば 75 分で 3 問、あるいは 5 時間で 12 問といった具合です。基本的にすべての問題に想定解法（いわゆる「答え」）が存在します。アルゴリズムの組み立て能力が問われることが多いことから「アルゴリズムコンテスト」とも呼ばれます。TopCoder SRM、Codeforces、ACM-ICPC（日本語）、情報オリンピック（日本語）あたりが代表的といえるでしょう。AtCoder の一連のコンテスト群もこのカテゴリーです。そのほか、最近はさまざまな企業が採用の一環としてプログラミングコンテストを開催していますが、それらの大半はこのカテゴリーに属します。
-
長期対戦型。短いものでは数日、長いものでは 1〜2 か月ほどかけてひとつの問題に取り組んでいくタイプのコンテストです。ゲームの AI を作って対戦する、または何らかの最適化問題を解いて計算結果（最適化具合）ないし計算時間を競うというパターンがほとんどです。一応の解答例が用意されることはありますが、絶対的な「答え」は基本的に存在しません。TopCoder Marathon Match が超典型。SuperCon、ICFPC、SamurAI Coding などもこちらに含まれるといってよいでしょう。CODE RUNNER は時間は短いですが（3〜5 時間）内容的にはこちらにあてはまります。
-
ソフトウェアコンテスト。あるテーマに沿ってアプリケーションあるいはシステムを開発する、という形式のコンテストも多数存在します。基本的には審査員の審査によって優劣が決まります。プレゼンテーションなどプログラミング以外の能力が影響することも多く、ほかのカテゴリーとは毛色がかなり異なることから、プログラミングコンテストの範疇に含めない人もいます。U-22 プログラミングコンテスト、Imagine Cup（日本語）1などが典型的です。
競技プログラミングと言ったときは、短期決戦型が念頭にあると考えてもらってよいでしょう。短期決戦型のコンテストでは、与えられた入力（テストケース）に対して一定時間内（典型的にはテストケースごとに 1〜2 秒程度）に解を出力するようなプログラムをいかに素早く完成させるかどうかが競われます。ひとつのコンテストで複数の問題が与えられ、問題によって難易度に差があることが普通です。大学入試あたりをイメージしてもらうのがよいのかもしれません。
競技プログラミングでは C++、Java のどちらかを用いるのが一般的です。これは、特に ACM-ICPC において使用言語がこの 2 つ2に制限されていることの影響が大きいです。Python、Ruby などの LL 言語を用いる人もいますが、実行速度の面で不利があるため、選択されることはどうしても少なくなります。
〔追記：ACM-ICPC でも 2017 年度の世界大会から Python の使用が認められるようになりました。ただし、全ての問題が解ける保証はないことから、C++/Java が優位である状況は今後も続くと思われます。（2017-12-21）〕
実際に問題を解いてみる
アルゴリズムコンテストは、標準入力からデータ（テストケース）を読み込んで、何らかの計算をして、標準出力にその結果を出力する、というフォーマットになっていることがほとんどです。たまに、標準入出力ではなく特定のファイルへの読み書きが指示されることもあります。ちなみに TopCoder SRM はやや例外的で、特定の関数／メソッドを実装するよう要求されます。
ここでは、AtCoder Beginner Contest の積雪深差という問題を解くことにします。見てのとおり、2 つの整数を読み込んで、その差を出力するだけのとても簡単な問題です。入力例を見てみると、
15
10
というように、単に数値が 2 つ並べられています。JSON のような構造的な形式になっていないのは、外部のライブラリがなくても容易にデータを読み込めるようにするためです。bash でも JSON をパーズするとなったら一大事ですね。しかし、このような単純な形式になっているおかげで、
read h1
read h2
と read 文を 2 つ並べれば入力の読み込みは終わります。あとは、引き算をしてその結果を標準出力に出せばよいわけですから、
echo $((h1 - h2))
とでも書けばよいわけです。もちろん、
expr $h1 - $h2
と書いても構わないのですが、$((...)) を使えば * などでハマる心配がないのでこちらのほうがよいでしょう。新しいプロセスを起動するコストも節約できるという利点もあります（参考：そこまで遅くないShellスクリプトの書き方）。ちなみに、この記法はいわゆる POSIX 準拠のシェルであればどれでも使えます（参考：Shell Command Language）。
あっという間に話が終わってしまいました。わざわざ載せるまでもないと思いますが、積雪深差に対する bash による解答（の一例）は以下のとおりです。一応、shebang（最初の行）も書いておきましたが、実際には書く必要はありません。
#!/bin/bash
read h1
read h2
echo $((h1 - h2))
ほかの例については私の GitHub のレポジトリにあるリンクを参照してください。
参考：入力に関する補足
先に取り上げた問題では数値がそれぞれ個別の行に書かれていましたが、問題によっては、
15 10
というように複数の数値が空白区切りでひとつの行に書かれていることもあります。もっとも bash では
read h1 h2
のように変数を複数指定すればトークンに区切って読み込んでくれるので、これが問題になる場面は少ないでしょう。ちなみに、Python や Ruby だと少し厄介で、
h1, h2 = (int(s) for s in sys.stdin.readline().split())
h1, h2 = gets.split.map { |s| s.to_i }
のように split、map などをうまく使うことになります。
シェル芸で解く
標準入力から読んで標準出力に出せばよいので、いわゆるシェル芸を使うこともできます。たとえば、先の問題は
#!/bin/bash
xargs | sed -e's/ / - /' | xargs expr
exit 0
のようなスクリプトを書いても正解として受理されます。もっとも、この例は強引にシェル芸を使ったものであり、実際にはおとなしく read と echo を使ったほうがよいだろうと思います。罠（解答例）、カキ（解答例）のように、外部コマンド、シェル芸を使って解ける問題も中にはありますが、基本的にこれらの出番は少ないと思ってよいでしょう。
ちなみに、最後の exit 0 は、AtCoder のシステムではスクリプトが 0 以外のステータスコードで終了すると実行時エラー（RE）と判定されるため、それを回避するために足したものです。3
bash を使うと不利な点
遅い！とにかくこの一言につきます。どれだけ遅いかは元記事で言及しているのですが、競技プログラミングの経験者でなければ理解できないと思いますので、ここで改めて説明します。
プログラムの実行が制限時間内に終わるかどうかを見極めるときの重要な判断材料として、「ループのもっとも深い部分が何回ぐらい実行されるか」というものがあります。例として、以下のようなコードを考えます。
for (( i = 0; i < n; i++ )) ; do
for (( j = 0 ; j < n; j++ )) ; do
for (( k = 0 ; k < n; k++ )) ; do
hoge $i $j $k
done
done
done
見ての通りの三重ループであり、hoge の実行回数が問題になります。
C++、Java など「普通の言語」では、その実行回数が 1 億回（108 回）ぐらいであれば問題なし、10 億回（109 回）ぐらいになると制限時間内に終わる可能性は低い、と判断するのが一般的です。上記の例だと、n の値が 500 程度までであれば比較的安全だけれども（5003 = 1.25 × 108）、1000 あたりになるとかなり厳しいという判断を下します（10003 = 109）。
Python、Ruby などでは、実行速度の問題もあって目安が 2 桁ほど下がります。100 万回（106 回）はよいが 1000 万回（107 回）はまずい、といった具合です。
じゃあ bash ではどうかというと、この目安がさらに 2 桁下がります。1 万回（104 回）までは大丈夫だが 10 万回（105 回）はほぼ間に合わない。これは大変な制約で、簡単に解けるはずの問題が簡単には解けなくなります。たとえば、トリボナッチ数列 という問題。ほかの言語であれば、
declare -r M=10007
read n
a=0 # a[k]
b=0 # a[k+1]
c=1 # a[k+2]
for (( k = 1; k < n; k++ )) ; do
c_next=$(( (a + b + c) % M ))
a=$b b=$c c=$c_next
done
echo $a
に相当するコードを書くだけの問題です。しかし、上記の bash スクリプトは制限時間内に実行が終わりません。実際、問題文を読むと n の上限は 106 であり、これがそのまま反復回数の上限でもあるので、Python、Ruby では OK だけれども bash では NG ということになるわけです。
一応、この問題には（時間計算量の意味で）もっと効率のよい計算方法があるため、何とか bash でも解くことができます。この問題は別解が存在するだけましなほうで、それすらもないこともよくあります。
おわりに
ここまで読んでいただければ、元記事の内容も理解できるかと思います。もっとも、内容はわりと重複しています。
いずれにせよ、今まで競技プログラミングとは縁のなかった方々に対して、競技プログラミングについて少しでも知ってもらう、その一助となったならば、この記事を書いた意味があったと言えると思います。