AtcorderABC-Dより先へ行くために代表的なアルゴリズムを勉強した-その4-（優先度付きキュー、貪欲法、しゃくとり法）

はじめに

• ABC-Dを解くために、下記のアルゴリズムを勉強しました。

1. 優先度付きキュー
2. 貪欲法
3. しゃくとり法

アルゴリズム

1. 優先度付きキュー

参考

• 【Python】優先度付きキューの使い方【heapq】

いつ使うか

優先度付きキュー（Priority queue）はデータ型の一つで、具体的には

• 最小値（最大値）を O(logN)O(logN)で取り出す
• 要素を O(logN)O(logN) で挿入する

ことが出来ます。通常のリストだとそれぞれ O(N)O(N) ですので高速です。 「リストの要素の挿入」と「最小値（最大値）を取り出す」ことを繰り返すような時に使います。

概要

import heapq  # heapqライブラリのimport

a = [1, 6, 8, 0, -1]
heapq.heapify(a)  # リストを優先度付きキューへ
print(a)
# -> [-1, 0, 8, 1, 6]

print(heapq.heappop(a))  # 最小値の取り出し
# -> -1
print(a)
# -> [0, 1, 8, 6]

heapq.heappush(a, -2)  # 要素の挿入
print(a)
# -> [-2, 0, 8, 6, 1]

例題

• 問題

  • D - Powerful Discount Tickets

• 解法

import heapq

n,m=map(int,(input().split()))
a_list = list(map(int,input().split()))

# heapqでは最小値しか取り出すことが出来ないため、最大値を取り出すために、各要素に-1をかけた上で最小値を取り出す
a_list_inverse=([-1*int(i) for i in a_list])

# リストを優先度付きキューに変換
heapq.heapify(a_list_inverse)

for i in range(m):
    # 優先度付きキューから最小値を取り出す
    a_min=heapq.heappop(a_list_inverse)

    # 優先度付きキューに要素を挿入
    #  一番小さいものを半分にしてリストpush
    heapq.heappush(a_list_inverse,int(a_min/2))

print(-1*sum(a_list_inverse))

2. 貪欲法

参考

• 簡単な貪欲法を解いてみた

いつ使うか

• 全探索する必要はありそうだが、ちょっとうまく（各部分では途中で打ち切ったり）できそうなとき。その時々で最善を選んでいけば良さそうなとき。

概要

問題設定の中で考えられる解すべてを検討しその中で最適な結果を与えるものを解として選択する手法 * 問題を複数の部分問題に分割する * 各部分問題に対する解を評価する(各部分問題ごとに考えられる解のパターンは複数ある．) * 評価が最も良いものをその部分問題の解(=局所最適解)として，次の部分問題の解(これも複数通り考えられる)を評価する

例題

• 問題

  • D - Lucky PIN

• 解法

N=int(input())
S=input()

key = []

for i in range(10):
    for j in range(10):
        for k in range(10):
            key.append([i,j,k])

flag1 = 0
flag2 = 0
flag3 = 0
ans = 0

for i in range(len(key)):
    flag1 = 0
    flag2 = 0
    flag3 = 0

    flag1 = S.find(str(key[i][0]))

    if flag1 == -1:
        continue

    flag2 = S.find(str(key[i][1]),flag1+1)

    if flag2 == -1:
        continue

    flag3 = S.find(str(key[i][2]),flag2+1)

    if flag3 == -1:
        continue

    if flag1 != -1 and flag2 != -1 and flag3 != -1:
        ans += 1

print(ans)

3. しゃくとり法

参考

• しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

いつ使うか

• 「〇〇を満たす区間の中で最小or最大の長さを求めよ」
• 「〇〇を満たす区間の数を求めよ」
• ex. a1,a2,…,an の連続する部分列のうち総和が xx 以下となるものを数え上げる

概要

• 条件を満たすような区間をすべて求めることができる方法

例題

• 問題

  • C - 列

• 解法

n,k = map(int,input().split())
s_list=[int(input()) for _ in range(n)]

# 整数が1つでも0ならNを返す
for i in range(len(s_list)):
    if s_list[i] == 0:
        print(n)
        exit()

answer = 0
right = 0
mul = 1
for left in range(n):
    # rightを最大まで増やす
    while right < n and mul * s_list[right] <= k:
        mul *= s_list[right]
        right += 1
    answer = max(answer, right - left)
    # 次のしゃくとりの準備
    if left == right:
        right += 1
    else:
        mul /= s_list[left]

print(answer)