ABC174を振り返る(B問題まで)

ちょっと今回は相性が悪かった(毎回言ってる)。

これは入力が30以上か判定するのみ。

read n
((n>=30)) && echo Yes || echo No

でACできます。

またN=10^6のループかぁ…。難易度は低いんですが時間的な制約をどうにかしないといけません。
いつも通りforループを避ける戦略を取りたいところ。今回はbcを使って解きます。このコマンドは数式を受け取ってそれを出力してくれるという素晴らしい関数です。

今回は入力x,yに対してx*x+y*y<=d*dを満たすx,yの数を出力する必要があるため、とりあえずこの形を作ることから考えます。

read n d
sed -r "s/^(.+) (.+)$/\1\*\1+\2\*\2<=$((d*d))/g"

これで入力例1が次のようになります。

0*0+5*5<=25
-2*-2+4*4<=25
3*3+4*4<=25
4*4+-4*-4<=25

あとはこれをbcコマンドに突っ込めば、

となります。不等式が成り立っている場合1、そうでない場合0を出力していますから、あとは1の数を数えるだけになります。
今回は0か1しかない中で1を選ぶので、シンプルにgrep 1 | wc -lで良いですね。

以上まとめて、

read n d
sed -r "s/^(.+) (.+)$/\1\*\1+\2\*\2<=$((d*d))/g" | bc | grep 1 | wc -l

でACとなります。しかし1500msを超えていて危なかったです。もう少し簡単にできるといいんですが…

C問題、D問題のアルゴリズムは分かるようになりたいところ。