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)$は厳しいと判断した方が多かったみたいです.
解法1:鳩ノ巣原理
鳩ノ巣原理とは
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$)))でした.
解法2:FFT(NTT)
著者FFTを競プロに応用することへの理解が浅いので,勉強して追記します.
とりあえず,ここまで.