ABC334 C - Socks 2

atcoder.jp

問題

• N組の靴下があったよ
• i番目の組の靴下は、色iだよ
• K枚の靴下がなくなってたよ
• 靴下のペアの奇妙さは、左右の色の差の絶対値だよ
• 残ってる靴下の組み合わせで、最小の奇妙さはいくつ？
• 残ってる靴下の枚数が奇数なら、1枚使わない靴下ができるよ

成約

• $ 1 \leq K \leq N \leq 2 \times 10^{5}$
• $ 1 \leq A{1} < A{2} < ... < A_{K} \leq N$

思考

• 残ってる靴下のうち、ペアがあるものはそれでペアにしてあげると良いね
• 偶数枚残ってるなら、ソートして小さい順にペア作ったら良いよね
• 奇数枚の時…どれを捨てるかを1枚ずつ全探索したい
• 入力例3の時で実験してみる
  • 1)1を捨てる時：(4-2) + (8-7) = 3
  • 2)2を捨てる時：(4-1) + (8-7) = 4
  • 3)4を捨てる時：(2-1) + (8-7) = 2
  • 4)7を捨てる時：(2-1) + (8-4) = 5
  • 5)8を捨てる時：(2-1) + (7-4) = 4
    • 4の靴下を捨てると最小になるね
• 毎回計算してたら$O(N^{2})$になって許されないので、楽に見たいよねぇ
• 捨てる靴下の左側と、右側でそれぞれスコアをいくつ持ってるか、みたいに累積和的に計算しておくと良い、かもしれない
• iが奇数の時、i番目の靴下を捨てる時よりも、i+1番目の靴下を捨てる時の方が絶対に奇妙さ増えてる
  • じゃあ、1,3,5,...の靴下だけチェックしたら良いね
  • 後は上手くシミュレーション

コード

from collections import deque

N, K = map(int, input().split())
A_L = list(map(int, input().split()))

if K % 2 == 0:
    ans = 0
    for i in range(0, K, 2):
        ans += A_L[i + 1] - A_L[i]
    print(ans)
    exit()

l_score,r_score = 0,0
l_que,r_que = deque(),deque()

for a in A_L:
    if len(l_que) == 0 or len(l_que)%2 == 0:
        l_que.append(a)
    else:
        l_que.append(a)
        l_score += l_que[-1] - l_que[-2]

ans = l_score
r_que.append(l_que.pop())
while l_que:
    l_score -= l_que[-1] - l_que[-2]

    r_que.appendleft(l_que.pop())
    r_score += r_que[1] - r_que[0]
    r_que.appendleft(l_que.pop())

    ans = min(ans, l_score + r_score)
print(ans)