Edited at

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

More than 1 year has passed since last update.


はじめに

$(n+1)$ 番煎じですが、@drkenさんの記事 AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ に取り上げられている問題10問を Bash で解いてみました.

普通の解法は元記事参照のこと.

Bash で解ける計算量の目安として、$10^3$ 回程度の掛け算なら2秒に間に合います.


第 1 問: ABC 086 A - Product (100 点)

read a b

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

まず、入力は一行に固定数あるので、1つの read コマンドで読めばよい.

これで $a$b に代入される.

$(( ... )) は Bash の拡張で中に整数の演算式が書ける. (整数に限ることに注意.)

また、この中では $ が省略できる. $(( a ))$(( $a )) と同じ (「省略できる」・「同じ」は正確には嘘で代入する場合挙動が変わるので、寧ろ$を付けてはいけない).

述語 == や論理演算 && で bool を出力できるがこれは単に 1 または 0 を出力する.

(( ... )) は中に書いたシェルコマンドの出力結果が整数1個であることを期待し、非ゼロなら return code 0 で終了する.

command && echo y || echo n

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


第 2 問: ABC 081 A - Placing Marbles (100 点)

tr -cd 1 | wc -c

入力文字列の中で 1 という文字がいくつあるかをカウントすればよい.

tr -cd で、それ 以外 の文字を削除し、 wc でカウントしている.


第 3 問: ABC 081 B - Shift Only (200 点)

何回2で割り算できるか、は、その整数を2進表示したとき、末尾にいくつ0が続くかに等しい.

2進表示するには例えば bc コマンドで

   bc <<< "obase=2; 24"

11000

などとすればよい.

末尾の 0 の個数を数えるために、例えば

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

3

と続ければ良い. のだが、手元だと確かに正しく動くのだが、提出してみると、サンプルすら通らない.

bc の挙動が違うのだろうか? (コメントからの情報: bcコマンドは禁止されている)

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

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 (200 点)

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 (200 点)

これは本当に無理.

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

echo 123 |                    # 123

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

とできる.

もちろん地道に書いても良いが、どちらにしろ時間が間に合わないので無理.

(あとやっぱりジャッジサーバー上の bc の挙動がよくわからない.) (コメントからの情報: bcコマンドは禁止されている)


第 6 問: ABC 088 B - Card Game for Two (200 点)

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 (200 点)

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

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


第 8 問: ABC 085 C - Otoshidama (300 点)

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 (300 点)

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$ 回程度) 適用する必要があって、遅そうなので、一発に変換させてしまう.

ただしその適用順は注意深く選ぶ必要がある.

(例えば eraseeraser より先に適用してはいけないのは明らか.)

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


第 10 問: ABC 086 C - Traveling (300 点)

$N$ が $10^5$ 程度で、$O(N)$ 掛かるのは目に見えているので、無理です.

一応書いたが、$10^3$ 程度なら通ると思います.

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