ABC177を振り返る(A,C問題)
レートこそ耐えたものの、不勉強が強く表れた回。
A - Don't be late
まあやるだけ。T*Sだけ進むことが出来るので、あとはその値がDに届くか届かないかで判定する。
read d t s ((t*s>=d)) && echo Yes || echo No
B - Substring
無理。最善は尽くした。
read s
read t
ls=${#s}
lt=${#t}
min=$lt
for i in `seq 0 $((ls-lt))`
do
ss=${s:i:lt}
c=0
for j in `seq 0 $((lt-1))`
do
if [ ${ss:j:1} != ${t:j:1} ]
then
c=$((c+1))
if((c>=min))
then
break
fi
fi
done
min=$((min<c?min:c))
done
echo $minすべての部分文字列についてループしていく方法でTLE。forループはやはり厳しいか。
過去のABCで似たような問題が出ていたが、あれは2つの文字列長が同じ状態であった。今回は部分文字列を列挙していかないといけないため前回同様にはいかず。これ解法あるのだろうか…
C - Sum of product of pairs
今回の戦犯。ちょっと思いつくのに時間がかかった。
正直( (a[0]+a[1]+a[2]+...+a[n-1])^2-(a[0]^2+a[1]^2+...+a[n-1]^2) ) / 2で解く気満々だったが、mod演算の関係で割れない。
この場合取れる戦略は2つで、「mod演算できる計算式を別に考える」か「この計算式を実現させる方法を考える」かのどちらかである。今回は(どういうわけか)後者を選択、bcコマンドによるゴリ押しで進んだ。本来であればオーバーフローしないようにmod演算をループごとに行うのが筋であろうが、オーバーフローしない状態で最後まで計算する方法があるなら越したことは無い(???)
m=1000000007 read n read a s1=`echo $a | tr ' ' '+'` s2=`echo $a | sed -r "s/([0-9]+)/\1\*\1/g" | tr ' ' '+'` echo "(($s1)*($s1)-($s2))/2%$m" | bc
入力をaとして受け取り、s1にΣa[i]を、s2にΣ(a[i]^2)の数式を入れた。あとはこれをbcコマンドに突っ込んで最後にmod演算する。
あまり美しいとは言えない解法だが、ギリギリACできたのでとりあえずヨシ！
余談
もう少し丁寧な解法を考える。
漸化式のように、i番目までの解=(i-1番目までの解)+(i番目の値)*(i-1番目までの値の和)でつないでいく形。
m=1000000007
read n
read a
s1=0
ans=0
for x in $a
do
ans=$(((ans+s1*x)%m))
s1=$(((s1+x)%m))
done
echo $ans普通にACできてしまった。これがコンテスト中に思いつかなかったのは勉強不足であったと言わざるを得ない。
解説を見ると累積和や区間和という言葉が出てきたが、正直真面目に実装した経験がないので理解できているか怪しい。本当は日頃からもっと学んでいければよいのだが…
