kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_3_D 続きの続きの続き

AC取ったし解説読む

ざっくり方針は同じにみえる
データ構造の章に出てるっていうのがヒントになったし

この問題の解法として、ソートアルゴリズムを応用するなど、いくつかのアルゴリズムが考えられますが

ふーん
どんなんだ
ちょっとぱっとは思いつかないな
「応用」だからただソートするわけじゃないんだろうな

各水たまりの面積はもう1つのスタックS2を用いて保存していきます。

ここは同じ作戦だ

スタックS2には、(その水たまりの最も左の\の位置, その水たまりのその時点での面積)の組を積んでいきます。

自分は「その水たまりの最も左の\の位置」じゃなくてその時点でのスタックの深さを積んでた
\の位置を覚えておいてどう使うのかな

ここで、新たにできる水たまりの面積は、S2に積まれているjの直前までの水たまりの面積の総和と、新しくできる面積i-jの和になります。

jが・・・
・・・

そうか
左の岸より右にある水たまりが飲み込まれるのか
図を見たら当たり前だった

ソース見る
違うところ以外はかなり似てた(当たり前か

def calc(shape):
    left_x = []
    pool_area = []
    for x, sh in enumerate(shape):
        if sh == "\\":
            left_x.append(x)
        elif left_x and sh == "/":
            lx = left_x.pop()
            area = x - lx
            while pool_area and (pool_area[-1])[0] > lx:
                area += (pool_area.pop())[1]
            pool_area.append((lx, area))
        # print(x, ":", sh, left_x, pool_area)

    return [p[1] for p in pool_area]

pool_area = calc(input())
print(sum(pool_area))
print(len(pool_area), *pool_area)