ARC106 E - Medals O(N^2K)解法??
よくわからないが解説と違う方法だったので書く。
たぶん合っていると思うけど嘘を書いていたら撃墜してほしい。
解法(feeling):
自明な下界で常にメダルの分配がうまくいくとうれしい。なんかうまくいく。
以下の2点を考えるのがよい。
(1) 同じ周期 T の人たちが x 人いる
→ 周期 T の人の出勤日数が Kx 以上でなくてはいけない
(2) 1日に配れるメダルは1枚まで
→ 1人でも出勤しているような日の合計が NK 以上でなくてはいけない
結婚定理とかに思いを馳せると合っている気がしてくる。
(たぶん一番厳しい部分集合は全体集合)
投げると通る。