More than 3 years have passed since last update.

Python版螺旋本(『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』) 解答例

Last updated at 2020-07-22Posted at 2020-07-20

#※この記事は随時更新していきます。

#はじめに
最近、競技プログラミング(AtCoder)をはじめてみました。が、がむしゃらにコンテストに出てみたり過去問を解いても実力の伸びがゆるいような気がしたので、ある程度体系的な知識を得るために螺旋本に手を出してみることにしました。
ただ、螺旋本の解答例はC++なので、Pythonで挑戦している人の参考（反面教師？）のため、また自身の備忘録代わりに投稿させていただきます。
初心者・初投稿なので不備等あるかもしれません。あたたかくご指摘いただけると幸いです。
なお、問題を解くにあたっては出来るだけ題意（本文の教育的配慮）に沿うように、敢えて便利なライブラリ等使っていないところもありますのでご了承ください。（もちろん、知識不足で知らないだけのことが多いのですが…）

#環境
python3
AOJでACを確認

#2章アルゴリズムと計算量
##2.5 導入問題
###ALDS1_1_D: Maximum Profit

ALDS1_1_D.py

R = [int(input()) for i in range(int(input()))]
dfmx = -10 ** 10
mn = 10 ** 10
for i in range(len(R)):
    dfmx = max(R[i] - mn, dfmx)
    mn = min(R[i], mn)
print(dfmx)

#3章初等的整列
##3.2 挿入ソート
###ALDS1_1_A: Insertion Sort

ALDS1_1_A.py

n = int(input())
A = list(map(int, input().split()))
for i in range(1, n):
    print(' '.join(map(str, A)))
    temp = A[i]
    j = i - 1
    while A[j] > temp and j >= 0:
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = temp
print(' '.join(map(str, A)))

##3.3 バブルソート
###ALDS1_2_A: Bubble Sort

ALDS1_2_A.py

n = int(input())
A = list(map(int, input().split()))
cnt = 0
flg = 1
while flg:
    flg = 0
    for i in range(n - 1, 0, -1):
        if A[i] < A[i - 1]:
            A[i], A[i - 1] = A[i - 1], A[i]
            cnt += 1
            flg = 1
print(' '.join(map(str, A)))
print(cnt)

##3.4 選択ソート
###ALDS1_2_B: Selection Sort

ALDS1_2_B.py

n = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(n):
    minj = i
    for j in range(i, n):
        if A[j] < A[minj]:
            minj = j
    A[i], A[minj] = A[minj], A[i]
    if minj != i:
        cnt += 1
print(' '.join(map(str, A)))
print(cnt)

##3.5 安定なソート
###ALDS1_2_C: Stable Sort

ALDS1_2_C.py

def bblsrt(cards):
    cards1 = cards.copy()
    for i in range(len(cards1)):
        for j in range(len(cards1) - 1, i, -1):
            if cards1[j][1] < cards1[j - 1][1]:
                cards1[j], cards1[j - 1] = cards1[j - 1], cards1[j]
    return cards1


def slcsrt(cards):
    cards2 = cards.copy()
    for i in range(len(cards2)):
        minj = i
        for j in range(i, len(cards2)):
            if cards2[j][1] < cards2[minj][1]:
                minj = j
        cards2[i], cards2[minj] = cards2[minj], cards2[i]
    return cards2


n = int(input())
C = list(input().split())
print(' '.join(bblsrt(C)))
print('Stable')
print(' '.join(slcsrt(C)))
print('Stable' if slcsrt(C) == bblsrt(C) else 'Not stable')

#4章データ構造
##4.2 スタック
###ALDS1_3_A: Stack

ALDS1_3_A

ops = list(input().split())
stk = []
for i in ops:
    if i == '+':
        y = stk.pop()
        x = stk.pop()
        stk.append(int(x) + int(y))
    elif i == '-':
        y = stk.pop()
        x = stk.pop()
        stk.append(int(x) - int(y))
    elif i == '*':
        y = stk.pop()
        x = stk.pop()
        stk.append(int(x) * int(y))
    else:
        stk.append(i)
print(stk[0])

##4.3 キュー
###ALDS1_3_B: Queue

ALDS1_3_B

n, q = map(int, input().split())
prcs = []
for _ in range(n):
    nm, tm = input().split()
    prcs.append([nm, int(tm)])
elps = 0
while prcs != []:
    tmp = prcs.pop(0)
    if tmp[1] - q > 0:
        tmp[1] = tmp[1] - q
        prcs.append(tmp)
        elps += q
    else:
        elps += tmp[1]
        print(tmp[0], elps)

##4.6 データ構造の応用: 面積計算
###ALDS1_3_D: Areas on the Cross-Section Diagram

ALDS1_3_D

ch = input()
stk1 = []
stk2 = []
ttlar = 0
for i, c in enumerate(ch):
    if c == '\\':
        stk1.append(i)
    elif c == '/' and stk1 != []:
        j = stk1.pop()
        ttlar += i - j
        lar = i - j
        while stk2 != [] and stk2[-1][0] > j:
            lar += stk2.pop()[1]
        stk2.append([j, lar])
print(ttlar)
ans = [len(stk2)]
ans[1:1] = [stk2[i][1] for i in range(len(stk2))]
print(' '.join(map(str, ans)))

#5章探索
##5.2 線形探索
###ALDS1_4_A: Linear Search

ALDS1_4_A

def linear_search(s, n, key):
    s_cp = s.copy() #都度sのコピーを取らないとsの末尾にkeyがどんどんappendされていってしまう。
    i = 0
    s_cp.append(key)
    while s_cp[i] != key:
        i += 1
    return i != n

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))
ans = 0
for i in t:
    if linear_search(s, n, i) != 0:
        ans += 1
print(ans)

以下の番兵無しver.のほうがAOJではずっと早い。

ALDS1_4_A　番兵無しver.

def linear_search(s, n, key):
    for i in s:
        if i == key:
            return 1
    return 0

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))
ans = 0
for i in t:
    if linear_search(s, n, i) != 0:
        ans += 1
print(ans)

##5.3 二分探索
###ALDS1_4_B: Binary Search

ALDS1_4_B

def binary_search(l, key):
    left = 0
    right = len(l)
    while left < right:
        mid = (left + right) // 2
        if l[mid] == key:
            return 1
        elif key < l[mid]:
            right = mid
        else:
            left = mid + 1
    return 0


n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))
ans = 0
for i in t:
    if binary_search(s, i) != 0:
        ans += 1
print(ans)

#参考図書、参考サイト
[プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ出版) ] (https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957/ref=tmm_pap_title_0?_encoding=UTF8&qid=&sr=)
[AIZU ONLINE JUDGE] (http://judge.u-aizu.ac.jp/onlinejudge/)
[螺旋本をpythonで解いてみた(2~4章)] (https://fukki.pythonanywhere.com/post_detail/6/)
[螺旋本（アルゴリズムとデータ構造）をpythonで解いていく！] (https://qiita.com/merry1221/items/81fa92f0611099b8d6db)

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Python版 螺旋本(『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』) 解答例

Python版螺旋本(『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』) 解答例