競プロ典型 90 問：084 - There are two types of characters（★3）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/11/03
• 結果：解けた
• 時間：20分ぐらい

考えたこと

• ????ox????となっていたら、 lはoか左の?部分から何を選んでもいいし、rはxか右の?部分から何を選んでもいい
• lを各字に固定して、lの右で一番近い別文字を見つければ良さそう
• Nの大きさがと大きいので、lをなめるループ＆右の別文字を探すとまずそう。とかになる。
• 同文字はまとめてしまえば良さそう。「ooxo」を「("o", 2), ("x", 1), ("o", 1)」のようにする感じで持っておけば、配列の隣の要素が別文字になっている。

公式解説

https://twitter.com/e869120/status/1412179495868534784/photo/2

解説を読んだふりかえり

• 「ooxo」を「("o", 2), ("x", 1), ("o", 1)」にすることを、ランレングス圧縮とよぶ。
• 解説の解法は自分とはちょっと異なり、一文字になってしまうパターンを求めて、全体から引くだった。言われてみればそのほうがシンプルな気がする。
• たとえば、「ooxo」の場合、
  • 全体は 個。
  • 一文字になってしまうパターンは、先頭のoo部分から選ぶ場合で 個。
  • 答えは差をとって

ソース

N = int(input())
S = input()

# 「ooxo」を「("o", 2), ("x", 1), ("o", 1)」のようにする
# 現在の色
cur = S[0]
length = 0
L = []
for c in S:
    if cur == c:
        length += 1
    else:
        L.append((cur, length))
        # 色がかわる
        cur = c
        length = 1
# 最後のやつも忘れずに入れる
if length > 0:
    L.append((cur, length))


# L[i] = (c, num)としたとき、
# このL[i]のnum個のどれかを、lとして選んだとする。
# rはL[i+1]以降なら何を選んでもOK。

# 現在位置を覚えておく
curidx = 0
ans = 0
for i in range(len(L)):
    num = L[i][1]
    curidx += num
    # lはnum個から選んでOK、 rは(N-curidx)個から選んでOK
    ans_sub = num * (N - curidx)
    ans += ans_sub

print(ans)