geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC227 参加記録

コンテスト中AC:A,B

コンテスト後に自力AC:C,D,G

 

 

 

B - KEYENCE building

a*bの積の部分を考えると、a,bは1〜1000までの組み合わせとなり、N=20を考慮しても、全探索で10^7程度になって間に合います。

提出コード

 

C - ABC conjecture

計算量をある程度正確に見極めないとダメな問題でした。

 

A \leq B \leq C

という制約から、

A\leq \sqrt[3]{N} ,\ B \leq \sqrt{N}

として上界を見積もれます。

10^{11}の時、\sqrt[3]{N} \simeq 5,000, \sqrt{N} \simeq 300,000となり、全探索すると10^9くらいになって、一見間に合わなさそうです。

(なお、CB \leq C \leq \sqrt{\lfloor \frac{N}{AB} \rfloor}]を満たすものを求めればよいので、A,Bが決定すれば、O(1)で求められるので無視できます。)

 

しかし、実際には

B \leq \sqrt{\lfloor \frac{N}{A} \rfloor}

であるため、

300,000くらいになるのは、Aが1桁の時だけです。

Aの桁数別にワーストの値を考えてみると、

・1桁(1〜9):300,000

・2桁(10〜99):100,000

・3桁(100〜999):30,000

・4桁(1000〜約5000):10,000

くらいとなります。割合としては、10^4程度になることの方が多いことがわかります。

加えて、上記はすべて各桁数の最小値(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個は達成できる。

以上が判定方法です。

 

上記では、

・各プロジェクトに少なくとも何人いるかを示す変数X

・次に挿入するプロジェクトは何かを示す変数num

を管理します。
プロジェクトの個数をm個としたとき、各処理の際に、以下のように更新します。

 

Xの更新

num+A_i \geq mであれば、X \leftarrow X+1

 

numの更新

A_i \gt Kなら、更新しない。(例の3番目の操作に対応。1周して元に戻る)

そうでなければ、num \leftarrow (num+A_i)\ mod\ m

 

計算量は最大プロジェクト数をMとして、O(NlogM)と見積もれます。

Mが最悪となるケースは、

2\times 10^5個のそれぞれの部署に10^{12}人が居り、K = 1であるプロジェクトに配属されたとすると、プロジェクト数は2\times 10^{17}くらいになります。

提出コード

 

G - Divisors of Binomial Coefficient

別記事にまとめたいと思います。

提出コード