ABC194(2021/03/06) 振り返り

A - I Scream

else ifで条件分岐を書き並べるだけ？思った通り書いてみた。

B - Job Assignment

入力で、min(Ai+Bi)を解として一旦保存しとく。そこから、min(Ai,Bj)(i!=j)の中で最小のものを探して解と比較したいけど、どうやって...?

って思ったけど、先週のABCで「困ったら全探索！！」ってなったのを思い出して(先週は素直に全探索しておけばよかったところを無駄に色々考えて反省してる)、とりあえず全探索してみたら普通にACできた。

C - Squared Error

数列の長さNに対して、素直に NC2 = n(n-1)/2 回の計算するとTLEになるのは、問題見てすぐ予想できた。

-200~200のどれか2つの差を2乗するってことは、(0~400)^2 っぽいから、 suti[400] に差の値をメモしておいて、2乗の計算だけ最後にすればいいかな、みたいな方針を立てた。

↑これで提出してみたけど、正しくなかったみたいで、TLE出してしまう。

↑ abs(Ai-Aj)

(追記:eが被ってるけどニュアンス伝わりそうなので訂正諦めます)

真面目にホワイトボード使いながら、式変形を検討し始める。

・ Ai,Ai のペアについて検討するのは、差をとって0だから、わざわざ省かなくても、省いても、どっちでもよさそう。

・対角成分を軸に対称だから、両方計算して最後に2で割っても、解は同じになりそう。

A1の行について見ると、

(a-e)^2 + (a-f)^2 + (a-g)^2 + (a-h)^2 + (a-i)^2

= (a^2 -2ae + e^2) + (a^2 -2af + f^2) + (a^2 -2ag + g^2) + (a^2 -2ah+ h^2) + (a^2 -2ai + i^2)

= (5 * a^2) - 2a * (e+f+g+h+i) + (e^2 + f^2 + g^2 + h^2 + i^2)

これをa,b,c,d,eの各行について行っても、e~iは変わらないから

X = e+f+g+h+i

Y = e^2 + f^2 + g^2 + h^2 + i^2

とおくと、

for( tmp = a~e ) { ans += 5*tmp^2 -2*tmp*X + Y }

みたいになりそうで、X,Yをそれぞれ求めるのは、入力と同じforループで行うと、O(2n)くらいで、...

ってやってたら、ちゃんと速くなったみたいで、93分でぎりぎりACできた。

大きい数値扱うところで、上限考えずにintにして1WAしたのが勿体無かったから、型選びは提出前に見直す癖つけておく。

PAST本買って少しずつ読み進めてるから、来週も3問以上安定して解けるように勉強していこう。