ABC406 C – ~ | ひびのまなびろぐ

この日はB問題までしかできませんでした。C問題が全くわからなかったので解説を読んでいくことにします。

Editorial - Panasonic Programming Contest 2025（AtCoder Beginner Contest 406）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

まず最初にPの大小関係を < と > を使い文字列Sで表します。

1 3 6 4 2 5

上記であれば

<<>><

ですね。

この時Pがチルダ型であるとは部分文字列Sが1個以上の < 、1個以上の > 、1個以上の < をこの順で結合した文字列となります。

ここでランレングス圧縮を考えます。

ランレングス圧縮【連長圧縮】は各文字と文字が連続している回数を組み合わせるもので上記の <<>>< であれば、

<2>2<1

といった形になります。

一個以上の > に着目すると、ランレングス圧縮後の文字が > である一つの要素に対応します。これにより数え上げるべき文字列の「1つ以上の > 」の部分を全探索する方針が立ちます。

つまり1つ以上の > の部分に対して全探索すれば良いということですね。

そして各1つ以上の > に関して左右の要素の数を掛け合わせたものを足し合わせると答えがもとまります。

以下でACすることができました。

def i_map():
    return map(int, input().split())


def i_list():
    return list(map(int, input().split()))


n = int(input())
p = i_list()

s = []

for i in range(n - 1):
    if p[i] < p[i + 1]:
        if len(s) == 0 or s[-1][0] == ">":
            s.append(["<", 1])
        else:
            s[-1][1] += 1
    else:
        if len(s) == 0 or s[-1][0] == "<":
            s.append([">", 1])
        else:
            s[-1][1] += 1

ans = 0

for i in range(1, len(s) - 1):
    if s[i][0] == ">":
        ans += s[i - 1][1] * s[i + 1][1]

print(ans)