トップページ -> AOJの解答例 -> ITP2_2の解答例

ITP2_2の解答例(Python)

ITP2_1に続いて配列に関する問題です．今回も配列に関する計算量に関して頭に入れた上でコードを書かないと時間制限に引っかかります．こちらのサイトに計算量がまとめてあります．

1. ITP2_2_A: Stack

両端への操作しかしないのでdequeを使いました． from collections import deque で deque を使うことができます．
【外部サイト】Pythonのdequeでキュー、スタック、デック（両端キュー）を扱う


# ITP2_2A
from collections import deque
m, n = list(map(int,input().split(" ")))

A = [deque() for _ in range(m)]

for _ in range(n):
    query = list(map(int,input().split(" ")))
    
    # 追加
    if query[0] == 0:
        A[query[1]].append(query[2])
    # 出力
    elif query[0] == 1:
        if len(A[query[1]]):
            print(A[query[1]][-1])
    # 取り出し
    else:
        if len(A[query[1]]):
            A[query[1]].pop()

2. ITP2_2_B: Queue

複数のdequeに対して操作を行うだけでAとほとんど変わりません．


# ITP2_2B
from collections import deque
m, n = list(map(int,input().split(" ")))

A = [deque() for _ in range(m)]

for _ in range(n):
    query = list(map(int,input().split(" ")))
    # 追加
    if query[0] == 0:
        A[query[1]].appendleft(query[2])
    # 出力
    elif query[0] == 1:
        if len(A[query[1]]):
            print(A[query[1]][-1])
    # 削除
    else:
        if len(A[query[1]]):
            A[query[1]].pop()

3. ITP2_2_C: Priority Queue

優先度付きキューに関する問題です． Pythonではheapqで優先度付きキューを使用することができます．【外部サイト】優先度付きキューの使い方


# ITP2_2C
# 優先度付きキュー
import heapq

m, n = list(map(int,input().split(" ")))
A = [[] for _ in range(m)]
for x in A:
    heapq.heapify(x)

for _ in range(n):
    query = list(map(int,input().split(" ")))
    # 追加
    if query[0] == 0:
        heapq.heappush(A[query[1]], -query[2]) # 最小値しか取り出せないので正負を逆転させておく
    # 最大値
    elif query[0] == 1:
        # 一度取り出してから再度追加
        if len(A[query[1]]):
            # print(-min(A[query[1]]))
            max_val = -heapq.heappop(A[query[1]])
            print(max_val)
            heapq.heappush(A[query[1]], -max_val) # 最小値しか取り出せないので正負を逆転させておく
    else:
        if len(A[query[1]]):
            heapq.heappop(A[query[1]])

4. ITP2_2_D: Splice

リストの結合に関してです． l1.extend(l2) で l1の後ろにl2を追加できます． insert は末尾に関してしか行わないのですが，結合に時間がかかります．例えば長さ3のリストAと長さ1000のリストBの結合でも A.extend(B) と B.extend(A)ではだいぶ時間が変わります．

list.extendにかかる時間

リストの結合は長さを比較して短い方を長い方に追加するようにしました．


# ITP2_2D
from collections import deque
import copy
m, n = list(map(int,input().split(" ")))

A = [deque() for _ in range(m)]

for _ in range(n):
    query = list(map(int,input().split(" ")))
    # 追加
    if query[0] == 0:
        A[query[1]].append(query[2])
    # 列挙
    elif query[0] == 1:
        print(*A[query[1]])
    # 結合の処理に時間がかかるので工夫する
    else:
        # A[query[1]] が空でない
        if A[query[1]]:
            # 短いほうを長いほうに追加するようにする
            if len(A[query[2]]) >= len(A[query[1]]):
                A[query[2]].extend(A[query[1]])
                A[query[1]] = deque()
            else:
                A[query[2]].reverse()
                A[query[1]].extendleft(A[query[2]])
                A[query[2]] = A[query[1]]
                A[query[1]] = deque()

<- 前へ戻る【目次に戻る】次へ進む ->