ARC104 / B - DNA Sequence
昨日の ARC104 で泣いたので記録を残しておく。
相補的などと難しい言葉が書いてあるが、連続する部分文字列のうち、A の数 = T の数 かつ C の数 = G の数となるものを数える問題。
始点と終点を全探索する。
N の最大値は 5000 だが、終点は始点より後ろにあるので、だいたい 5000 * 2500 = 12500000 で 10 ** 7 くらいの計算量。実行時間制限は 2 sec。 コンテスト中に通せなくて落ち込んでいたのだが、後で聞いたら、String のまま処理していたのを、Symbol にしたら通った。
以下、 String のまま数えたコードと、Symbol に変えてから数えたコードの比較
通せなかった原因としては、10 ** 7 が通るのかよくわかっておらず、計算量を軽くするほうに考えてしまって結果失敗したため。 TLE のときは今まで計算量自体が多すぎて、アルゴリズム自体を変える必要があることが多かったので、中の処理を軽くするだけでいけたことに驚いた。 まあでも 12500000 回も計算したら小さな差でも大きくなるか。
Symbol の方が速いことは知ってはいたが、普段あまり大量の計算をしないので、差が大きくなることに気づかなかった。 N の数が十分に小さいならともかく、実行時間に制限があるときにこういう部分で甘えるのはよくないなと反省。
あとは、String のままでも index を指定して文字を取得できるけれど、s.chars して Array から取得した方が速いので、この辺りも忘れないようにしておく。
