はじめに

米田優峻さんの書籍『競技プログラミングの鉄則』を購入したので、シェル芸（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関連の記事もあります。