ALDS1_3_D 続き

さて

しかしスタックだかキューだかリストだか知らんけど

使うとしたらスタックかなあ
何を積むか
計算量を増やさないようにするには、左から順番に１回見るだけで終わらないといけなさそう

深くなっていく間はなにか積んでおいて、浅くなるときに取り出す感じ？
何を積む？
深さ？x座標？両方？
両方いるような気もするけど、スタックをたとえば深さごとに用意するのでは
計算量が増えてしまう

そうか、深くなるのも浅くなるのも１刻みだから深さは覚えておかなくても？
右へ進みつつ、深くなるときx座標だけをpush、浅くなるときにpopしていくと
スタックの一番上にはいつも同じ深さの左側の底のx座標があるということ？

スタックが空なら水たまりが終わりってことになるな
なんかいけそう

コードはほとんど書き直しか

def main():
    shape = [ch for ch in input()]
    slope = [shape_to_slope(ch) for ch in shape]

    left_x = []
    cur_area = 0
    pool_area = []
    for x, sl in enumerate(slope):
        if sl == -1:
            left_x.append(x)
        elif left_x and sl == 1:
            cur_area += x - left_x.pop() 
            if not left_x:
                pool_area.append(cur_area)
                cur_area = 0

    print(sum(pool_area))
    print(len(pool_area), *pool_area)

これでいけるかと思ったけどダメ
水たまりの終わりの判定条件がおかしい
スタックが空にならなくても水たまりが終わることがある