- 「並び替えたら」という問題文だが、文字通り並び替える必要はなく頻度カウントで良いと判断
- 並び替えが「順序を無視すること」だから「順序のない列は多重集合」のパターン
- 並び替え→頻度カウント
- 素朴な書き方で方向が間違ってないか確認 python
def solve_simple(N, S):
from collections import Counter
ret = 0
for i in range(N):
for j in range(i + 1, N + 1):
subseq = S[i:j]
debug("subseq", subseq)
count = Counter(subseq)
if count["A"] == count["T"] and count["C"] == count["G"]:
ret += 1
return ret
- で、これを十分に高速な方法で実装し直す
- 頻度カウントは範囲和だから累積和の方法かな？と思う
- でもN=5000だから、O(N^2)でもギリギリ通るのでは？という気がしたので、まずシンプルに数える方法を試してからにしようと判断。
- 結果、その判断が正しくて累積和を使わずにAC python
def solve(N, S):
from collections import defaultdict
ret = 0
for i in range(N):
count = defaultdict(int)
for j in range(i, N):
count[S[j]] += 1
if count["A"] == count["T"] and count["C"] == count["G"]:
ret += 1
return ret
- jの動く範囲を1間違えて一回REした
-
-
どういう想定なのか全然イメージつかなかったのでとりあえず素朴に深さ優先探索で実装
-
サンプルケースは正解できるようになったがかなり複雑なコードになり、 WAが解消しなかった
- 中途半端に高速な実装をしたのが良くない。 WAになる原因を特定できなかった。
- もっとシンプルで遅くて正しいコードがあれば、ランダムテストで食い違いを見つけることができた。
-
解説を読むと、領域分割に帰着してDPでO(N^3)とのこと
-
これは全然思いつかなかった、こういう「帰着する力」は足りてないなぁ、どうすれば身につくかなぁ、と考えている
