ABC175を振り返る(A,C問題)

ちょっと調子が良かったと言える回。Bash相性は良かったり良くなかったりした。

ABC175

茶色復帰も少しずつ見えてきている。

A - Rainy Season

atcoder.jp

せいぜい入力が3であることを考慮すると、RRRがあるか→RRがあるか→Rがあるかを順番にif文で見ていってもよい。
これがコンテスト当時のAC解。

read s
if echo $s | grep -q RRR
then
    echo 3
elif echo $s | grep -q RR
then
    echo 2
elif echo $s | grep -q R
then
    echo 1
else
    echo 0
fi

grep -qは見つかったか見つかってないかだけを判定し、出力はさせたくないときに使える。

また、こう長ったらしく書かなくても、

grep -Eo "R+" | head -1 | tr -cd R | wc -c

でもいける。これは"R+"(Rの1回以上の繰り返し)が入力にあればそれを出力し、その1行目のRの文字数を出力している。これが4文字以上であればsortなどが必要になってくるが、3文字までなのでこれで良い。
多分文字数カウントなどに関してはもっと効率よい手段がある。

B - Making Triangle

atcoder.jp

公式の解説では「Nは200までなのですべての組を確認できる」とあるが、Bashでは確認できない。

read n
n=$((n-1))
a=(`tr ' ' '\n' | sort -n`)
c=0
for i in `seq 0 $n`
do
    for j in `seq $((i+1)) $n`
    do
        for k in `seq $((j+1)) $n`
        do
            if((a[i]+a[j]>a[k]))
            then
                if((a[i]!=a[j]&&a[j]!=a[k]))
                then
                    c=$((c+1))
                fi
            else
                break
            fi
        done
    done
done
echo $c

この3重ループはTLEする。他の方法が無いか考えておく。

C - Walking Takahashi

atcoder.jp

まず求める値が絶対値であることを踏まえ、xは絶対値を取って正の値になるようにする。
次に、kステップあれば原点を越える一歩手前まで到達できるかを計算し、到達できないのであればひたすら原点に向かい続けた際の距離が解となる。ここで、この条件分岐は移動回数による不等式で求める。距離による不等式if((k*d<x))ではオーバーフローしてしまうので気を付ける(1敗)。
到達できる場合、残りの移動回数を計算する。この回数が偶数なら一歩手前が解、奇数なら原点を1回だけ超えた場所が解となる。原点近くを行って帰って…と繰り返し移動することを考えると導出できる。
こう考えるとループが一切必要ないため、Bashにとってはかなりありがたい問題であった。

read x k d
x=$((x>0?x:-x))
c=$((x/d))
if((k<c))
then
    echo $((x-d*k))
else
    echo $(((k-c)%2?d-(x-d*c):x-d*c))
fi

これでAC。変数cには原点を越える手前までの移動数が入る。