ABC176を振り返る(C問題まで)
ついに茶色に復帰した。とはいえギリギリなのでまたすぐ落ちる気はする…
A - Takoyaki
これは焼く回数の計算に小数点の切り上げが必要。愚直に分岐してもよい。
read n x t
if((n%x==0))
then
echo $((n/x*t))
else
echo $(((n/x+1)*t))
fi1発で計算したい場合は次のようになる。
read n x t echo $(((n+x-1)/x*t))
B - Multiple of 9
各桁の総和が9の倍数であるかを判定したいが、本ブログで何回も触れてきたように2*10^5のループを足し算していくのはちょっと危険。別の方法を考える。
ここではuniqを使い、それぞれの数字が何回現れるかを計算する。
fold -1 | sort | uniq -c
これを入力例3で試すと、次の出力が得られる。
7 0
6 1
10 2
10 3
8 4
7 5
8 6
6 7
11 8
13 97個の0、6個の1…といった表記に出来る。
次にこの結果を配列に入れると、a=(7 0 6 1 ...)となる。あとはこれを使って各桁の総和を計算すればよい。
a=(`fold -1 | sort | uniq -c`)
l=${#a[@]}
s=0
i=0
while((i<l))
do
s=$((s+a[i]*a[i+1]))
i=$((i+2))
done
((s%9==0)) && echo Yes || echo Nolには配列の長さが入っている。これでACできる。
改善点
さらに考えると、0と9はどれだけあっても総和が9の倍数であるかの判定に影響しないため、最初に削除してしまう方法もある。そこまで大幅な時短にはならないが考え方としてはありかもしれない。
C - Step
今回の肝。B問題のようにループを省略する手段がなく、愚直にループを回していくしかない。ところが200000のループはBashにとってかなりの難敵である。
例えばこう書くとTLEになる。
read n
read -a a
s=0
min=${a[0]}
for x in ${a[@]}
do
((x<min)) && s=$((s+min-x)) || min=$x
done
echo $siについてのループを回してループ内でa[i]を参照するよりも、配列の中身を直接xに入れて処理した方が明らかに早くなる(配列を参照しないで済むため？)
ところがこれでも足りない。
そこで、そもそも配列を使わないという方法を考える。上のコードではread -a aのように配列とみなして入力を受け取っているが、この-aを消し、あくまでも1つの文字列として入力を受け取ろうと考える。
文字列であっても、空白区切りであれば1つずつループを回すことが可能である。つまり、配列時のfor x in ${a[@]}と文字列時のfor x in $aで同じループが実現できる。配列に入れて展開する時間を省けるという利点がある。
ただしこの問題では、最初の基準点としてa[0]を調べる必要が出てくる。そこで、cutコマンドを使って空白区切りで表されるデータの1つ目だけを切り取ることで取得する。
長々と書いたが、要は配列を使うことそのものが時間を食ってしまっているため、どうにか配列を使わないで考えるとギリギリ時間が足りたのである。
read n
read a
s=0
min=`echo $a | cut -d' ' -f1`
for x in $a
do
if((x<min))
then
s=$((s+min-x))
else
min=$x
fi
done
echo $sa[0]はcut -d' ' -f1で代用している。これは、空白区切りで表されたフィールドの1つ目を切り取るという意味である。時間は983ms。
余談
では他の200000回ループも似たように攻略できるかといったらそうではなく、アルゴリズム上どうしてもループ内で配列の参照という形を取りたい場合はこの方法が使えない。現時点での攻略法は適用できる問題がかなり限られてしまうため、別の方法も考えていきたいところ。
ちなみにB問題をこの方法で実装すると次のようになる。ここでは入力をfold -1で1文字ずつ区切り、そのままforループに突っ込んでいる。
s=0
for x in `fold -1`
do
s=$((s+x))
done
((s%9==0)) && echo Yes || echo No意外と500ms以内でACできてしまった。B問題については少し考えすぎだったかもしれないが、結果として0WAで通せたので良かったとする。
