精進(2024/2/22) - あるぱかのブログ

AtCoder ProblemsのRecommendation(Moderate)を解く

AtCoder Beginner Contest 245 C - Choose Elements
THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318） C - Blue Spring

AtCoder Beginner Contest 245 C - Choose Elements

diff = 403

リンク：C - Choose Elements (atcoder.jp)

概要：配列 $A$ および $B$ から配列 $X$ を次の条件を守って作成できるか判定してね

条件1： $X_i$ = $A_i$ or $B_i$

条件2： $|X_i - X_{i+1}| \leq K$

$X_i$ の取り方は $A_i$ or $B_i$ の2通りなので条件を無視すれば配列 $X$ は $2^{N}$ 通り考えられます。

$N \leq 2 \times 10^{5}$ なので愚直に全組み合わせを探索していては到底間に合いません。

そこで $X_i$ に対して $A_{i+1}$ あるいは $B_{i+1}$ が条件2を満たし得るかのみ考えていくことにします。

（条件を満たした配列1つを出力、あるいは条件を満たす組み合わせ数を出力する問題では無いので、実際に配列 $X$ を作る必要はありません。）

具体的は $A_i$ と $B_i$ を持っておいて（コード9行目の $cnt$ ） $A_{i+1}$ および $B_{i+1}$ との差の絶対値を計算します。

つまり $|A_i - A_{i+1}|$ 、 $|A_i - B_{i+1}|$ 、 $|B_i - A_{i+1}|$ 、 $|B_i - B_{i+1}|$ の最大4回を計算します。

計算結果が $K$ 以下となるような $A_{i+1}$ と $B_{i+1}$ を採用して（コード26、28行目の $nxt$ ）次のステップの計算を行います。

試行回数は最大で $4 \times N$ なので計算量は $O(N)$ となり十分高速です。

#ABC245 C - Choose Elements
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
nxt = [A[0], B[0]]
ans = 'No'

for i in range(N):
    cnt = nxt[:]
    nxt = []
    flag_A = 0
    flag_B = 0
    if i == N-1:
        if len(cnt) != 0:
            ans = 'Yes'
        break
    else:
        if len(cnt) == 0:
            break
        for j in cnt:
            if abs(A[i+1] - j) <= K:
                flag_A += 1
            if abs(B[i+1] - j) <= K:
                flag_B += 1
        if flag_A > 0:
            nxt.append(A[i+1])
        if flag_B > 0:
            nxt.append(B[i+1])
        #print(i, cnt, nxt)
print(ans)

これを入力例1に対して実行すると以下の出力が得られます（コメントアウトしている部分も有効化しています）

 5 4　          #入力N, K
 9 8 3 7 2      #入力A
 1 6 2 9 5      #入力B
0 [9, 1] [8, 6] #i=0, cnt[A[0], B[0]], nxt[A[1], B[1]]
1 [8, 6] [3, 2] #i=1, cnt[A[1], B[1]], nxt[A[2], B[2]]
2 [3, 2] [7]    #i=2, cnt[A[2], B[2]], nxt[A[3]] #B[3]は条件を満たさない
3 [7] [5]       #i=3, cnt[A[3]], nxt[B[4]]
Yes             #X4となり得る数字を保持してi=N-1に到達したのでYes

提出リンク：提出 #50516759 - AtCoder Beginner Contest 245

THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318） C - Blue Spring

diff = 400

リンク：C - Blue Spring (atcoder.jp)

概要：1単位 $D$ 枚綴りの1日周遊パスを買ったり買わなかったりして $N$ 日間の旅費を最小にしてね

こちらも $N \leq 2 \times 10^{5}$ なので計算量 $O(N^{2})$ だとTLEになります。

この問題を高速に解くためには累積和が使えそうです。

1日周遊パスの販売単位である $D$ 日ごとに累積和をとっておくと後々計算しやすそうです。

前処理として $F$ の長さが $D$ の倍数になるように末尾に $0$ を足しておきます。

後は1日周遊パスを $0$ ～ $\dfrac{len(F)}{D}$ 単位まで増やしながら旅費の最小値を更新していきます。

1段落目で $len(F)$ が $D$ の倍数になるよう調整、2段落目で $D$ 日毎に累積和の計算、3段落目で旅費の計算と最小値の更新をしています。

$F$ のソートに最も時間がかかるので計算量は $O(Nlog(N))$ です。

#ABC318 C - Blue Spring
N, D, P = map(int, input().split())
F = list(map(int, input().split()))
F = sorted(F, reverse = True)
if N % D != 0:
    a = D - (N % D)
    F += [0] * a
#print(F)

S = [0]
s = 0
for i in range(len(F) // D):
    s += sum(F[i*D:i*D+D])
    S.append(s)
#print(S)

ans = s
for i in range(len(S)):
    pay = S[-1] - S[i] + P * i
    #print(ans, pay)
    ans = min(ans, pay)
print(ans)

これを入力例1に対して実行すると以下の出力が得られます（コメントアウトしている部分も有効化しています）

 5 2 10             #入力N, D, P
 7 1 6 3 6          #入力F
[7, 6, 6, 3, 1, 0]  #Fをソートして末尾に0を足した
[0, 13, 22, 23]     #累積和S
23 23               #周遊パス0単位のとき（i=1から始めればよかった・・・）
23 20               #購入数0単位と1単位を比較(ansを20に更新)
20 21               #購入数1単位と2単位を比較
20 30               #購入数1単位と3単位を比較
20                  #最小値は周遊パス1単位購入したときの20

提出リンク：提出 #50517168 - THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）