ABC227 参加記録
コンテスト中AC:A,B
コンテスト後に自力AC:C,D,G
B - KEYENCE building
a*bの積の部分を考えると、a,bは1〜1000までの組み合わせとなり、N=20を考慮しても、全探索で程度になって間に合います。
C - ABC conjecture
計算量をある程度正確に見極めないとダメな問題でした。
という制約から、
として上界を見積もれます。
の時、となり、全探索するとくらいになって、一見間に合わなさそうです。
(なお、は]を満たすものを求めればよいので、A,Bが決定すれば、で求められるので無視できます。)
しかし、実際には
であるため、
くらいになるのは、が1桁の時だけです。
の桁数別にワーストの値を考えてみると、
・1桁(1〜9):300,000
・2桁(10〜99):100,000
・3桁(100〜999):30,000
・4桁(1000〜約5000):10,000
くらいとなります。割合としては、程度になることの方が多いことがわかります。
加えて、上記はすべて各桁数の最小値(1,10,100,1000)で見積もっているので、実際には更に定数倍軽くなります。
よって、全探索が可能そうなことがわかり、実際にC++で提出した下記コードはTLEになることなくACできました。
D - Project Planning
制約的にO(NlogN)がいけそうなので、二分探索を疑ってみます。
割り当て可能なプロジェクト数は、ある数を境に達成可能と不可能が分かれそうです。
(実際に、k個のプロジェクトが達成可能なら、そこからプロジェクトを1つ取り除けばk-1個も達成できますし、同様な理由でk個目が不可能でk+1個目が可能ということもあり得ません)
あとはプロジェクトの数を固定した時、それが達成可能かO(N)くらいで判定出来れば良いです。
(コンテスト中はこれが思い浮かばず)
判定は、以下の方法でO(N)で判定可能です。
「人数が最も少なく、かつ、部署iの人が入ることが可能な部署に順に配置する貪欲法を行い、最終的に全体にK人以上入っていれば達成可能である」
一例を示します。
部署をAからEまでの5つとし、そこに属する人をa,bのように小文字で表現します。
A : aaa
B : bb
C : ccccc
D : d
E : eee
プロジェクト0〜3までの4個とし、3人を配置する必要があるものとします。
1.部署Aの人を配置する。次に配置するプロジェクトは3。
[0] a
[1] a
[2] a
[3]
2.部署Bの人を配置する。次に配置するプロジェクトは1。全体に少なくとも1人いる。
[0] ab
[1] a
[2] a
[3] b
3.部署Cの人を配置する。5人は配置できない。次に配置するプロジェクトは1。各プロジェクトに少なくとも2人いる。
[0] abc
[1] ac
[2] ac
[3] bc
4.部署Dの人を配置する。次に配置するプロジェクトは2。
[0] abc
[1] acd
[2] ac
[3] bc
5.部署Eの人を配置する。各プロジェクトに少なくとも3人いる。
[0] abce
[1] acd
[2] ace
[3] bce
各プロジェクトに少なくとも3人いる状態となったので、プロジェクト数が4個は達成できる。
以上が判定方法です。
上記では、
・各プロジェクトに少なくとも何人いるかを示す変数
・次に挿入するプロジェクトは何かを示す変数
を管理します。
プロジェクトの個数をm個としたとき、各処理の際に、以下のように更新します。
・の更新
であれば、
・の更新
なら、更新しない。(例の3番目の操作に対応。1周して元に戻る)
そうでなければ、
計算量は最大プロジェクト数をMとして、と見積もれます。
Mが最悪となるケースは、
個のそれぞれの部署に人が居り、であるプロジェクトに配属されたとすると、プロジェクト数はくらいになります。
G - Divisors of Binomial Coefficient
別記事にまとめたいと思います。