A - 長いだけのネクタイ (Just Long Neckties)
最初はDPと思っていたけど，sortして，順番に計算していけばよい．A，B のどちらも昇順でsortして前から順番に差を求めたときに"奇妙さが"が最小になる．最小値になるネクタイ以外を除いた場合は，もちろん最小値以上になるので，前に値と比較して更新していく．図を持ちいた分かりやすい解説．参考にした記事
from sys import stdin input = stdin.readline n = int(input().strip()) a = list(map(int, input().strip().split())) b = list(map(int, input().strip().split())) sort_a = [] for i in range(n + 1): sort_a.append([a[i], i]) a.sort() sort_a.sort() b.sort() p =[i[1] for i in sort_a] #p[i]，sortされたi番目の要素の元々のindex ans = [-1] * (n + 1) tmp_ans = 0 for i, j in zip(a, b): tmp_ans = max(i - j, tmp_ans) ans[p[-1]] = str(tmp_ans) #joinできるようにsrtにする for i in reversed(range(n)): tmp_ans = max(a[i + 1] - b[i], tmp_ans) #ネクタイをずらす ans[p[i]] = str(tmp_ans) #joinできるようにsrtにする print(' '.join(ans))
できたこと
- 最小値になるのは，Aを昇順でsortしたときになること
学んだこと
- 多次元配列をinで引っぱてくるときに，その要素数と同じ数の変数で受けとれる
- indexと要素を一緒にもって考える．←けっこう使う
