日別アーカイブ: 2014年12月20日

Bashを使ってAtCoder Beginners Contestの簡単な問題を解いてみる

投稿日時: 投稿者:
返信

AtCoder Beginners Contest (ABC) において、A, B問題の速解きテンプレートを作成している人も多く見かけます。しかし、たいていはC++が主流となっています。C++では型の扱いなども問題もあるため、このような場面では型がいつの間にか変換されるような言語を用いたほうが楽であると考えられます。

さて、AtCoderでは多様な言語を選択可能で、”Bash”というものも選択可能です。ABCでもC問題以降のようなものをBashで解くのは面倒かと思いますが、A問題、B問題を速く特にあたってBashを利用することは現実味を帯びているとも考えられます。実際のコンテストの解答一覧で検索しても、実際にBashを利用してA問題やB問題を解いている参加者はちらほらいるようです。また、サーバー管理等でも、自分のやりたいことをBashで書けると便利です。

そのため、ABCのA問題、B問題のような問題を解くために必要となるようなコマンドの使い方をある程度調べながら考えていくことにします。

まず、ABC004 A問題「流行」を見てみます。入力が一つで、入力をN（整数）とした時2*Nを返します。入力が一つのシンプルなパターンでは、入力値を取り出すのに

`cat`

とすることができます。また、bash上での整数の四則演算にはexprが使えますから、

expr `cat` \* 2

とすると解けるはずですね（*はそのままだとワイルドカードとみなされ、カレントディレクトリのファイル名一覧として展開されてしまうためエスケープする必要があることに注意しましょう）。しかし、実際にこれを提出するとRuntime Error (RE)となります。これは、exprでは演算結果が0の時exit statusが1となってしまうため、異常終了とみなされてしまうことにあります。そのため、

expr `cat` \* 2
exit 0

とする必要があります。こうするとACとなります。

入力値が複数ある場合はまた考える必要があります。ABC005 A問題「おいしいたこ焼きの作り方」では、標準入力からスペースで区切られたxとyを読み取り、y/xの値（小数点以下切り捨て）を出力する必要があります。

readコマンドを利用すると、複数の入力を複数の変数に入れることができます。

read a b
expr $b / $a
exit 0

とすると解くことができます。

文字列処理の問題が出てくることもあります。ABC010 A問題「ハンドルネーム」では、受け取った文字列の末尾にppをつけます。
まずはsedを使って

sed -e 's/$/pp/'

とかやることで、正規表現一発で済む問題は解くことができます。

また、ABC005 A問題あたりで出てきたテンプレっぽい何かを使って

read a
echo $a'pp'
exit 0

という風にすることもできます。sedなど、標準入力から読み込むコマンドをつかいたければ

read a
echo $a | sed -e 's/$/pp/'
exit 0

などすることもできます。


climpet氏のこの発言に従えば、

read a b c
expr
exit 0

までを事前に用意しておき、問題を読んだら演算結果のみをexprの右に、もし数値演算でなければexprではなくsedなどにすればよいことになります。入力する量はC++で事前にテンプレートを作った場合とそれほど変わらないと思いますが、見た目がシンプルでどこに書くか探しやすいのと、数字ではなく文字列だった場合も対処が楽というメリットがあります。

また、ABC009 B問題「心配性な富豪、ファミリーレストランに行く。」というように、行単位で入力が与えられ、その処理がシンプルに終わる場合、Bashを使うと楽に解けることがあります。

一行目は要らないので（EOFを考えなくても入力できるようになるためのもの）tailコマンドを利用して取り除くことにします。あとは重複を取り除き、大きい方から2番めの数字を取り出すわけですが、それぞれはそういうことをしてくれるコマンドがあるので、

tail -n +2 | sort -n | uniq | tail -n 2 | head -n 1

とすることで楽に求められます。こういうのに慣れると（あとはcutやsedが使えると）目grepだと大変だがそんなに大規模でないログから必要な情報を取り出すのにも役立ちそうです。

また、ABC008 B問題「投票」では、それぞれの行の内容を集計し、最多のものを出す、ということをする必要があります。Bashで集計をするにも、 uniq -c とすると件数を出してくれます。あとはそれを処理すればいいので、

tail -n +2 | sort | uniq -c | sort -n | tail -n 1 | sed -e 's/^ *[0-9]* //g'

とすることができます。

今回はABCのA,B問題ということで基本的なコマンドの色々な挙動を調べつつ覚えていこう、というのが大半になりましたが、Bashでも短くコンパクトに意外と色々なことができます。サーバー上で色々やるために使っていると実際に使用するコードだとPerlなどの既にインストールされたLLのワンライナーを突っ込むこともありますが、ABCのA,B問題のいくつかではよくあるコマンドをパイプすることでBashがコンパクトに解けました。