AOJのアルゴリズムとデータ構造入門をPythonで解いていく -Part3-

10308 ワード
アルゴリズム AOJ ALDS1 Python データ構造 Python テキストリンク

はじめに

こんにちは。もちもちもちおです。
AOJのアルゴリズムとデータ構造入門を解いていきます。
学んだ記録として残していこうと思いやす。

僕自身プログラミングに触り始めてまだ半年もたっておらず
AtCoder緑なので、強者ではありましぇん。
一緒に頑張りましょう。

make it possible with パイちゃん

目次

今回はPART3: 基本的データ構造 です。
頑張って最後までやりたいものです。

ALDS1_3_A : スタック
ALDS1_3_B : キュー
ALDS1_3_C : 双方向連結リスト
ALDS1_3_D : Areas on the Cross-Section Diagram

ALDS1_3_A : スタック

スタック〜

a = list(map(str,input().split()))
l = []
for i in a:
    if i=="+":
        a1 = l.pop()
        a2 = l.pop()
        a3 = a1+a2
        l.append(a3)

    elif i=="-":
        a1 = l.pop()
        a2 = l.pop()
        a3 = a2-a1
        l.append(a3)

    elif i=="*":
        a1 = l.pop()
        a2 = l.pop()
        a3 = a1*a2
        l.append(a3)

    else:
        l.append(int(i))

print(l[0])

ALDS1_3_B : キュー

dequeを使おう

from collections import deque
n,q = map(int,input().split())
l = [list(map(str,input().split())) for _ in range(n)]
time = 0
dq = deque(l)
while dq:
    a,b = dq.popleft()
    if int(b)<= q:
        time += int(b)
        print(a,time)

    else:
        time += q
        b = int(b) - q
        dq.append([a,b])

ALDS1_3_C : 双方向連結リスト

基本はdequeで計算
Pythonだと以下の2点をしないとTLEになってしまう
・inputを自分で定義する方が早い
・index必要ないなら for a in d: の方が早い


from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
d = deque([])
for _ in range(n):
    a = list(map(str,input().split()))
    if a[0]=="insert":
        d.appendleft(a[1])


    elif a[0]=="delete":
        if a[1] in d:
            d.remove(a[1])

    elif a[0]=="deleteFirst":
        s = d.popleft()


    elif a[0]=="deleteLast":
        s = d.pop()

print(*d)

ALDS1_3_D : Areas on the Cross-Section Diagram

まだとけてません、、、　ぴえん

おわりに

Dとけたら更新します　吸いません