ARC104

https://gyazo.com/081fb0643104fc030e8fa2efcc2e3c98

https://gyazo.com/818fada48bf4efbe9a8b0cf3d2bd63f8

「並び替えたら」という問題文だが、文字通り並び替える必要はなく頻度カウントで良いと判断

素朴な書き方で方向が間違ってないか確認

code: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):

debug("subseq", subseq)

count = Counter(subseq)

ret += 1

return ret

で、これを十分に高速な方法で実装し直す

でもN=5000だから、O(N^2)でもギリギリ通るのでは？という気がしたので、まずシンプルに数える方法を試してからにしようと判断。

結果、その判断が正しくて累積和を使わずにAC

code: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):

ret += 1

return ret

jの動く範囲を1間違えて一回REした

https://gyazo.com/b3d2128a1b48c990053e2085fc64aa88

どういう想定なのか全然イメージつかなかったのでとりあえず素朴に深さ優先探索で実装

サンプルケースは正解できるようになったがかなり複雑なコードになり、 WAが解消しなかった

中途半端に高速な実装をしたのが良くない。 WAになる原因を特定できなかった。

もっとシンプルで遅くて正しいコードがあれば、ランダムテストで食い違いを見つけることができた。

解説を読むと、領域分割に帰着してDPでO(N^3)とのこと

https://gyazo.com/06ed0feefd8266f248933d30d8b3f36f