JSC(Japanese Student Championship)2019Final参加して，2完69位でした．
上位陣が化け物すぎました！

第一回日本最強プログラマー学生選手権 A問題

JSC2019FinalはA問題がdifficulty2000越えだったらしく, ひらめきが必要な問題でした．
解法も鳩ノ巣原理を使ったものとFFTを使ったものの2パターンがあったので，記録に残しておきます．

問題

問題概要：
N個のしゃりとM個のネタがある.
それぞれ重さは$A_i$,$B_j$で，ネタとしゃりを組み合わせて握りを作る．
同じ重さの握りを作りなさい．
同じネタやしゃりを使ってはいけない．ネタ同士，しゃり同士は互いに異なる重さ．二つ以上は握りを作ることが可能
制約：
$N,M\le2×10^5$
$A_i,B_j\le10^6$

コンテスト中は$N,M$の制約から愚直に探索した$O(NM)$は厳しいと判断した方が多かったみたいです．

解法１:鳩ノ巣原理

鳩ノ巣原理とは

n,mを自然数，n＞mとする．n個のものをm組にわけるとき，少なくともひとつの組は2個以上のものを含む．

はい．これ自体は当たり前のことですね．367人の人がいれば誕生日が同じ人は必ず1組は存在します．
ではこれを問題に当てはめます．

まずネタの重さの最大値を考えます．制約から$A_i+B_j\le2×10^6$.

つまり，$2×10^6+1$個の握りを作ったら，必ず同じものができるので,同じものができた時点で打ち切れば最大でも$2×10^6+1$回しかループが回ることはないです．

ということで計算量はO(min(NM,max($A_i+B_j$)))でした.

筆者の回答(C++,AC)

解法2:FFT(NTT)

著者FFTを競プロに応用することへの理解が浅いので，勉強して追記します．
とりあえず，ここまで．