naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉ARC 057 C - 2乗根

旧スコア体系(現行のE問題相当)。

考察

入力の数列を2乗したもの(甲)と、入力の数列+1を2乗したもの(乙)を用意して、左から比較して違う数字になるところに着目して 甲≦x<乙 になるような数列を返す。
(自乗するのにFFT使ってるけど1000桁程度だったら要らなかったな)
→WA(1)
2乗した結果の末尾のゼロを捨てて、ジャストになるなら乙側に寄せないようにする
→WA(2) あまり減ってない

時間切れにつき解説を読む

なるほど、2桁ずつのアラインメントを意識する必要があるのね(√Nサイドが10^t乗だから、10^2tがかかった数を扱っている)

その後2WA出した。コーナーケースきつい。

  • 99 のようなケースで 末尾桁をincrementしてはいけない。(a+1)^2の末尾が00..00になるので、incrementでそれに追いついてしまうから。
  • 2499 のようなケースでも同様

→AC
https://beta.atcoder.jp/contests/arc057/submissions/2744668

教訓
  • 1000桁ぐらいなら愚直に掛け算しても大丈夫
  • 考えられるコーナーケースのテストをすべて用意する
  • 配列のどちら側が上位桁なのか迷子になりやすいので気をつける。