JOI難易度６ 長いだけのネクタイ

問題原文

atcoder.jp

問題要旨

種類のネクタイと、 人の社員がいる。
各ネクタイの長さは であり、 各社員が最初につけているネクタイの長さは である。
について、以下の問に答えよ。

• 番目のネクタイを除いた 種類のネクタイを、各社員に１人１本ずつ割り当てる。
  このとき、各社員は割り当てられたネクタイの長さを , 最初につけていたネクタイの長さを とすると、 の違和感を感じる。
  全体の違和感の最大値を最小化せよ。

• 

解法

まず入力はソートしておく、元の位置を覚えておく必要があるのでよしなにやる。

わかりやすいので、, を考える。
すると、全ての場合の最小値は、 番目のネクタイを取り除いて をそれぞれソートして前から並べたものになる。
またこれは当たり前だけど、 番目のネクタイを取り除いた場合の答えになっている。

次に 番目のネクタイを取り除いた場合を考える。
この場合には、ネクタイ５を社員４に割り当てるのが最小値を達成する方法であるが、この値は として計算できる 。
（ 番目を取り除いた時が最小なのが確定しているので、 番目を取り除いた時の値はそれよりよくなる可能性がないため）

同じ感じで、直前の答えを持っておけばドミノ倒しのように各場合の答えが求められる。

解説スライドにわかりやすい図がのっている。
https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t1-review.pdf

実装

制約が厳しくてPythonには結構辛い。
PyPy2を持ち出してなんとかAC。（900ms）

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    A_with_index = sorted([[A[i], i] for i in range(N + 1)])
    P = [i for a, i in A_with_index]
 
    A = sorted(A)
    B = sorted(list(map(int, input().split())))
 
    ans = [-1] * (N + 1)
    tmp_ans = 0
    for a, b in zip(A, B):
        tmp_ans = max(tmp_ans, a - b)
    ans[P[-1]] = str(tmp_ans)
 
    for i in range(N)[::-1]:
        p, a, b = P[i], A[i + 1], B[i]
        tmp_ans = max(tmp_ans, a - b)
        ans[p] = str(tmp_ans)
 
    print(' '.join(ans))
 
 
if __name__ == '__main__':
    main()

感想

１部分だけ再計算 + それに直前の答えが使える、みたいなパターンかな？