SRM 505 Div2 Medium (500) PerfectSequences

入力シーケンスの和をsum,積をprodとすると
(prod/seq[i]) * x = (sum-seq[i]) + xとなるようなxが存在すればYesとなる.
言い換えるとsum-seq[i]が(prod/seq[i]) - 1で割り切れれば良い.
単純にprodを計算すると桁あふれを起こすので,各prod/seq[i]を計算する際(prod/seq[i])を超えた時点で計算をやめる(式を満たすような整数xは存在しない).

シーケンスの中に0があると少し厄介.0が一つだと変更される要素は0だけに限定,0が要素数-1あるときは残り一つを0にすれば成り立つ.それ以外は成り立たない.

class PerfectSequences {
public:
  string fixIt(vector <int> seq) {
    string res;
    int n = seq.size();

    if(n==1) return "Yes";
    int zero=0;
    for(int i=0; i < n;i++){
      if(seq[i] == 0) zero++;
    }
    if(zero==n-1)return "Yes";
    if(zero > 1) return "No";

    int i, j;
    int sum = 0;
    for(i = 0; i < n; i++) sum += seq[i];

    for(i = 0; i < n; i++){
      if(zero == 1 && seq[i] != 0) continue;
      bool check = true;
      long a = 1;
      for(j = 0; j < n; j++) if (i!=j){
          a *= seq[j];
          if ((a-1) > (sum-seq[i])){
            check = false;
            break;
          }
        }
      if (check && a > 1 && (((sum-seq[i]) % (a-1))==0) && ((sum-seq[i]) / (a-1)) != seq[i]) return "Yes";
    }
    return "No";
  }
};

2013.06.29.追記
復習中にもっとスッキリしたコードがかけたので掲載

class PerfectSequences {
public:
  string fixIt(vector <int> seq) {
    int i, j;
    int n = seq.size();
    for(i = 0; i < n; i++){
      long long x = 0;
      long long y = 1;
      for(j = 0; j < n; j++){
        if (i != j){
          x += seq[j];
          y *= seq[j];
        }
      }
      if ((y == 1 && x == 0) || (y > 1 && (x % (y-1) == 0) && (x/(y-1)) != seq[i])
          || (x == 0 && y == 0 && seq[i] != 0)){
        return "Yes";
      }
    }
    return "No";
  }
};