teratail header banner
teratail header banner
質問するログイン新規登録

質問編集履歴

1

追加

2021/06/06 03:08

投稿

kay_ventris4
kay_ventris4

スコア269

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