【AtCoder】ABC297のA,B,C,D,E問題をpythonで解説

N,D = map(int, input().split())
T = list(map(int, input().split()))

for i in range(1,N):#2回目からN回目の操作において
    if T[i]-T[i-1] <=D:#i回目とi-1回目の時間の差がD以下であれば
        print(T[i])
        exit()
print(-1)#ダブルクリックが一度も行われていなければ

s = input()

check =0#Bの偶奇をチェックする
for i in range(8):
    if s[i] == "B":
        check += i
if check %2 == 0:
    print("No")
    exit()

king = 100#後に更新される　適当な数字
R = []
for i in range(8):
    if s[i] == "K":
        king = i#Kの座標を取得
    if s[i] == "R":#Rの座標を取得
        R.append(i)

import bisect

a = bisect.bisect_left(R,king)#kingを挿入する際に何番目に挿入されるか
if a == 1:#挿入される場所が1なら
    print("Yes")
else:
    print("No")

H,W = map(int, input().split())
box = []#最後に答えを出力する空のリスト
cnt = 0
for i in range(H):
    s = input()#文字列を受け取る
    s_l = list(s)#文字列だと操作しづらいのでリストに変換
    for j in range(W-1):
        if s_l[j]== s_l[j+1] == "T":#もし、j番目もj+1番目もTだったら
            s_l[j] = "P"#j番目をPに
            s_l[j+1] ="C"#j+1番目をCへ
    
    ans = ""#答えを出力する空の文字列
    for j in range(W):#先程変更した文字列を
        ans += s_l[j]#順に連結(足して)
    box.append(ans)#最終的な答えのリストに格納

for i in range(H):
    print(box[i])

import math
A,B = map(int, input().split())
# print(math.gcd(A,B))
if A ==B:#もしAとBが同じ値なら
    print(0)
    exit()
cnt = 0
#以降A≠Bについて
while A != B:
    #Aのほうが大きいようにしたいので、
    if A < B:#もしAよりもBが大きかったら
        A,B = B,A#AとBを入れ替える
    
    if A%B == 0:#もしAがBの倍数なら
        cnt+= A//B-1#変遷した数字の数-1=変遷した回数
        print(cnt)
        exit()
    else:#AがBの倍数ではないなら
        cnt += A//B#AがBよりも小さな値になるまで変遷させる
        A = A%B#新しいAがの値

N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)#商品の値段を大きいもの順に並べる
# 上記操作はなくても大丈夫なはずだが、理解しやすくするために並べ替えた

dp = [[0]* (K+1) for i in range(N)]#N+(K+1)のdpを作成

for j in range(1,K+1):#商品2のみを使用したK番目までの支払い方法
    dp[0][j] = A[0]*j

for i in range(1,N):
    is_flg = 0#次参照する商品iまでを使用した支払い方法
    was_flg = 1#参照する商品i-1までを使用した支払い方法
    for j in range(1,K+1):
        if dp[i][is_flg]+A[i] == dp[i-1][was_flg]:
            #商品iを買って、i-1番目までのj番目の支払いの金額と同じ担った場合
            dp[i][j] = dp[i][is_flg]+A[i]#どちらの値を使用してもよい
            is_flg += 1#次参照する商品iまでを使用した支払い方法を更新
            was_flg += 1#次参照する商品i-1までを使用した支払い方法を更新
        elif dp[i][is_flg]+A[i] < dp[i-1][was_flg]:#商品iを買ったら、i-1番目までのj番目の支払いよりも小さい時
            dp[i][j] = dp[i][is_flg]+A[i]
            #商品iまで使用して支払うj番目の支払い=商品iまでを支払うパターンにおいてis_flg番目に安い支払いの値+i番目の商品の値
            is_flg += 1#次参照する商品iまでを使用した支払い方法のみを更新
        elif dp[i][is_flg] +A[i]> dp[i-1][was_flg]:#商品iを買ったら、i-1番目までのj番目の支払いよりも大きい時
            dp[i][j] = dp[i-1][was_flg]
            #商品iまで使用して支払うj番目の支払い=商品i-1までを支払うパターンにおいてwas_flg番目に安い支払いの値
            was_flg += 1#次参照する商品i-1までを使用した支払い方法のみを更新

print(dp[-1][K])