ALDS1_3_D
※この問題はやや難しいチャレンジ問題です。難しいと感じたら今は飛ばして、実力をつけてから挑戦してみましょう。
どこが難しいんだろう?
水面の高さを覚えておいて、あと面積を足し算していくだけじゃない?
今水たまりの中か外か覚えておいて場合分けは必要かな
そもそもデータ構造らしきものも出てこないし・・・
などと思った私があさはかでした
そもそもデータ構造らしきものが出てこない時点でおかしいと思え
左から見ていくだけでできると思ったんですけどね
考えてみたら右側の岸が確定するまで水面の高さ出ませんね
しばらくがんばって考えましたが、データ構造っぽいものが出てくるやり方は
思いつかなかったのでまずは力技でやってみました
まずは地形まで求めたあと、すべてのx座標(左右)について、一番高いところの高さから
1ずつ下がりつつ、左右に岸のある高さを探して水面を求める、という方式
横方向にループして、高さ方向にループして、また横方向にループするからO(n3)かな
あ、面積はマジメに台形の計算とかしてないです
幅1なので深さを単純に足し算すれば面積に
#! /usr/local/bin/python3
# coding: utf-8
def shape_to_slope(ch):
if ch == "\\":
return -1
elif ch == "_":
return 0
else:
return 1
def land(height, h, x, delta):
while x in range(len(height)):
if height[x] >= h:
return True
x += delta
return False
def depth_at_x(height, x, max_height, min_height):
for h in reversed(range(height[x], max_height + 1)):
if land(height, h, x, -1) and land(height, h, x, 1):
return h - height[x]
return 0
def main():
shape = [ch for ch in input()]
slope = [shape_to_slope(ch) for ch in shape]
max_height = min_height = 0
height = [0]
for sl in slope:
height.append(height[-1] + sl)
max_height = max(height[-1], max_height)
min_height = min(height[-1], min_height)
prev_depth = 0
current_area = 0
pool_area = []
for x in range(1, len(height)):
depth = depth_at_x(height, x, max_height, min_height)
current_area += depth
if prev_depth > 0 and depth == 0:
pool_area.append(current_area)
current_area = 0
prev_depth = depth
print(sum(pool_area))
print(len(pool_area), *pool_area)
main()
はいはいTLETLE
400文字でTLEだけど20,000文字まである
O(n2)でもダメかも?
しかしスタックだかキューだかリストだか知らんけど
どうやって使うんだ?
解説見るか・・・
うーん
もうちょっと考えよう