Help us understand the problem. What is going on with this article?

競プロ精進日誌 #01 Equal Weight | JSC2019FinalA

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$)))でした.

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

解法2:FFT(NTT)

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした