AOJ ALDS1_3_D Areas on the Cross-Section Diagram

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_D&lang=ja

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque
import copy

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    stack = []

    water = []
    sum = 0
    for i in range(len(S)):
        s = S[i]
        if s == '\\':
            stack.append(i)
        elif s == '/' and len(stack) > 0:
            j = stack.pop()
            sum += i - j
            area = i - j
            while len(water) > 0 and water[-1][0] > j:
                w = water.pop()
                area += w[1]
            water.append([j, area])

    ret = []
    for i, w in water:
        ret.append(w)
    print(sum)
    print(len(ret), *ret)


if __name__ == '__main__':
    main()

考え方

螺旋本より、スタックの問題。
実装はC++のコードをほぼ写経。。。

---

観点は2つで、
１つ目は/に対応する\との面積を求めること、
２つ目は、深さが2以上ある場合(例えば\\//など）の時、
1つの水たまりとして扱うこと。

1つ目について。
\が与えられたとき、そのindexをスタックに積んでおく。
/が与えられたとき、スタックから１つpopすることで、
/に対応する\の位置が判明する。
あとは自身(/)の位置から対応する\の位置で面積を求めることが出来る。
（全て1 * 1の区画として扱われるため、/の位置 - \の位置で面積を求めることが出来る）

2つ目について。
予め、1つ目で得た\の位置と面積を別のスタックに積んでおく。
新たに位置と面積の情報をスタックで積む際に、
スタックの末尾に自分の\の位置より大きい値の有無を確認する。
自分の\の位置より大きいとは、自分より右側に存在しているため、
１つの繋がった水たまりと判定することができる。