問題：F - Contrast
解答：Submission #19529927 - AtCoder Beginner Contest 178
解法：AとB合わせてN+1個以上含まれる数字がある場合は、どのように並べ替えてもAとBとでかぶる場所が生じてしまうためNoを出力する。実はそれ以外の場合はBを適切に並べ替えることにより、Aとかぶる数字をなくすことが出来る。さらにいうと、そのようなBの並べ方はシフトのみで実現できる。
C[i]を「Aの要素でi以下のものの個数」、D[i]を「Bの要素でi以下のものの個数」とする。このとき半区間(C[i-1], C[i]]はAの中でiが現れる場所を表現する。Bを右にx個シフトすることによりAとBがかぶらない状態にできるとするとき、全てのiについてC[i] ≦ x + D[i-1] かつ x + D[i] ≦ C[i-1] + Nが成り立つ（要素iがかぶらない条件）。これを整理すると、すべてのiに対し C[i] - D[i-1] ≦ x ≦ C[i-1] - D[i] + N という条件になる。このようなxが1つ存在することは証明できる（解説参考）ため、C[i] - D[i-1]の最大値をxとおけばよい。これは直感的には、「かぶらないようにするために最も右に動かさなくてはならない数字」に合わせてB全体を右シフトするようなイメージである。
