ABC169

過去最高に厳しいABCだった．BとC通せなかったのはそれぞれ1ケースだけWAだったがそのせいでレートを失った．

atcoder.jp

結果

問題	ACまでに要した時間	AC	WA	TLE
A	0:45	1	0	0
B	:	0	2	0
C	:	0	2	0
D	52:03	1	0	0
E	:	0	0	0
F	:	0	0	0

新Rating	Performance	順位
636 (-4)	598	5786

解答

B

1ケースだけWAで死んだ．原因はなにか？

オーバーフロー判定をアホみたいに愚直に書いてそれが動かないケースを踏んだらしい．

だめなやつ

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N) { cin >> A.at(i); }
  sort(A.begin(), A.end(), greater<ll>());
  if (A.at(N - 1) == 0) {
    cout << 0 << endl;
    return 0;
  }

  ll const MAX = 1000000000000000000;
  ll ans = 1ll;
  ll prev_ans = ans;

  REP(i, N) {
    ans *= A.at(i);
    if (ans / A.at(i) != prev_ans) {
      ans = -1;
      break;
    }
    prev_ans = ans;
  }

  if (ans > MAX) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }

  return 0;
}

この実装だと

2
4294967296 4294967296

みたいなケースで4294967296と4294967296の計算をした時点で結果が0になりおかしくなる．これはこの積がちょうどunsigned long longの最大値+1になるためである．

ではこれを回避するにはどうするか．long longの代わりにunsinged long longを使うとこのケースは通せてACになるが，なぜこれがACになるのか良くわかっていない．．．

ただしくは積を取る前に掛けても大丈夫かを判定する．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N) { cin >> A.at(i); }
  sort(A.begin(), A.end(), greater<ll>());
  if (A.at(N - 1) == 0) {
    cout << 0 << endl;
    return 0;
  }

  ll const MAX = 1000000000000000000;
  ll ans = 1;

  REP(i, N) {
    if (A.at(i) > MAX / ans) {
      ans = -1;
      break;
    }
    ans *= A.at(i);
  }

  if (ans > MAX) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }

  return 0;
}

C

同じく1ケースだけWAで死んだ．

不動点少数を整数にしたかったのでBを100倍してから積をとったが実はこのタイミングで誤差が出る．

ABC169-Cの犯人一覧です pic.twitter.com/H4zrgf8MuK

— アトム (@atom_HeV) 2020年5月31日

これに気づかなかったのが今回の敗因．

正しくはstringとしてBを受け取り，小数点を取り除いてからstollしてlong longに変換して計算する．こうすれば数学的な結果と一致する．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll A;
  string B;
  cin >> A >> B;
  B.erase(1, 1);
  ll C = stoll(B);
  cout << A * C / 100 << endl;

  return 0;
}

D

問題文の通り愚直に解いても，素因数分解と素数判定にそれぞれなので計算量的には解ける．もっと効率がいい解き方があるような気がするが今回は愚直に解いた．

B問題，C問題に比べたら「設問に従って解くだけ」なので相当簡易な問題であり，なぜこれがD問題なのか疑問が湧いた．これ200点問題でもよかったのではないか．．．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

bool f2(ll v) {
  if (v <= 2) {
    return true;
  }

  bool ans = true;
  for (ll i = 2; i * i <= v; ++i) {
    if (v % i == 0) {
      ans = false;
      break;
    }
  }

  return ans;
}

vector<ll> f(ll v) {
  vector<ll> ans;
  for (ll i = 2; i * i <= v; ++i) {
    if (v % i == 0) {
      ans.push_back(i);
      if (i * i != v)
        ans.push_back(v / i);
    }
  }
  return ans;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll N;
  cin >> N;
  vector<ll> y = f(N);
  y.push_back(N);

  vector<ll> p;
  for (ll i : y) {
    if (f2(i)) {
      p.push_back(i);
    }
  }

  vector<ll> p2(p);
  for (ll v : p) {
    ll v2 = v * v;
    if (v2 < 0) {
      continue;
    }
    while (v2 < N) {
      p2.push_back(v2);
      v2 *= v;
      if (v2 < 0) {
        break;
      }
    }
  }
  sort(p2.begin(), p2.end());

  ll ans = 0;
  ll c = 0;
  ll idx_mx = p2.size();
  while (N > 1 && c < idx_mx) {
    bool flg = false;
    for (int i = 0; i < idx_mx; ++i) {
      if (p2.at(i) == -1) {
        continue;
      }
      if (N % p2.at(i) == 0) {
        N /= p2.at(i);
        p2.at(i) = -1;
        flg = true;
        break;
      }
    }
    if (!flg) {
      break;
    }

    ++c;
    ++ans;
  }

  cout << ans << endl;

  return 0;
}

ダメだった点

オーバーフロー判定がうまく書けなかった（というかこれはやるべきではなかった）のと計算誤差の配慮が甘すぎた．アルゴリズムと関係ないところで落として本当に情けない結果となった．一応これでもCSで工学修士とった身なのでこれは解けないといけなかった．

良かった点

一応D通して2完にできたのはまぁギリギリ救われた．1完だったら立ち直れなかったかもしれない．

おわりに

• 小数点演算はやらない
• オーバーフロー判定を書かないといけないと思ったらなにかおかしいと考える