第一回日本最強プログラマー学生選手権決勝 A. Equal Weight

問題

N個のシャリAとM個のネタBがあり、シャリiの重さはAi、ネタjの重さはBjで与えられる。
ここで、寿司の握りはシャリとネタ1つずつの組み合わせで作ることができ、同じ重さの寿司を2つ作りたい。
これが可能かどうか判定し、可能な場合は組み合わせのインデクスを1つ出力せよ。不可能な場合は-1を出力せよ。

制約

• 2 <= N, M <= 2*10^5
• 1 <= Ai, Bj <= 10^6
• 同じ重さのシャリは存在しない
• 同じ重さのネタは存在しない

解法1

N,Mが大きい時を考える。

シャリとネタの重さの組み合わせは2*10^6までしかないため、鳩ノ巣原理から、それ以上の組み合わせを生成した場合、同じ重さになる寿司が1つは必ず現れる。

したがって、重さをメモりながらシャリとネタの組み合わせを全部列挙するように書くと、2*10^6程度で必ず見つかるか、列挙が終わる。

解法2

Xi := Aの中に重さiのシャリがあるか(1か0)
Yi := Bの中に重さiのネタがあるか(1か0)
と定義し、その畳み込みZi = Σ^i_{j=0} X_j*Y_{i-j}を考えると、
これは「同じ重さiになるシャリ/ネタのペアの個数」になる。

この畳みこみはFFTを行うとO(NlogN)で求められるので、実装次第で通せる。
(doubleで計算していると間に合わなかったけどfloatにすると間に合った。計算精度はわらかない・・・怪しいかも。テストケースによる？)