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

はじめに

2015 年末に bash で始める競技プログラミング（?）という記事をネタ半分で書いたのですが、どういうわけか百花繚乱！なないろ言語で競技プログラミングをする資料まとめ（@drken）の中で入門資料に認定されてしまったので、ひとつ釣られたつもりになって AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～にある問題をすべて bash で解きました。実際に解いてみると bash の良い点も悪い点もよくわかるセットだったので、私の解答をひととおり解説しようかと思います。

なお、この記事では、読者と対して以下のことを想定します。

• とりあげる問題についてはすべて解法を知っている
• シェルスクリプトをある程度書くことができる
• よく使われるコマンド（grep とか sed とか）もわかっている

bash の文法については適宜説明を入れますが、必要に応じて GNU Bash manual などを参照してください。

問題自体の説明はいちいちしません。リンクだけ貼っておくので各自読んでください。

ルール

極端に言えば、単に Python や Ruby を呼び出すだけのスクリプトも「bash スクリプト」と主張することができるわけですが、それだと bash とは何だったのかとなってしまうので、次のような制限を設けています。

• 外部コマンドは /bin にあるものだけ
• awk と bc は基本使わない

0. Practice A - Welcome to AtCoder

問題文

read a
read b c
read s
echo $((a+b+c)) "$s"

read に複数の変数を指定すると空白で区切って読んでくれます。

算術演算は expr ではなく $((...)) を使いましょう。そうすれば * がファイル名に展開されて大変な目に遭うこともありません。なお、$((...)) は展開の一種なので、上の解答例のように echo に引数として渡すことなども可能です。

1. ABC 086 A - Product

問題文

read a b
if (( (a * b) % 2 == 0 )); then
  echo Even
else
  echo Odd
fi

シェルで比較というと、典型的には test あるいは [ ... ]、bash に多少詳しい人であれば [[ ... ]] あたりが知られているところでしょうが、シェルで算術比較をしたいときは ((...)) を使うのが正解です。

別解

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

個人的にはこのように書くことが多いです。

&& と || をいわゆる三項演算子のような感覚で用いていますが、挙動には癖があるので、真似をされるときはこの式の意味をきちんと理解してから使ってください（参考）。

2. ABC 081 A - Placing Marbles

問題文

tr -Cd 1 | wc -c

1 の個数を数えるだけの問題なので、これだけです。ちなみに tr の -d は指定文字を削除する、-C は指定を反転するためのオプションで、両者をあわせると指定されていない文字は全部削除するという意味になります。このとき改行も削除されるので、あとは wc で文字数を数えるだけでよいです。

3. ABC 081 B - Shift only

問題文

read n
read -a a

for (( count = 0; ; count++ )); do
    for (( i = 0; i < n; i++ )); do
        (( a[i] % 2 != 0 )) && echo ${count} && exit
        a[i]=$(( a[i] / 2 ))
    done
done

bash にも配列はあります。さらに、read コマンドに -a オプションをつけると、勝手に空白区切りで読み出して、配列として変数に格納してくれます。添字はたいていの言語と同様に 0-origin です。

まるで C/C++ のような for 文が現れたりと、これが本当に bash だろうかと疑われるかもしれませんが、れっきとした bash スクリプトです。C/C++、あるいはその近隣言語を知っていれば理解は可能でしょう。

別解

tail -1 | factor | cut -d : -f 2 | sed -e's/[0-9][0-9][0-9]*//g' | \
    tr -Cd '2\n' | sort | head -1 | tr -Cd 2 | wc -c

少しずるいですが、Linux にはたいてい factor というコマンドが存在するので、これを利用する方法もあります。これは、引数として、あるいは標準入力を通して正の整数を指定すると、その整数を素因数分解した結果が出力してくれるコマンドです。実行例を見てもらったほうが早いかもしれません。

$ factor 8 12 40
8: 2 2 2
12: 2 2 3
40: 2 2 2 5

# Same as above.
$ echo 8 12 40 | factor

入力の先頭行が邪魔になりますが、tail を用いれば 2 行目だけを取り出せます。あとは何とかして 2 の個数が一番少ない行を見つけ、その個数を報告できればよいわけです。シェル芸人としての腕の見せ所ですね。

あまり安直にやると 23 のような数字に足をとられることになりますので注意してください（経験者は語る）。解答例では 2 桁以上の数字を先に消すことで対処しています。なお、cut、sed、tr とつなぎましたが、まとめてひとつの sed だけで片付けることもできます。

4. ABC 087 B - Coins

問題文

read A
read B
read C
read X

count=0

for (( a = 0; a <= A; a++ )); do
    for (( b = 0; b <= B; b++ )); do
        for (( c = 0; c <= C; c++ )); do
            (( a * 500 + b * 100 + c * 50 == X )) && (( ++count ))
        done
    done
done

echo ${count}

ただの三重ループなので特に説明はいらないと思います。ただ、これで一応通るのですが、bash は実行がとても遅いのでちょっとヒヤヒヤしながら結果を待つことになります。実際、実行時間は 1 秒を少し超えます。

ちなみに、この「実行が遅い」ということが bash で問題を解くうえでの最大の厄介事です。過去の記事にも書きましたが、よくある「内側の繰り返しが 10^8 回以下ならば基本大丈夫、10^9 回に届くとかなり危険」みたいな見積もりは、bash だと 4 桁も下がって「10^4 回は大丈夫だけど 10^5 回は往々にして厳しい」となります。これだけ遅いと、時として ABC の C 問題すらまともに解けないなんてことが起こります。実際、後半の問題でこの実行が遅い問題に悩まされることになります。

別解

read A
read B
read C
read X

count=0

for (( a = 0; a <= A; a++ )); do
    for (( b = 0; b <= B; b++ )); do
        c=$(( (X - a * 500 - b * 100) / 50 ))
        (( c >= 0 && c <= C )) && (( ++count ))
    done
done

echo ${count}

$X$、$a$、$b$ がわかれば $c$ は一意に決まります。これならば bash でも 30 msec ぐらいで動くので安心できます。

5. ABC 083 B - Some Sums

問題文

read n a b
ans=0
for (( k = 1; k <= n; k++ )); do
    dsum=0
    for (( j = 0; j < ${#k}; j++ )); do
        (( dsum += ${k:j:1} ))
    done
    if (( dsum >= a && dsum <= b )); then
        (( ans += k ))
    fi
done
echo ${ans}

$N$ の上限が 10000 だったのではじめは身構えてしまいましたが、結局はこれで十分でした。

${#k} は変数 k に格納された文字列長、${k:j:1} は変数 k の j 文字目から長さ 1 文字の部分文字列にそれぞれ展開されます。bash では文字列と数値の区別がないに等しいので上のようなコードが許されます。

ちなみに配列変数 a に対して ${#a} とすると文字列長ではなく要素数になります。

6. ABC 088 B - Card Game for Two

問題文

read # N
ans=0
sign=1
for ai in $( tr ' ' '\n' | sort -nr ); do
    (( ans += sign * ai ))
    sign=$(( -sign ))
done
echo ${ans}

もちろんソートするわけですが、bash でソートしたいとなると基本的に sort コマンドに頼らざるを得ません。そこでまずは空白区切りの列を改行区切りに変換することになります。本当は xargs -n 1 がお手軽でよいのですが、要素ひとつにつき echo を 1 回実行することになるため要素数が多いと容易に TLE の原因になりえます（この問題は $N$ の上限が 100 なので実は大丈夫ですが）。なので、上の解答例のように tr を用いるのがよいでしょう。

解答例では先頭行を読み飛ばすために read を使いましたが、もちろん先の問題と同じように tail を使っても構いません。

7. ABC 085 B - Kagami Mochi

問題文

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

まるでシェル芸の基礎確認のような問題です。

最初の行を読み飛ばすところだけトリッキーですが、GNU 系の tail であれば上のように「2 行目以降を出力」という指定が可能です。ワンライナーにこだわりがなければ、前の問題と同じように read で読み飛ばすという手もあります。

sort コマンドの -n はなくても通るはずです。ちなみに -u というオプションもあるようで、これを用いれば uniq が不要になります。

8. ABC 085 C - Otoshidama

問題文

# **** TLE ****
read N Y
for (( x = 0; x <= N; x++ )); do
    for (( y = 0; x + y <= N; y++ )); do
        z=$(( N - x - y ))
        if (( x * 10000 + y * 5000 + z * 1000 == Y )); then
            echo $x $y $z
            exit
        fi
    done
done
echo -1 -1 -1

公式の解説、元記事などによれば、$x$、$y$、$z$ の全部でループを回すと制限時間内に計算が終わらないので $z$ だけは計算で求めましょう、というのが想定解法らしいですが、bash ではそれすらも間に合いません！

幸いにして、この問題では比較的簡単に時間計算量を下げられるので、それに頼ることにします。

O(N) で計算する

read N Y
(( Y /= 1000 ))
for (( z = Y % 5; z <= N; z += 5 )); do
    x5=$(( Y + 4 * z - N * 5 ))
    x=$(( x5 / 5 ))
    y=$(( N - x - z ))
    (( x >= 0 && y >= 0 )) && echo $x $y $z && exit
done
echo -1 -1 -1

$x$、$y$、$z$ のうち 1 つを決めると、合計枚数と合計金額という 2 つの制約があるため、残りの 2 変数の値は一意に決まります。したがってループはひとつで足ります。解答例では 5000 円未満の端数は千円札でしか支払えないことを活かすため $z$ でループを回していますが、ほかの変数でも構いません。

（詳しい説明）

話を簡単にするために $Y' = Y / 1000$、つまり千円を単位として考えることにします。

五千円未満の端数は千円札でしか支払えないので、千円札の枚数は $z = 5k + (Y' \bmod 5)$（$k$ は整数）でなければならないことがわかります。そこで $z$ に関してループを回すことにします。

$z$ の値をひとつ決めると、残りの $x$、$y$ について 2 つの条件が発生します。

\begin{cases}
  x + y = N - z \\[1ex]
  10x + 5y = Y' - z
\end{cases}

ここから $5x = Y' + 4z - 5N$ を得ます。ここで $z$ に関する前提条件から

Y' + 4z = (Y' - z) + 5z = \bigl\{ Y' - (Y' \bmod 5) \bigr\} - 5k + 5z

は必ず 5 の倍数になるので、何も考えずに 5 で割ってしまってよいです。$x$、$z$ が決まったので、残りの $y$ は計算で求まります。

ここまでやると bash でも 10 msec 未満で終わります。

O(1) で計算する

declare -r INV=(0 7 5 3 1 8 6 4 2) 

read N Y
(( Y /= 1000 ))

if (( Y >= N )); then
    y=${INV[(Y - N) % 9]}
    x=$(( (Y - N - 4 * y) / 9 ))
    if (( x >= 0 && y >= 0 && x + y <= N )); then
        echo $x $y $((N-x-y))
        exit
    fi
fi
echo -1 -1 -1

公式の解説でもわずかに触れられていますが、その気になれば定数時間で計算することもできます。

（解法の説明）

同じく $Y' = Y/1000$ として考えます。

全部千円札で払うとすれば $Y'$ 枚必要になるはずです。もちろん $N$ 以上のはずなので（でなければ支払不能）、その一部を一万円札または五千円札で支払うことにします。一万円札を 1 枚使うと、千円札は 10 枚減るので、紙幣の合計枚数は都合 9 枚減ることになります。同様にして、五千円札を 1 枚使うと、紙幣の合計枚数は 4 枚減ります。全体で $(Y' - N)$ 枚減らす必要があるので、 $9x + 4y = Y' - N$ を満たすような $x$、$y$ を 1 組求めればよいことになります。

なるべく一万円札を使ったほうが枚数制限に引っかかる可能性が下がるので、五千円札の利用は最小限にすることにしましょう。$9x = Y' - N - 4y$ なので、右辺が 9 の倍数となるように $y$ を選びます。これは $(Y' - N)$ を 9 で割った余りと $4y$ を 9 で割った余りが等しいと言い換えることができます。この余りの値と $y$ の関係はあらかじめ計算しておくことができます。つまり、

• $(4 \times 1) \div 9 = 0 \ldots 4$ なので、$(Y' - N)$ の余りが 4 ならば $y = 1$
• $(4 \times 2) \div 9 = 0 \ldots 8$ なので、$(Y' - N)$ の余りが 8 ならば $y = 2$
• （途中は省略）
• $(4 \times 8) \div 9 = 3 \ldots 5$ なので、$(Y' - N)$ の余りが 5 ならば $y = 8$
• $(Y' - N)$ の余りが 0 のときはもちろん $y = 0$

解答例の INV はこうして得られた値になっています（INV[4]=1、INV[8]=2、…）。剰余群を知っていれば $4y \equiv Y' - N \pmod 9$ より $y \equiv 7(Y' - N) \pmod 9$ であると計算してもよいです（7 は 4 の逆元）。

$y$ が決まれば $x$ も決まり、したがって $z$ も決まります。

declare -r は読み取り専用の変数を定義するための決まり文句です。もっとストレートな readonly というコマンドもあります。

9. ABC 049 C - Daydream

問題文

egrep -q '^(dream|dreamer|erase|eraser)+$' && echo YES || echo NO

もちろん grep で一発です。世の中には正規表現というものがある、ということを知らしめてやりましょう。

括弧などの前にバックスラッシュを置くのが面倒だったので egrep のほうを使いましたが、もちろん普通の grep でも大丈夫です。

別解

read s
[[ "$s" =~ ^(dream|dreamer|erase|eraser)+$ ]] && echo YES || echo NO

実は bash にも正規表現とマッチするための演算子があります。すでに文字列が変数に格納されているときはこちらのほうがスマートですが、今回の場合は標準入力に与えられた文字列をそのまま渡すだけなので (e)grep でよいだろうと思います。

参考

# **** TLE ****
read s
while [[ ! -z "$s" ]]; do
    case "$s" in
        *dream)   s="${s%dream}"   ;;
        *dreamer) s="${s%dreamer}" ;;
        *erase)   s="${s%erase}"   ;;
        *eraser)  s="${s%eraser}"  ;;
        *)        echo NO; exit    ;;
    esac
done
echo YES

後ろから貪欲法という方針をあえて実装すると上のようになりますが、文字列が長いことも影響してか、ループ 1 回あたりで 10 msec とかのオーダーで時間がかかり、とても制限時間内には処理が終わりません。bash を用いるときは bash らしい方法で解きましょう。

10. ABC 086 C - Traveling

問題文

# **** TLE ****

read n

t0=0 x0=0 y0=0
for (( i = 0; i < n; i++ )); do
    read t1 x1 y1
    dx=$(( x0 < x1 ? x1 - x0 : x0 - x1 ))
    dy=$(( y0 < y1 ? y1 - y0 : y0 - y1 ))
    dt=$(( t1 - t0 ))
    if (( dx + dy > dt || (dx + dy) % 2 != dt % 2 )); then
        echo No
        exit
    fi
    t0=$t1 x0=$x1 y0=$y1
done

echo Yes

出ました！入力列自体に 10 万個の要素があると bash では基本的にどうしようもありません。この問題のきちんとした正答を bash だけで書くのは無理だと見ています。

乱択法（だいぶ頑張った）

read n

(( n > 10000 )) && M=16384 || M=32768

while read t1 x1 y1; do
    (( RANDOM < M )) &&
    (( d = (t1-t2) - (x1>x2 ? x1-x2 : x2-x1) - (y1>y2 ? y1-y2 : y2-y1),
       d < 0 || d % 2 )) && echo No && exit
    read t2 x2 y2 || break
    (( RANDOM < M )) &&
    (( d = (t2-t1) - (x1>x2 ? x1-x2 : x2-x1) - (y1>y2 ? y1-y2 : y2-y1),
       d < 0 || d % 2 )) && echo No && exit
done
echo Yes

今のところ bash で TLE にならない一番まともな解法はこれです。$N$ が大きいときは一部だけ調べることにして時間を節約します。頑張って余計な代入を減らすなどした結果、半分までは調べることができるようになりました。これでも一応通ります。

RANDOM は 0 から 32767 までの乱数を与える特殊変数です。

嘘解法

read n
for (( i = 0; i < n; i++ )); do
    read t x y
    if (( x + y > t || (x + y) % 2 != t % 2 )); then
        echo No
        exit
    fi
done
echo Yes

おーい、@chokudai、入力がガバガバだぞー。

どのくらいまでコードを削れば bash でも TLE にならないか調べているときに偶然見つけたものです。この解答例は以下のような入力例に対して正しく動作しないので、本来は WA と判定されるべきなのですが、驚いたことに AC という返事が返ってきました。

3
10 5 5
20 0 0
30 15 15

$t=20$ の時点で $(0, 0)$ にいるので、$t=30$ の時点までに $(15, 15)$ に移動するのは不可能です。したがってNo と判定すべきですが、上の解答例は Yes と出力してしまいます。

awk に魂を売る

declare -r PREPROCESS='
BEGIN {
    t = 0; x = 0; y = 0
}
{
    print ($1 - t) " " ($2 - x) " " ($3 - y)
    t = $1; x = $2; y = $3
}'

read

while read dt dx dy; do
    if (( d = dt - ${dx#-} - ${dy#-}, d < 0 || d % 2 )); then
        echo No
        exit
    fi
done < <(awk "${PREPROCESS}")
echo Yes

仕方がないので awk で前処理をして bash の負担を軽くすることにします。絶対時刻、絶対座標の代わりに、直前のプランからの相対時刻（時間）および相対座標（移動方向＋距離）を入力として与えることにすると、スクリプトが少し単純化されてどうにか時間内に計算が終わります。

<(...) は標準入力を与えられたコマンドの出力に置き換えるものです。パイプを用いない理由は某企業が公開している Shell Style Guide の Pipes to While という項を読んでください。

awk に移行する

BEGIN {
    t = 0; x = 0; y = 0
    ans = "Yes"
}
(NF >= 3) {
    dt = $1 - t; dx = $2 - x; dy = $3 - y
    if (dx < 0) { dx = -dx }
    if (dy < 0) { dy = -dy }
    if (dx + dy > dt || (dx + dy) % 2 != dt % 2) {
        ans = "No"
    }
    t = $1; x = $2; y = $3
}
END { print ans }

いっそのこと全部を awk で書くとこんな感じになります。すっきりしていますね。