ALDS1_3_D 続きの続き
スタックが空にならなくても水たまりが終わることがある
浅くなってきてた水たまりが深くなったらいったん水たまりが終わったことに
するけれども、右側の底がもっと高くなったら「飲み込まれる」ような動きがいる
と思って作り込んだのがこれ
def pool_merge(pool_area, left_x, cur_area):
if not pool_area:
return cur_area
while pool_area and (pool_area[-1])[0] > len(left_x):
cur_area += (pool_area.pop())[1]
return cur_area
def calc(s):
shape = [ch for ch in s]
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:
if cur_area > 0:
pool_area.append((len(left_x), cur_area))
cur_area = 0
left_x.append(x)
elif left_x and sl == 1:
cur_area += x - left_x.pop()
cur_area = pool_merge(pool_area, left_x, cur_area)
if not left_x:
pool_area.append((len(left_x), cur_area))
cur_area = 0
if cur_area > 0:
pool_area.append((len(left_x), cur_area))
return [p[1] for p in pool_area]
pool_area = calc(input())
print(sum(pool_area))
print(len(pool_area), *pool_area)
そろそろ頭が死にそうなんだけれども、まだ漏れがある
はずなんだけどAC
(50番のテストが"--"ってなってるんだけどAC)
ていうかね
自分でまだうまくいかないはずっていうテストケースがうまくいってしまう
意味わからないんですけど
\///\\\//
はうまくいかないはずなんですよ!
まんなかに山があっても飲み込んでしまうはずなの!
まんなかに山があるとか考慮してないんだから!
水たまり以外のことは忘れてしまうんだから!
なんで成功してるの!
:
:
そうか
実際の標高じゃなくて、スタックの深さでやってるからか
山があるってことはスタックが空になってるってことで
その時点で深さ0ってことになるから金輪際飲み込まれることはないってわけか
いや難しすぎる
漏れがないとかまったく保証できる気がしない
AC取ったし解説読む