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)