はじめに
$(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 を出力する.
(( ... )) は中に書いたシェルコマンドの出力結果が整数１個であることを期待し、非ゼロなら 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$ 回程度) 適用する必要があって、遅そうなので、一発に変換させてしまう.
ただしその適用順は注意深く選ぶ必要がある.
(例えば erase を eraser より先に適用してはいけないのは明らか.)
[ -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