ABC474 D - Outweigh

考え方

直感的に、以下のようにしたくなる。

• 高橋君の方がたくさん持っているものはなるべく重い方がいいので $10^{18}$ にする
• 青木君の方がたくさん持っているものはなるべく軽い方がいいので $1$ にする
• 同じである場合は、何にしても影響がないので範囲内で適当に設定する
  • $10^{18}$ にすると話がややこしくなる（以下の説明が成立しなくなる）ので、$1$ にすると無難

そして、$10^{18}$ にした石が $1$ つでもあればこれを出力、なければ不可能判定、で正解である。
計算量は $O(N)$ である。

以下、これで正しいことの証明。

まず、$10^{18}$ にした石が $1$ つもない場合。
この場合、全ての種類の石を青木君が高橋君以上に持っている。
したがって、高橋君が青木君を上回ることは絶対にないことは明らか。

次に、$10^{18}$ にした石が $1$ つでもあった場合。
$10^{18}$ にした石の分だけを見ると、高橋君の方がこれを $1$ つ以上多く持っている。
よって、それにより生じる差は、少なくとも $10^{18}$ ある。
$1$ にした石の分だけ見ると、その種類数は $10^5$ より小さく、各種の個数差は $10^9$ より小さい。
よって、それにより生じる差は、多くとも $10^{14}$ となる。
したがって、必ず高橋君の方が重くなっている。

以上、証明終わり。

入力例1での動作

入力を受け取る。

n: 3
a: {4, 7, 4}
b: {5, 5, 5}

各種類について、高橋君の方が多く持っているかを確認する。

$2$ 種類目では高橋君の方が多く持っているので、$10^{18}$ にした石が $1$ つ以上ある。
したがって、条件を満たす構築が以下のように可能である。

w: {1, 1000000000000000000, 1}

注意点

この方法で作ったものが本当に条件を満たすか確認すると、long long 型でもオーバーフロー。
手作業で証明して、コードには構築方法だけを書くこと。

別解

特になし。