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

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

はじめに

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

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

ぱちょふぁそまちょぱそまちょぱそ

目次

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

ALDS1_4_A: Linear Search
ALDS1_4_B: Binary Search
ALDS1_4_C: Dictionary
ALDS1_4_D : Areas on the Cross-Section Diagram

ALDS1_4_A: Linear Search

tの要素各々確認していく
計算量は0(n*q)

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

print(ans)

ALDS1_4_B: Binary Search

tの要素各々確認していく
計算量は0(n*q)→0(10**9)無理なので二分探索で0(q*ln(n))
二分探索

def b_search(x, target):
    found = False
    min = 0
    max = len(x)
    mid = (min + max) // 2
    while min <= max:
        if target == x[mid]:
            found = True
            break
        elif target > x[mid]:
            min = mid + 1
        else:
            max = mid - 1
        mid = (min + max) // 2
    if found:
        return True
    else:
        return False


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

ALDS1_4_C: Dictionary

基本はdequeで計算



n = int(input())
d = {}

for i in range(n):
    demand, str_list = map(str,input().split())
    if demand == "insert":
        d[str_list] = True

    else:
        if str_list in d:
            print("yes")
        else:
            print("no")

ALDS1_3_D : Areas on the Cross-Section Diagram

決め打ち二分探索
ある値でクリアできるかの関数を作っておく
あとは二分探索の流れ通り


n,k = map(int,input().split())
w = list(int(input())for i  in range(n))
def amount(p):
    e_amount = 0
    track = 1
    for i in w:
        if i > p:
            return False
        elif e_amount + i > p:
            e_amount = i
            track += 1
        else:
            e_amount += i

    if track <= k:
        return True
    else:
        return False


ng = 0
ok = 10**10
while ng + 1 < ok :
    mid = (ok+ng)//2
    if amount(mid) :
        ok = mid
    else:
        ng = mid

print(ok)

おわりに

頑張ります