AtCoder:ABC112-D(partition)を解いた-ぐぐりらにっき

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。
## 問題

<a href="https://atcoder.jp/contests/abc112/tasks/abc112_d">D-Partition</a>

N,Mが与えられて、N個の自然数の列${a_i}$を考える。
この数列の和がMになるもののうち、この数列の最大公約数を最大にする数列を考えて、そのときの最大公約数を出力する問題。

最大公約数の最大、こんがらがる〜

## 考察

和が制約になっているときの最大公約数って関係ありそうだけどよくわからん、ってなったので数式にしてジッと睨む。

最大公約数が$d$だと、$d$でくくってあげることができるので、制約式の両辺を$d$で割る変形ができそう

割ったあとの左辺(数列の和の方)はN個項があって、それぞれ1以上でなきゃいけないから左辺はN以上、右辺はもちろん割り切れてなきゃいけない。

と、ここまで考えて、あー、逆にすればいいのか、と気づき、制約式の両辺を$d$で割るのではなく、括られた数式の方で割るようにしてみる。

とすれば、求める最大の最大公約数は

* Mの約数であり
* Mを割ったときの商がN以上

の中で最大のもの、となる。

## 実装

$M$が大きいので、Mの約数かどうかみるのに全部見ているとだめで、$\sqrt{M}$まで調べるという工夫が必要。

これをしないとTLEになります。

また、単純にやると間違えそうです。
例えば以下のように

```python
ans = 0
for i in range(1, int(np.sqrt(M)) + 2):
    if M % i == 0 and M // i >= N:
        ans = max(ans, i)

print(ans)
```
とすると間違えます。
$M$を割ったときに大きい方が$N$以上だったら小さい方を答えの候補に採用する、とやると、小さい方ですら$N$以上だった場合に間違いになります。

探索範囲を`np.sqrt(M)`にしているので、逆の場合を探索することなくループを出てしまうわけです。

もちろん範囲を$\sqrt{M}$ではなく$M$までにすればちゃんと更新されますが、先に書いた通りそれではTLEになります。

というわけで、このループの範囲の中で約数を一回につき2つだしてそれぞれ条件分岐する、みたいな書き方が必要なんかな、とおもって書き直すとこうなりました。

```python
ans = 0
for i in range(1, int(np.sqrt(M)) + 2):
    if M % i == 0:
        if min(M // i, i) >= N:
            ans = max(ans, max(M // i, i))
        elif max(M // i, i) >= N:
            ans = max(ans, min(M // i, i))

print(ans)
```
もちろんベストなのは小さい方の約数が$N$以上で、大きい方の約数を答えの候補にする、という状態なので先に分岐。
だめなら逆を試します。

両方$N$より小さいときはなにもしません。

AtCoder:ABC112-D(partition)を解いた

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT