気をつけないといけないのは以下の三つ。
- 誤差 $10^{-15}$
- 実行時間 2 秒
- 出力ファイルサイズ 20 MB
正直全部厳しいので、こっちが自由にできるところはあまり無い。
誤差を回避しようと全てを $10^{30}$ 倍してから平方根を取るようにすると多倍長が要るので、PyPy を今回は選んだ。
現状まだ PyPy には isqrt が実装されておらず（v7.3.1 は Python 3.6 相当）、時間制限の関係で平方根を求める部分は自前だとしんどいように思う。
出力サイズの制限がバイト単位では分からないが、一行あたり 19 文字 + 改行文字（1 バイト）の 20 バイトにすると全体で $20{,}000{,}000$ バイトの出力になる。
これが許されるかどうか。無理なら各行一文字削る。
入出力する量が多いので、この高速化もやっておいたほうが良い。
せめて実行時間制限だけでも緩めてもいいと思う。
個人的には想定解の倍以上を目安にしている。
(ΦωΦ)＜おしまい