倒錯思索ステイルメイト

愚問愚答観察。

AtCoder ARC A - Sum and Product

AtCoder ARC 解説記事 競プロ

おはようございます。久しぶりにAtcoder触ったので思い出しがてら記事を書きます。

久しぶりなので緩めの問題です。

問題

https://atcoder.jp/contests/arc108/tasks/arc108_a

  • S, P は整数．
  • N+M = S かつ N \times M = P を満たす整数 (N, M) の組が存在するか判定せよ．
  • 1 \leq S, P \leq 10^{12}

解法1

というわけでこれが整数となるかどうか，つまり平方根の中身が平方数かつ分子が偶数となっているかどうかを判定すれば良いです． しかし， P が小さいときのことを考えると平方数であるかどうかの判定に O(S) くらい掛かりそうですし，そもそもC++では long long 型であっても S^{2} でオーバーフローしてしまいます．

そこで補助変数 X := \sqrt{S^{2} - 4P} を導入すると以下の議論ができます．

  • X は整数( \because \displaystyle{N=\frac{S \pm X}{2}} が整数)．
  • X^{2} = S^{2} - 4P より， (S + X)(S - X) = 4P．
  • S + X,\ S - X も整数なのでこれらは 4P の約数．
  • A := S + X,\ B := S - X とすると \displaystyle{S = \frac{A+B}{2},\ X = \frac{A-B}{2}}

以上より， 4P の約数 A を O(\sqrt{P}) で列挙・探索し， \displaystyle{B=\frac{4P}{A}}としたときに，

  • \displaystyle{S = \frac{A+B}{2}} となるか．
  • \displaystyle{N=\frac{S \pm X}{2}} が整数か \Leftrightarrow S \pm X が偶数か．

を判定すればOKです．計算量は，約数列挙の部分がボトルネックとなり O(\sqrt{P})です．

解法2

https://atcoder.jp/contests/arc108/editorial/353

......たしかに！！

問題の本質がオーバーフローの解決だと勘違いして迂遠な解き方をしてしまいましたが，制約と積の形の時点でもっとシンプルな O(\sqrt{P}) の解法を思いつくべきでした．

解法3

ところで，解法1のように因数分解を利用するのであれば，

  • P の約数 N を全列挙．
  • \displaystyle{M := \frac{P}{N}} として， N + M = S かどうかを判定．

で良いことに気がつきました(え？)．回り道が上手．

実装

実装1 : 解の公式からごちゃごちゃやる

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

// retun n の約数の集合
vector<ll> divisors(ll n){
    vector<ll> div;
    for (ll i = 1; i * i <= n; i++) {
        if(n % i == 0) div.push_back(i);
    }
    for (auto d : div) {
        if(d * d != n) div.push_back(n / d);
    }
    return div;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll s, p;
    cin >> s >> p;

    vector<ll> div = divisors(4 * p);
    ll ng = 1;
    for (auto a : div) {
        ll b = 4 * p / a;
        if (a < b || (a + b) % 2) continue;
        ll x = (a - b) / 2;
        if ((a + b) / 2 == s && (s + x) % 2 == 0) {
            ng = 0;
            break;
        }
    }
    if (ng) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

実装2 : N の取りうる値の範囲を全探索

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll s, p;
    cin >> s >> p;

    int ng = 1;
    for (ll n = 1; n * n <= p; n++) {
        if (n * (s - n) == p) {
            ng = 0;
            break;
        }
    }
    if (ng) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

実装3 : N が取りうる値として P の約数を全探索

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

// retun n の約数の集合
vector<ll> divisors(ll n){
    vector<ll> div;
    for (ll i = 1; i * i <= n; i++) {
        if(n % i == 0) div.push_back(i);
    }
    for (auto d : div) {
        if(d * d != n) div.push_back(n / d);
    }
    return div;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll s, p;
    cin >> s >> p;

    vector<ll> div = divisors(p);
    ll ng = 1;
    for (auto n : div) {
        ll m = p / n;
        if (n + m == s) {
            ng = 0;
            break;
        }
    }
    if (ng) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

感想

迂遠な解法をやってしまうのってあまり良くないんですよね．仮にそれで解けるという確信を持ってたとしても，よりスマートな解法の方が実装がシンプルに済みがちなので(数式変形してるときには手計算によってプログラムに落とす量が減ると信じ切っているのが厄介ですが......)．

最近これの類題 https://atcoder.jp/contests/abc190/tasks/abc190_dでも同じようなことをしてしまったので気を付けたいところです．

次は(僕視点で)重めの問題を何か解いて紹介できたらなと思います．それではまた．