arc104

NISHIO Hirokazu [Translate]
ARC104
AtCoder Regular Contest

B - DNA Sequence
「並び替えたら」という問題文だが、文字通り並び替える必要はなく頻度カウントで良いと判断
並び替えが「順序を無視すること」だから「順序のない列は多重集合」のパターン
並び替え→頻度カウント
素朴な書き方で方向が間違ってないか確認
pythondef 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
pythondef 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した

C - Fair Elevator
どういう想定なのか全然イメージつかなかったのでとりあえず素朴に深さ優先探索で実装
サンプルケースは正解できるようになったがかなり複雑なコードになり、 WAが解消しなかった
中途半端に高速な実装をしたのが良くない。 WAになる原因を特定できなかった。
もっとシンプルで遅くて正しいコードがあれば、ランダムテストで食い違いを見つけることができた。
解説を読むと、領域分割に帰着してDPでO(N^3)とのこと
二者間の関係からより大きな構造ができる
重なるなら同じ長さ→偶数長のブロック

これは全然思いつかなかった、こういう「帰着する力」は足りてないなぁ、どうすれば身につくかなぁ、と考えている