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

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

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

#環境
python3
AOJでACを確認

#2章 アルゴリズムと計算量
##2.5 導入問題
###ALDS1_1_D: Maximum Profit
```python: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
```python: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
```python: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
```python: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
```python: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
```python: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
```python: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
```python: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
```python: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ではずっと早い。

```python: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
```python: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)