AtCoder に登録したら解くべき精選過去問 10 問を Bash で解いてみた


# はじめに
$(n+1)$ 番煎じですが、@drkenさんの記事 [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067) に取り上げられている問題10問を Bash で解いてみました.
普通の解法は元記事参照のこと.
Bash で解ける計算量の目安として、$10^3$ 回程度の掛け算なら2秒に間に合います.

## 第 1 問: [ABC 086 A - Product](https://beta.atcoder.jp/contests/abc086/tasks/abc086_a) (100 点)

```bash
read a b
(( $(( a * b % 2 == 0 )) )) && echo Even || echo Odd
```

まず、入力は一行に固定数あるので、1つの `read` コマンドで読めばよい.
これで `$a` と `$b` に代入される.

`$(( ... ))` は Bash の拡張で中に整数の演算式が書ける. (整数に限ることに注意.)
また、この中では `$` が省略できる. `$(( a ))` は `$(( $a ))` と同じ [(「省略できる」・「同じ」は正確には嘘で代入する場合挙動が変わるので、寧ろ$を付けてはいけない)](#comment-13bccda95b2c9b07809c).
述語 `==` や論理演算 `&&` で bool を出力できるがこれは単に `1` または `0` を出力する.
`(( ... ))` は中に書いたシェルコマンドの出力結果が整数１個であることを期待し、非ゼロなら return code 0 で終了する.

```bash
command && echo y || echo n
```

はイディオムで、`if` 文と同義.

## 第 2 問: [ABC 081 A - Placing Marbles](https://beta.atcoder.jp/contests/abc081/tasks/abc081_a) (100 点)

```bash
tr -cd 1 | wc -c
```

入力文字列の中で `1` という文字がいくつあるかをカウントすればよい.
`tr -cd` で、それ **以外** の文字を削除し、 `wc` でカウントしている.

## 第 3 問: [ABC 081 B - Shift Only](https://beta.atcoder.jp/contests/abc081/tasks/abc081_b) (200 点)

何回2で割り算できるか、は、その整数を2進表示したとき、末尾にいくつ0が続くかに等しい.
2進表示するには例えば `bc` コマンドで

```bash
   bc <<< "obase=2; 24"
11000
```

などとすればよい.
末尾の 0 の個数を数えるために、例えば

```bash
   bc <<< "obase=2; 24" | sed 's/^.*1\(0*\)$/\1/' | tr -d '\n' | wc -c
3
```

と続ければ良い. のだが、手元だと確かに正しく動くのだが、提出してみると、サンプルすら通らない.
`bc` の挙動が違うのだろうか？ [(コメントからの情報: bcコマンドは禁止されている)](#comment-13bccda95b2c9b07809c)

結局2進表示するやり方はやめて、実際に2で試し割りする方法を取った.

```bash
for a in $(tail -1); do
    c=0
    while (( $(( a % 2 == 0 )) )); do
        a=$(( a / 2 ))
        c=$(( c + 1 ))
    done
    echo $c
done |
awk '
BEGIN { ans = 100000 }
{ ans = ans < $1 ? ans : $1 }
END {print ans}'  # take minimum
```

LLで書いてて、しばしば、入力の一部 (特に数列の個数) を捨てるというのがあって、
これもそうしていて、いきなり `tail -1` で初めている.

このforループは数列を吐いて、続く awk で最小値を取っている.

## 第 4 問: [ABC 087 B - Coins](https://beta.atcoder.jp/contests/abc087/tasks/abc087_b) (200 点)

```bash
read A; read B; read C; read X
for a in $(seq 0 $A); do
    for b in $(seq 0 $B); do
        c=$(( ( X - 500 * a - 100 * b ) / 50 ))
        [ 0 -le $c -a $c -le $C ] && echo y
    done
done | wc -l
```

初めに書いたように、1000回程度の掛け算をするくらいが限度なので、$O(ABC)$ は無理.
A,Bについてループを回して、Cは決定的に決めればよい.

入力は4行で渡されるので `read` を4回呼んでいる.

個数を数えるためにカウンターとしての変数を作らずに、代わりに何でもいいから何かを出力しておいて最後に `wc -l` で何回 (何行) 出力したかを見てます. こっちのがシェルスクリプトっぽい (諸説あります).

## 第 5 問: [ABC 083 B - Some Sums](https://beta.atcoder.jp/contests/abc083/tasks/abc083_b) (200 点)

これは本当に無理.

ある整数の桁の和は、シェル芸っぽくやるなら

```bash
echo 123 |                    # 123
    sed 's/./&+/g;s/+$//g' |  # 1+2+3
    bc                        # 6
```

とできる.
もちろん地道に書いても良いが、どちらにしろ時間が間に合わないので無理.
(あとやっぱりジャッジサーバー上の `bc` の挙動がよくわからない.) [(コメントからの情報: bcコマンドは禁止されている)](#comment-13bccda95b2c9b07809c)

## 第 6 問: [ABC 088 B - Card Game for Two](https://beta.atcoder.jp/contests/abc088/tasks/abc088_b) (200 点)

```bash
tail -1 | tr ' ' '\n' | sort -n | awk '
{ a=$1-a }
END {print a<0?-a:a}'
```

入力の内、個数を捨てて、数列部分を行に変換して awk に投げる.
awk の中で `a` という変数を初期化せずに使っているが、awk では未初期化の変数が右辺に登場しても、その型の初期値が勝手に使われる. この場合は `a=0` で初期化される.
差を取るのにどちらがAliceでどちらがBobなのか考えてないので、最後は abs を取って出力してる.

## 第 7 問: [ABC 085 B - Kagami Mochi](https://beta.atcoder.jp/contests/abc085/tasks/abc085_b) (200 点)

```bash
tail -n +2 | sort | uniq | wc -l
```

コレはいかにもシェルスクリプトっぽいタスク.

## 第 8 問: [ABC 085 C - Otoshidama](https://beta.atcoder.jp/contests/abc085/tasks/abc085_c) (300 点)

```bash
read N Y
Y=$((Y / 1000))

for A in $(seq 0 $N); do
    B=$(( ( (Y-10*A) - (N-A) ) / 4 ))
    C=$(( N - A - B ))
    if (( $(( B >= 0 && C >= 0 && 10*A + 5*B + C == Y )) )); then
        echo $A $B $C
        exit
    fi
done
```

$O(N)$ にする必要がある.

まず大きい数は嫌なので円はすべて1000で割っておく.
$A$ についてはループを取ることにして、

- $5B + C = (Y-10A)$
- $B + C = (N - A)$

$A$ が決まっていれば右辺は既知なので、この連立方程式は解ける.
解が適切な範囲に入ってることをチェックする必要がある.
割り算は整数の除算なので、改めて合計が $Y$ であることもまたチェックする必要がある.

## 第 9 問: [ABC 049 C - Daydream](https://beta.atcoder.jp/contests/abc049/tasks/arc065_a) (300 点)

```bash
if [ -z "$(sed 's/eraser//g; s/erase//g; s/dreamer//g; s/dream//g')" ]; then
    echo YES
else
    echo NO
fi
```

本来は `/eraser$/` を空文字列に変換したいが、繰り返し ($10^5/4$ 回程度) 適用する必要があって、遅そうなので、一発に変換させてしまう.
ただしその適用順は注意深く選ぶ必要がある.
(例えば `erase` を `eraser` より先に適用してはいけないのは明らか.)

`[ -z "$X" ]` は `$X` が空文字列 (zero-length) かどうかをチェックする.

## 第 10 問: [ABC 086 C - Traveling](https://beta.atcoder.jp/contests/abc086/tasks/arc089_a) (300 点)

$N$ が $10^5$ 程度で、$O(N)$ 掛かるのは目に見えているので、無理です.
一応書いたが、$10^3$ 程度なら通ると思います.

```bash
read N
T=0
X=0
Y=0

distance() {
    echo $((
    ($1 < $3 ? $3-$1 : $1-$3)
    +
    ($2 < $4 ? $4-$2 : $2-$4)
    ))
}

for _ in $(seq $N); do
    read t x y
    dist=$( distance $X $Y $x $y )
    dt=$(( t - T ))

    if (( $(( dist > dt || (dt - dist) % 2 == 1 )) )); then
        echo No
        exit
    fi

    T=$t
    X=$x
    Y=$y
done
echo Yes
```