Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@480_AC

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

More than 1 year has passed since last update.

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を競プロに応用することへの理解が浅いので,勉強して追記します.
とりあえず,ここまで.

0
Help us understand the problem. What is going on with this article?
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.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?