perarduaadastra

競技プログラミングとかをしています

ARC106 E - Medals O(N^2K)解法??

atcoder.jp


 

よくわからないが解説と違う方法だったので書く。

たぶん合っていると思うけど嘘を書いていたら撃墜してほしい。

 

解法(feeling):

自明な下界で常にメダルの分配がうまくいくとうれしい。なんかうまくいく。

以下の2点を考えるのがよい。

 

(1) 同じ周期 T の人たちが x 人いる

→ 周期 T の人の出勤日数が Kx 以上でなくてはいけない

 

(2) 1日に配れるメダルは1枚まで

→ 1人でも出勤しているような日の合計が NK 以上でなくてはいけない

 

結婚定理とかに思いを馳せると合っている気がしてくる。

(たぶん一番厳しい部分集合は全体集合)

 

投げると通る。

 

atcoder.jp


atcoder.jp