問題
小学生のような感想
解説に書いてある通り、O(|S|^2)を落とすために試行錯誤していたら、|S|が大きくなってしまいました。
すべてはO(|S|^2)解法で5*10^5が通ったC++のせいです。
問題文に書いてある通り、Bashでは通りませんでした。
謝罪します。
(bashでpython使おうとしたら、権限がなくてダメでした)
(2021/04/09 23:31 追記) Bash(外部呼出しあり)でACしている方を確認しました。(解読不能)
↑普段触らないJavascriptやRustでもACを確認しました。
Javascriptは入出力が意味不明で死にました。
Rustで文字列は二度と触りたくなくなりました。文字列(i番目のアクセス)遅すぎませんか。
提出一覧を見てて思いましたが、PyPyでTLEしている人が多い印象でした。
PyPyは文字列の足し算は遅いので、今回は足さずに出力する方法があります。
あとは、|S|=1のコーナーケースでREになっている人もいました。
(原案時には|S|=0、つまり空文字列を入れようとしていましたが、Javaが空文字列受け取れなかったので削除しました。)
制限時間が3secになってたのは、aseertをpythonでやったら2secだとTLEしたからです。
たぶんまた今度なんか出すと思います。