データ構造に関する問題です． データ構造について詳しく知りたい方は参考文献などをご覧ください．
# ALDS1_3_A
from collections import deque
# 入力された内容を保存しておくスタック
N = deque(input().split(" "))
# 計算用のスタック
M = deque()
# 答えが出る = 長さが1になる までループ処理
while len(N)>=1:
n = N.popleft()
if n == "+":
a = int(M.pop())
b = int(M.pop())
M.append(b+a)
elif n == "-":
a = int(M.pop())
b = int(M.pop())
M.append(b-a)
elif n == "*":
a = int(M.pop())
b = int(M.pop())
M.append(b*a)
else:
M.append(n)
print(M[0])
# ALDS1_3_B
from collections import deque
n,q_time = map(int,input().split(" "))
p_list = deque()
for _ in range(n):
p_name,p_time = input().split(" ")
p_list.append([p_name,int(p_time)])
# 全部が削除されるまで
elasped_time = 0 # 経過時間
while p_list:
p = p_list.popleft()
# 残り処理時間がクオンタイム以下なら削除して終了
if q_time >= p[1]:
elasped_time += p[1]
print(p[0],elasped_time)
# 終わらない場合は処理時間からクオンタイムを引いて末尾にappend
else:
p[1] -= q_time
elasped_time += q_time
p_list.append(p)
# ALDS1_3_C
dll = [] # 双方向連結リスト
n = int(input())
first = None # 先頭の要素のインデックス
last = None # 末尾の要素のインデックス
# 双方向連結リストか最初に現れるtargetを探し，インデックスを返す
def search_idx(target,first):
idx = first
while idx!=None:
if target == dll[idx]["num"]:
return idx
else:
idx = dll[idx]["next"]
return None
for _ in range(n):
command = input().split(" ")
# 入力の内容によっては num も受け取る
if len(command)==1:
command = command[0]
else:
command, num = command[0], int(command[1])
# insert: 指定された要素を先頭に挿入
if command=="insert":
# num, prev, next
dll.append({"num":num,"prev":None,"next":first})
# 先頭だったもののprevを更新
if first!=None:
dll[first]["prev"] = len(dll)-1
first = len(dll)-1 # 先頭のインデックスを更新
# last==None(一つも要素がない)ならlastも更新する
if last==None:
last = len(dll)-1
# delete: 指定された要素(最初に現れるもの)を削除
elif command=="delete":
idx = search_idx(num,first)
# 双方向リスト内に含まれなければ削除は行わない
if idx==None:
pass
else:
# deleteされる要素の1個前のnextを書き換え
if dll[idx]["prev"]!=None:
dll[dll[idx]["prev"]]["next"] = dll[idx]["next"]
# deleteされる要素の1個後ろのprevを書き換え
if dll[idx]["next"]!=None:
dll[dll[idx]["next"]]["prev"] = dll[idx]["prev"]
# lastの要素が削除された場合はlastも更新
if idx==last:
last = dll[last]["prev"]
# firstの要素が削除された場合はfirstを更新
if idx==first:
first = dll[idx]["next"]
# deleteFirst: 先頭の要素を削除
elif command=="deleteFirst":
idx = search_idx(dll[first]["num"],first)
if last!=idx:
dll[dll[first]["next"]]["prev"] = None
# lastの要素だった場合はlast=Noneにする
elif last==idx:
last = None
first = dll[first]["next"]
# deleteLast: 最後の要素を削除する
if command=="deleteLast":
idx = last
if first!=idx:
dll[dll[last]["prev"]]["next"] = None
# firstの要素だった場合はfirst=Noneにする
elif first==idx:
first = None
last = dll[last]["prev"]
# 結果を出力する
result = []
idx = first
while idx!=None:
result.append(dll[idx]["num"])
idx = dll[idx]["next"]
print(*result)
# ALDS1_3_D
# 一番左の高さを20000にしておく
graph = input()
# (i番目の文字,文字の左端の高さ，文字の右端の高さ)のリストを作る
def search_height(graph):
height = 20000 # 全体の左端の高さは20000
height_graph = []
for s in graph:
if s == "\\":
height_graph.append(("\\",height,height-1))
height -= 1
elif s == "_":
height_graph.append(("_",height,height))
else:
height_graph.append(("/",height,height+1))
height += 1
return height_graph
def calc_area(start,end):
left_height = height_graph[start][1]
is_area = False
area = 0
for i in range(start,end+1):
if height_graph[i][0]=="_":
area += left_height - height_graph[i][2]
# 斜めになる分 0.5を引いている
elif height_graph[i][0]=="\\":
area += (left_height - height_graph[i][2]) - 0.5
else:
area += (left_height - height_graph[i][2]) + 0.5
if height_graph[i][2] >= left_height:
return max(area,0)
height_graph = search_height(graph)
left_idx = 0 # 左端のインデックス
left_height = 20000 # 左端の高さ
area_list = [] # 面積のリスト
# 自身より右側の最高点を把握するために高さのリストを作る
height_list = []
for j in range(len(height_graph)):
height_list.append(height_graph[j][2])
height_list.sort()
# 右側の最大値を保持しておく
max_right = height_list.pop()
for i in range(len(height_graph)):
x_left = height_graph[i][1] # 文字の左側の高さ
x_right = height_graph[i][2] # 文字の右側の高さ
# 自身より右側の最高点の更新
if height_list:
if x_right==max_right:
max_right = height_list.pop()
else:
height_list.remove(x_right)
# x_rightがleft_height以上なら区間の面積を確定させてleftを更新
if x_right == left_height:
# left_idxからiまでの面積の計算を行う
area = calc_area(left_idx,i)
if area!=0:
area_list.append(area)
# leftの更新 右側にleft以上の高さがあればleftを更新
if x_right <= max_right:
left_height = x_right
left_idx = i
else:
# なかった場合は次の文字の高さに設定しておく
if i+1 <= len(height_graph)-1:
left_height = height_graph[i+1][1]
left_idx = i+1
if x_right >= left_height or x_left >= left_height:
# 右側にleft以上の高さがあればleftを更新
if max(x_right,x_left) <= max_right:
left_height = max(x_right,x_left)
left_idx = i
else:
# なかった場合は次の文字の高さに設定しておく
if i+1 <= len(height_graph)-1:
left_height = height_graph[i+1][1]
left_idx = i+1
print(int(sum(area_list)))
print(len(area_list),end="")
for area in area_list:
print(" " + str(int(area)),end="")
print()