はじめに
米田優峻さんの書籍『競技プログラミングの鉄則』を購入したので、シェル芸（Bash）を用いて問題を解いていこうと思います。ただし、Bashは処理速度がCやC++などと比べるとそこそこ遅いため、解けない問題はC++で解きます。また、応用問題まで解いていると大変なので、今のところ応用問題は飛ばすことにします。よろしくお願いいたします。
Amazonリンク
問題集（AtCoder）
序章 : 競技プログラミング入門
「競技プログラミングとは何か」ということや、コンテストの種類、本書の構成などが書かれている章です。また、GitHubにソースコードも公開されているとのことです。参考にしましょう。さらに、AtCoder上で自動採点も行えるとのことです。利用しましょう。
1章 : アルゴリズムと計算量
アルゴリズムと計算量についての説明があります。読みましょう。
1.1 : 導入問題
まずは簡単な問題から始まります。
A01 - The First Problem
readで標準入力から値を受け取り、$(())の中で計算、echoで標準出力しましょう。
read n
echo $((n*n))
1.2 : 全探索（1）
全探索問題を解いていきます。
A02 - Linear Search
問題の流れとしては全探索を行う処理を書くべきですが、Bashにはgrepがあるので使っちゃいましょう。まず、入力の値が一行になっているのでsedでスペースを改行に置換します。その後、Xの値をgrepで探します。最後に三項演算子的な感じでYes or Noを出力します。
三項演算子的な処理は以下のように書けます。
コマンド && 最初のコマンドが正常終了時に実行するコマンド || 最初のコマンドが異常終了時に実行するコマンド
参考記事↓
提出コードは以下の通りです。
grep -qは@kkddさんのコメントを参考にいたしました。ありがとうございます！
read n x
sed 's/ /\n/g' | grep -q ^$x$ && echo Yes || echo No
1.3 : 全探索（2）
引き続き全探索の問題を解いていきましょう。
A03 - Two Cards
Bashでは標準入力を配列に入れたいとき、以下のように書きます。
declare -a p=()
read p
参考記事↓
提出したコードは以下の通りです。二重のfor文を使って全通りの足し算を行い、echoで出力します。そして、その出力の中からgrepでKの値を探して、Yes or Noを出力します。
read n k
declare -a p=() q=()
read p
read q
for i in ${p[@]};do
for j in ${q[@]};do
echo $((i+j))
done
done | grep -q ^$k$ && echo Yes || echo No
1.4 : 2進法
2進法に関する問題を解いていきます。
A04 - Binary Representation
bcを使って10進数を2進数に変換しましょう。
参考記事↓
obase=2で出力を2進数に指定、ibase=10で入力を10進数に指定します。その後にNの値をbcに渡します。また、2進数の値を10桁で出力する必要があるのでprintfを使ってあげましょう。
read n
printf '%010d\n' $(echo "obase=2;ibase=10;" $n | bc)
1.5 : チャレンジ問題
1章の最後に少し難しいチャレンジ問題があります。
A05 - Three Cards
この問題では計算量がO(N^2)となる解法が紹介されていますが、残念ながらBashではそれでも間に合いません。
以下がTLEするコードです。
read n k
a=0
for((i=1;i<=n;++i));do
for((j=1;j<=n;++j));do
d=$((k-i-j))
if((d>=1&&d<=n));then
a=$((a+1))
fi
done
done
echo $a
仕方がないのでBash(C++)で解いていきましょう。
cat << 'EOF' >> a.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, a=0;
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
int d = k-i-j;
if(d >= 1 && d <= n) ++a;
}
}
cout << a << endl;
}
EOF
g++ -o a a.cpp
./a
純粋なBashでも解ける方法があれば、教えていただけますと幸いです。
おわりに
本記事は、随時更新していきます。
シェル芸と『競技プログラミングの鉄則』とAtCoderとAtCoder Problemsに感謝を。
ありがとうございます。
楽しいです。
コメントいただいた改善点
@kkddさん（2023/01/09）
-
grep -qで不要な出力を無しに - 三項演算子的な構文についての正確な説明
ブログの移転
新しくブログを始めました。AtCoder関連の記事もあります。