kb84tkhrのブログ

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

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)でもダメかも?

しかしスタックだかキューだかリストだか知らんけど
どうやって使うんだ?

解説見るか・・・
うーん
もうちょっと考えよう