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

DSL_3の解答例(Python)

リストの中のある区間に関する質問に答える問題です．

1. DSL_3_A: The Smallest Window I

リストの中から要素の総和がS以上となる区間を探し出し，条件を満たす最も短い区間の長さを報告します．まともに調べようとするとO(n**2)程度を調べなければいけなくなるので，区間をスライドさせて調べます．


# DSL_3_A
n,s = map(int,input().split())
A = list(map(int,input().split()))

start = 0 # ウィンドウの開始位置
min_length = n # 最初の長さをnで初期化しておく
window_sum = A[0] # ウィンドウ内の合計

# A[0]の時点で満たしている場合
if A[0] >= s:
    print(1)
else:
    for i in range(1,len(A)):
        window_sum += A[i]
        # window_sum が s 以上なら 開始位置をずらして短くできないかを調べる
        if window_sum > s:
            for j in range(start,i):
                if window_sum - A[j] >= s:
                    window_sum -= A[j]
                    start = j+1
                else:
                    break

        # print(f"{start} to {i}: {window_sum}")
        # print(i-start+1,min_length)
        if (i-start+1 < min_length) and window_sum >= s:
            min_length = i-start+1

    if window_sum >= s:
        print(min_length)
    else:
        print(0)

2. DSL_3_B: The Smallest Window II

条件が変わって集合の包含関係になりましたが，ほとんど同じことをしました．区間内に含まれるの数字の個数だけは count_dict で別途管理しました．


# DSL_3_B
# set の比較演算子(包含関係)が数字と同じように動くのでほとんど変わらない
n,k = map(int,input().split())
A = list(map(int,input().split()))
K = set([i for i in range(1,k+1)])

start = 0 # ウィンドウの開始位置
min_length = n # 最初の長さをnで初期化しておく
window_set = set([A[0]]) # ウィンドウ内の要素のセット
count_dict = {A[0]:1} # Kの範囲内の数字の個数を管理したい

# A[0] = 1, k = 1 の場合
if window_set >= K:
    print(1)
else:
    for i in range(1,len(A)):
        window_set.add(A[i])
        if A[i] not in count_dict:
            count_dict[A[i]] = 0
        count_dict[A[i]] += 1
            
        # window_sum が s 以上なら 開始位置をずらして短くできないかを調べる
        if window_set >= K:
            for j in range(start,i):
                # K の範囲外なら無条件で取り除いてよい
                if A[j] > k:
                    window_set -= set([A[j]])
                    start = j+1
                elif A[j] <= k and count_dict[A[j]] > 1:
                    count_dict[A[j]] -= 1 # 1個取り除く
                    start = j+1
                else:
                    break

        # print(f"{start} to {i}: {window_set}")
        # print(i-start+1,min_length)
        if (i-start+1 < min_length) and window_set >= K:
            min_length = i-start+1

    if window_set >= K:
        print(min_length)
    else:
        print(0)

3. DSL_3_C: The Number of Windows

A,Bと同じく区間をスライドさせて求めます．すごいくだらないことなのですが，アルゴリズムに関すること以外でいくつかハマってしまった部分があったので別のページで紹介しています．
【関連】やらかしてしまったPythonの悪い書き方


# DSL_3_C
def f2():
    n,q = map(int,input().split())
    A = list(map(int,input().split()))
    X = list(map(int,input().split()))

    for x in X:
        cnt = 0
        start = 0
        end = 0
        window_sum = 0 # ウィンドウ内の合計
        for i in range(n): # nの代わりにlen(A)を呼び出すとTLE
            # end < len(A) でないとインデックスエラーになる
            if end < n: # nの代わりにlen(A)を呼び出すとTLE
                # 終了位置をずらしてどこまでいけるか確かめる
                while window_sum + A[end] <= x: 
                    window_sum += A[end]
                    end += 1
                    # 終了位置までたどり着いたら終了
                    if end == n: # nの代わりにlen(A)を呼び出すとTLE
                        break

            cnt += end-i # カウントを増やす
            # print(i,end,window_sum)
            # スタートの数を引いてスタート位置をずらす
            window_sum -= A[start] 
            start += 1

        print(cnt)
        
f2()

3. DSL_3_D: Sliding Minimum Elements

区間内の最小値を報告する問題です． dequeを使って区間内の最小値を含む単調増大な部分列を保持していれば，区間内の最小値を常に左に保持した状態で，次以降の必要な情報も上手く保持することができます．砕けた言い方をすれば，ある数字よりもインデックスが小さいくせに大きいような数字が最小値になることはないので保持する必要がありません． dequeを使っている上にリストの真ん中のような要素にアクセスすることもないので高速に処理できます．


# DSL_3_D
from collections import deque
N,L = map(int,input().split())
A = list(map(int,input().split()))

subsequence = deque()
min_list = []

for i in range(N):
    # A[i] より大きいうえにインデックスも小さい数字は保持する意味がない (単調増大に保つ)
    while subsequence and A[subsequence[-1]] >= A[i]:
        subsequence.pop() # pop で削除する
    
    subsequence.append(i)
    
    # 範囲から出てしまったものは取り除く
    if subsequence[0] < i-L+1:
        subsequence.popleft()
        
    min_list.append(A[subsequence[0]])
        
print(*min_list[L-1:])

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