ついに水色になれた。精進します。
"文字列として同一でも、異なる位置から取り出された部分列は区別して数えることとします。" ここを若干勘違いして10分ほどロス。
それぞれの文字から1個以下ずつ選び、最後にすべてゼロの分を抜けばよい。
from collections import Counter def solve(N, S): d = 10**9 + 7 c = Counter(S) ans = 1 for ch, count in c.items(): ans *= (count + 1) ans %= d return ans - 1 assert(solve(1, "a") == 1) assert(solve(2, "ab") == 3) assert(solve(3, "abc") == 7) assert(solve(3, "baa") == 5) assert(solve(6, "abcab") == 17) if __name__ == "__main__": N = int(input()) S = input() print(solve(N, S))
atcoder.jp 700点問題を取れたのは初。600点もなかった気がする。
最初はそんな簡単なわけがないと思いつつ、各色ごとの中から2つ選ぶだけでよいと考えた。 これはある色だけを見たとき、その中から二つ選び間を塗るという行為は、任意の区分を塗ることに等しくなると思っていたから。 が、実際にはこれは異なる。区間が3つに分割されるとき、左右の区間を塗ることは二つを選ぶだけでは満たすことができない。
色の数、石の数共に20000で、計算量N2の解法は取れない。計算量Nの解法を突き詰めて考える。
ではDPっぽく考えてみる。ある地点まででKパターンできたとする。 ここでさらに一つ石を追加したときを考える。
同じ色の石がその地点までに一つもなかったらパターンは一つも増えない。 もし、同じ色の石がその地点までに一つ以上あった場合は増えそうだとわかる。
ここで、追加したことによって新しくできる「既存の一番右にある同じ色の石」と「新しく追加した石」の区間を考えると この間を塗る、塗らないのに２パターンに分けることができる。
この2パターンに分けたとき、全体としては「既存の一番右にある同じ色の石」が左側に構成する区間の通り数の分だけ増えることがわかり、 この地点はKパターン＋「既存の一番右にある同じ色の石、が左側に構成する通り数」となり、DPが成立する。 なお、コーナーケースとして同じ色が連続していたらそれは区間を作ったことにならないので、はじく。
また、新しく追加した石と、一番右以外にある同じ色の石が作る区間は考えなくてよい。 なぜならば、その区間はすでに一番右にある石が追加された段階で数え上げられていると考えてよいため。
結果として、一次元のDPだけれども、ある地点の解を構成する要素は石の並び方によって異なることになる、ちょっと変形したDPになる。 漸化式としては作れず、トップダウンは、、実装できない気がする。ともあれ、ボトムアップの実装にならざるを得ない。 DPの勉強をしてた時にこういうケースもあるんだろうなと考えていたがさっそく現実に。
def solve(N, Cs): dp = [-1 for _ in Cs] latest_c = {} ans = 1 d = 10 ** 9 + 7 for i, c in enumerate(Cs): if c not in latest_c: latest_c[c] = i dp[i] = ans else: previous_i = latest_c[c] if previous_i != i - 1: ans += dp[previous_i] latest_c[c] = i dp[i] = ans return ans % d assert (solve(1, [1]) == 1) assert (solve(2, [1, 1]) == 1) assert (solve(3, [1, 1, 1]) == 1) assert (solve(3, [1, 2, 1]) == 2) assert (solve(3, [2, 1, 1]) == 1) assert (solve(4, [2, 1, 2, 1]) == 3) assert (solve(5, [1, 2, 1, 2, 2]) == 3) assert (solve(5, [1, 2, 1, 1, 2]) == 3) assert (solve(5, [1, 1, 1, 1, 2]) == 1) assert (solve(5, [1, 2, 1, 2, 1]) == 5) assert (solve(7, [1, 3, 1, 2, 3, 3, 2]) == 5) assert (solve(6, [1, 3, 1, 2, 3, 2]) == 5) assert (solve(3, [1, 3, 1]) == 2) assert (solve(4, [1, 3, 1, 2]) == 2) assert (solve(5, [1, 3, 1, 2, 1]) == 4) assert (solve(20000, [1] * 20000) == 1) assert (solve(20000, [1] * 10000 + [2] * 10000) == 1) assert (solve(6, [1, 2] * 3) == 8) if __name__ == "__main__": N = int(input()) Cs = [int(input()) for _ in range(N)] print(solve(N, Cs))
