SRM505 Div2 Medium - PerfectSequences

問題

　与えられた整数列の要素を1つ非負の整数へ変化させたとき、要素全ての和と積が一致するかを判定せよ。

解法

　要素数が1つの時はどう変えても一致するので2つ以上の場合について考える。

　 $i$ 番目の要素を $j = 0, 1, \dots$ へと変化させることを考える。 $i$ 番目以外の要素の和を $s$ 、積を $p$ としたとき$$j + s = jp$$となればよい。したがって

$p = 0$ のとき、 $j + s = 0$ となることから $s = 0$ かつ元の $i$ 番目の要素が0でなければ"Yes"
$p = 1$ のとき、 $j + s = j$ となることから $s = 0$ であれば"Yes"
上記以外のとき $j$ を小さい順に試していき $j + s \lt jp$ となったら $i$ 番目の要素を変化させることでは一致しない

　という判定を $i = 1, 2, \dots$ についてやれば求まる。制約が緩いので計算量も問題ない。

反省

　コーナーケースに突っ込みまくっていくらかWAを出した。ここに書いたくらい見通し良い解法に練り上げてからコードを書き始めないと大変なバグが生まれまくる。

　オーバーフローの判定も入れないと一度はPassedと表示されるが数秒後にFailedとも出てくる。よくわからないがおそらくFailedなんだろう。そういうのも含めて結構時間かかってしまったし本番でちゃんと解ける気は一切しない。

コード

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

class PerfectSequences {
public:
    string fixIt(vector <int> seq) {
        ll N = (ll)seq.size();
        if (N == 1) {
            return "Yes";
        }
        vector<ll> sum_others(N, 0), pro_others(N, 1);
        vector<bool> pro_big(N, false);
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                if (j == i) {
                    continue;
                }
                sum_others[j] += seq[i];
                pro_others[j] *= seq[i];
                if (pro_others[j] > 1e9 * 50) {
                    pro_big[j] = true;
                }
            }
        }
        for (ll i = 0; i < N; i++) {
            if (pro_others[i] == 0) {
                if (sum_others[i] == 0 && seq[i] != 0) {
                    return "Yes";
                }
                continue;
            } else if (pro_others[i] == 1) {
                if (sum_others[i] == 0) {
                    return "Yes";
                }
                continue;
            } else if (pro_big[i]) {
                continue;
            }
            for (ll j = 0; ; j++) {
                if (j == seq[i]) {
                    continue;
                }
                ll sum = sum_others[i] + j;
                ll pro = pro_others[i] * j;
                if (sum == pro) {
                    return "Yes";
                } else if (sum < pro) {
                    break;
                }
            }
        }
        return "No";
    }
};