ABC112-D

README

ABC112 D. Partition

@2020-04-26

3WAで自力AC。

想定解法と違った汚い解き方をしてしまった。

想定解法は、「解の候補が M の約数かつ M/N 以下の整数のなかで最大もの」となる。 つまりは約数列挙の問題になるため、計算量は O(sart(M)) となる。 これは、答えの性質から素直に導ける。

。。自分は根本的な性質には気づけたが、全探索は調和級数的なオーダーに落ちるような範囲でやってしまった。 つまり、 2, 4, 8... という感じでべき乗のものも一緒に調べていく方法をとった。 多分、嘘解法ではないと思う。。

また復習してもいい問題。