Help us understand the problem. What is going on with this article?

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
cympfh
有意義、躍進など
http://cympfh.cc/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away