atcoder.jp
問題
- N個の島があるよ
- i番目の島と、i+1番目の島が繋がってるよ
- N番目の島は1番目の島と橋で繋がってるよ
- 島M個を回るツアーがあるよ
- 橋の内どれか1本を壊したいんだけど、ツアーの長さの最小値はいくつになる？
成約
- $ 3 \leq N \leq 2 \times 10^5 $
- $ 2 \leq M \leq 2 \times 10^5 $
思考
- 橋ごとに、「この橋壊したらコストどうなる？」を見ていきたい…
- 愚直にツアーを毎回確認してたら、$O(NM)$になって吹っ飛ぶ
- じゃあどうしよう…（本番はここで止まった。無事死亡）
- ツアーの移動毎に見ていく？
- 島$X_i$から島$X_{i+1}$に行く時、橋が壊れていない時は2パターンの経路があるよね
- 経路1（反時計回り）：渡る橋の数は$X_{i+1} - X_i$個
- 経路2（時計回り）：渡る橋野数は$N - (X_{i+1} - X_i)$個
- 経路1で使わなかった橋の数で、経路2ですね
- アナログ時計の文字盤考えると良いかも
- じゃあ、経路1の長さ、経路2の長さが出た所で…
- 経路1の方が、経路2より短い時！
- 経路1で使用した橋を壊してしまうと、経路2を通らなければいけない
- 経路1で使用していない橋を壊しても、経路1で行けるので問題なし！
- 経路2の方が、経路1より短い時！
- 経路2で使用した橋を壊してしまうと、経路1を通らなければいけない
- 経路2で使用していない橋を壊しても、経路2で行けるので問題なし！
- 欲しい値は「この橋壊したら、ツアーの最小経路はいくつになる？」なので…橋ごとに纏めたいね
- 経路1で使用した橋 / 経路2で使用した橋は、区間で表すことができるね！
- じゃあ区間の変動する箇所だけメモって、imos法で集計取ってあげたら、$O(N)$で間に合うね！
コード
N,M = map(int,input().split())
X_L = list(map(int, input().split()))
cost_L = [0]*(N+10)
for i in range(M-1):
a,b = X_L[i],X_L[i+1]
if a > b:
a,b = b,a
min_dist = min(b-a,N-(b-a))
max_dist = max(b-a,N-(b-a))
dist_diff = max_dist - min_dist
if b-a < N+a-b:
cost_L[0] += min_dist
cost_L[a] += dist_diff
cost_L[b] -= dist_diff
cost_L[N+1] -= min_dist
else:
cost_L[0] += max_dist
cost_L[a] -= dist_diff
cost_L[b] += dist_diff
cost_L[N+1] -= max_dist
for i in range(1,N+1):
cost_L[i] += cost_L[i-1]
print(min(cost_L[1:N+1]))
