質問編集履歴
1
追加
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -3,7 +3,7 @@
|
|
|
3
3
|
AtCoder Regular Contest 104 B問題より
|
|
4
4
|
|
|
5
5
|
#方針
|
|
6
|
-
1<=N<=5000という制約から、Sの部分文字列の全列挙自体は計算量は5000*(5000 + 1)//2と見積もられ、実行制限時間2秒を超えることはないと想定されます。しかし、実際に部分文字列を取り出そうとするとスライスの部分で余計な計算量を食うので、あらかじめi番目までにA, T, G, Cが何回登場したかを累積和を用いてA_rec, T_rec, G_rec, C_recに格納しておき、S[i:j]なる部分文字列についてそこから必要な値を用い、その部分文字列に何が何個含まれているかを調べます。そして(Aの個数)=(Tの個数)かつ(Gの個数)=(Cの個数)となれば良いので、それぞれ調べます。
|
|
6
|
+
1<=N<=5000という制約から、Sの部分文字列の全列挙自体は計算量は5000*(5000 + 1)//2と見積もられ、実行制限時間2秒を超えることはないと想定されます。しかし、実際に部分文字列を取り出そうとするとスライスの部分で余計な計算量を食うので、あらかじめi番目までにA, T, G, Cが何回登場したかを累積和を用いてA_rec, T_rec, G_rec, C_recに格納しておき、S[i:j]なる部分文字列についてそこから必要な値を用い、その部分文字列に何が何個含まれているかを調べます。そして(Aの個数)=(Tの個数)かつ(Gの個数)=(Cの個数)となれば良いので、それぞれ調べカウントします。
|
|
7
7
|
|
|
8
8
|
#TLEコード
|
|
9
9
|
```Python
|