競プロ日記

コード
行列累乗
https://atcoder.jp/contests/abc129/submissions/7196508
ダブリング①
https://atcoder.jp/contests/abc129/submissions/7196517
ダブリング②
https://atcoder.jp/contests/abc129/submissions/7196857


しんどい！！！
E問題も相当かかったしABC129は強敵だった。
E問題は単純に桁DPを知るだけで終わったから特に書くことはないが、これは本当にしんどかった。
最初尋常じゃない定義域も相まって解き方の検討がつかなかったが、解説を読んでこういうのも漸化式で解けるのかと感心した。

行列累乗

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto &&V : v)
#define all(x) (x).begin(), (x).end()
constexpr int INF = 1 << 30;
constexpr long long INFL = 1LL << 62;
constexpr int MOD = 1e9 + 7;
constexpr double EPS = 1e-9;
using lint = long long;

using namespace std;

class VariableModInt {
  long long n_;
  static long long &mod() {
    static long long mod_ = 1;
    return mod_;
  }

  public:
  VariableModInt(const long long num = 0) : n_(num % get_mod()) {}
  const long long &value() const { return n_; }
  bool operator==(const VariableModInt &r) const { return this->n_ == r.n_; }
  bool operator==(const long long &r) const { return this->n_ == r; }
  bool operator!=(const VariableModInt &r) const { return this->n_ != r.n_; }
  bool operator!=(const long long &r) const { return this->n_ != r; }
  bool operator<(const VariableModInt &r) const { return this->n_ < r.n_; }
  bool operator<(const long long &r) const { return this->n_ < r; }
  bool operator>(const VariableModInt &r) const { return this->n_ > r.n_; }
  bool operator>(const long long &r) const { return this->n_ > r; }
  bool operator<=(const VariableModInt &r) const { return this->n_ <= r.n_; }
  bool operator<=(const long long &r) const { return this->n_ <= r; }
  bool operator>=(const VariableModInt &r) const { return this->n_ >= r.n_; }
  bool operator>=(const long long &r) const { return this->n_ >= r; }
  VariableModInt operator+(const VariableModInt &r) const { return VariableModInt(*this) += r; }
  VariableModInt operator-(const VariableModInt &r) const { return VariableModInt(*this) -= r; }
  VariableModInt operator*(const VariableModInt &r) const { return VariableModInt(*this) *= r; }
  VariableModInt operator/(const VariableModInt &r) const { return VariableModInt(*this) /= r; }
  VariableModInt operator+(const long long &r) const { return VariableModInt(*this) += VariableModInt(r); }
  VariableModInt operator-(const long long &r) const { return VariableModInt(*this) -= VariableModInt(r); }
  VariableModInt operator*(const long long &r) const { return VariableModInt(*this) *= VariableModInt(r); }
  VariableModInt operator/(const long long &r) const { return VariableModInt(*this) /= VariableModInt(r); }
  friend VariableModInt operator+(const long long &l, const VariableModInt &r) { return VariableModInt(l) += r; }
  friend VariableModInt operator-(const long long &l, const VariableModInt &r) { return VariableModInt(l) -= r; }
  friend VariableModInt operator*(const long long &l, const VariableModInt &r) { return VariableModInt(l) *= r; }
  friend VariableModInt operator/(const long long &l, const VariableModInt &r) { return VariableModInt(l) /= r; }
  VariableModInt &operator++() { return *this += 1; }
  VariableModInt &operator--() { return *this -= 1; }
  VariableModInt &operator+=(const VariableModInt &r) {
    n_ += r.n_;
    if (n_ >= get_mod()) n_ -= get_mod();
    return *this;
  }
  VariableModInt &operator-=(const VariableModInt &r) {
    if (n_ < r.n_) n_ += get_mod();
    n_ -= r.n_;
    return *this;
  }
  VariableModInt &operator*=(const VariableModInt &r) {
    n_ = n_ * r.n_ % get_mod();
    return *this;
  }
  VariableModInt &operator/=(VariableModInt r) {
    long long exp = get_mod() - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r *= r;
      exp /= 2;
    }
    return *this;
  }
  static void set_mod(const long long mod_num) { mod() = mod_num; }
  static long long get_mod() { return mod(); }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
  friend std::istream &operator>>(std::istream &is, VariableModInt &r) {
    is >> r.n_;
    r.n_ %= r.get_mod();
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const VariableModInt &r) { return os << r.n_; }
};

template 
class Matrix {
  int h_, w_;
  std::vector<std::vector> mat_;

  public:
  Matrix(void) {}
  Matrix(size_t n) : h_(n), w_(n), mat_(h_, std::vector(w_)) {}
  Matrix(size_t height, size_t width) : h_(height), w_(width), mat_(h_, std::vector(w_)) {}
  Matrix(size_t height, size_t width, T initial) : h_(height), w_(width), mat_(h_, std::vector(w_, initial)) {}
  Matrix(std::initializer_list<std::initializer_list> list_2d) : h_(list_2d.size()), w_(list_2d.begin()->size()), mat_(list_2d.begin(), list_2d.end()) {
    for (const auto &list : list_2d) assert(w_ == list.size());
  }
  const std::vector &operator[](size_t k) const { return mat_[k]; }
  std::vector &operator[](size_t k) { return mat_[k]; }
  Matrix operator+(const Matrix &rmat) const { return (Matrix(*this) += rmat); }
  Matrix operator-(const Matrix &rmat) const { return (Matrix(*this) -= rmat); }
  Matrix operator*(const Matrix &rmat) const { return (Matrix(*this) *= rmat); }
  Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); }
  Matrix operator*(const T &n) const { return (Matrix(*this) *= n); }
  friend Matrix operator*(const T &t, const Matrix &rmat) { return (Matrix(rmat) *= t); }
  Matrix &operator+=(const Matrix &rmat) {
    assert(h_ == rmat.h_ && w_ == rmat.w_);
    for (int i = 0; i < h_; ++i) {
      for (int j = 0; j < w_; ++j) {
        mat_[i][j] += rmat[i][j];
      }
    }
    return *this;
  }
  Matrix &operator-=(const Matrix &rmat) {
    assert(h_ == rmat.h_ && w_ == rmat.w_);
    for (int i = 0; i < h_; ++i) {
      for (int j = 0; j < w_; ++j) {
        mat_[i][j] -= rmat[i][j];
      }
    }
    return *this;
  }
  Matrix &operator*=(const Matrix &rmat) {
    assert(w_ == rmat.h_);
    std::vector<std::vector> nmat(h_, std::vector(rmat.w_));
    for (int i = 0; i < h_; ++i) {
      for (int k = 0; k < w_; ++k) {
        for (int j = 0; j < rmat.w_; ++j) {
          nmat[i][j] += mat_[i][k] * rmat[k][j];
        }
      }
    }
    mat_.swap(nmat);
    w_ = rmat.w_;
    return *this;
  }
  Matrix &operator*=(const int n) {
    for (int i = 0; i < h_; ++i) {
      for (int j = 0; j < w_; ++j) {
        mat_[i][j] *= n;
      }
    }
    return *this;
  }
  Matrix &operator^=(long long k) {
    assert(h_ == w_);
    Matrix imat(h_);
    for (int i = 0; i < h_; ++i) imat[i][i] = 1;
    while (k > 0) {
      if (k & 1) imat *= *this;
      *this *= *this;
      k >>= 1;
    }
    mat_.swap(imat.mat_);
    return *this;
  }
  int height(void) { return h_; }
  int width(void) { return w_; }
  T max_value() {
    T maxi = *std::max_element(mat_[0].begin(), mat_[0].end());
    for (int i = 1; i < h_; ++i) maxi = std::max(maxi, *std::max_element(mat_[i].begin(), mat_[i].end()));
    return maxi;
  }
  T min_value() {
    T mini = *std::min_element(mat_[0].begin(), mat_[0].end());
    for (int i = 1; i < h_; ++i) mini = std::min(mini, *std::min_element(mat_[i].begin(), mat_[i].end()));
    return mini;
  }
  friend ostream &operator<<(ostream &os, Matrix &mat) {
    int digit = std::log10((double)mat.max_value()) + 2;
    for (int i = 0; i < mat.h_; ++i) {
      os << "[";
      for (int j = 0; j < mat.w_; ++j) {
        os << std::setw(digit) << mat[i][j] << (j + 1 == mat.w_ ? " ]\n" : ",");
      }
    }
    return os;
  }
  // External
  Matrix transpose(void);
  T determinant(void);
  T rational_determinant(void);
};

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

  lint l, a, b, m;
  cin >> l >> a >> b >> m;
  vector k;
  k.push_back(0);
  lint x = 1;
  rep1 (i, 18) {
    x *= 10;
    if (x - a < 0) {
      k.push_back(0);
    } else {
      lint t = min((x - 1 - a) / b + 1, l);
      k.push_back(t);
      if (t == l) break;
    }
  }
  VariableModInt::set_mod(m);
  Matrix product_mat{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  rrep1(i, k.size() - 1) {
    lint len = k[i] - k[i - 1];
    if (len <= 0) continue;
    Matrix mat{{1, 0, b}, {1, x, 0}, {0, 0, 1}};
    mat ^= len;
    product_mat *= mat;
    x /= 10;
  }
  Matrix init{{a}, {0}, {1}};
  product_mat *= init;
  cout << product_mat[1][0] << endl;
  return 0;
}

行列ってこういう使い方ができるのかぁという感想。
連立方程式を行列にして～みたいな計算も学生時代一瞬で終わってしまったからほぼ記憶になかった。
そもそも漸化式を作ることすら発想になかったので、もし漸化式を作っていたら蟻本の記憶で思いついた可能性もなきにしもあらず・・・。
こういう線形変換をアフィン変換というらしいけど初耳。
同次変換行列は勉強した記憶があるのでそっちのイメージのほうが強い。
実装に取り掛かってみるととても簡単。
行列の実装が相当しんどかった。
今回使わなかった行列式を有理数の演算で実装したのが悪い。

ダブリング

①

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto &&V : v)
#define all(x) (x).begin(), (x).end()
constexpr int INF = 1 << 30;
constexpr long long INFL = 1LL << 62;
constexpr int MOD = 1e9 + 7;
constexpr double EPS = 1e-9;
using lint = long long;

using namespace std;

class VariableModInt {
  long long n_;
  static long long &mod() {
    static long long mod_ = 1;
    return mod_;
  }

  public:
  VariableModInt(const long long num = 0) : n_(num % get_mod()) {}
  const long long &value() const { return n_; }
  bool operator==(const VariableModInt &r) const { return this->n_ == r.n_; }
  bool operator==(const long long &r) const { return this->n_ == r; }
  bool operator!=(const VariableModInt &r) const { return this->n_ != r.n_; }
  bool operator!=(const long long &r) const { return this->n_ != r; }
  bool operator<(const VariableModInt &r) const { return this->n_ < r.n_; }
  bool operator<(const long long &r) const { return this->n_ < r; }
  bool operator>(const VariableModInt &r) const { return this->n_ > r.n_; }
  bool operator>(const long long &r) const { return this->n_ > r; }
  bool operator<=(const VariableModInt &r) const { return this->n_ <= r.n_; }
  bool operator<=(const long long &r) const { return this->n_ <= r; }
  bool operator>=(const VariableModInt &r) const { return this->n_ >= r.n_; }
  bool operator>=(const long long &r) const { return this->n_ >= r; }
  VariableModInt operator+(const VariableModInt &r) const { return VariableModInt(*this) += r; }
  VariableModInt operator-(const VariableModInt &r) const { return VariableModInt(*this) -= r; }
  VariableModInt operator*(const VariableModInt &r) const { return VariableModInt(*this) *= r; }
  VariableModInt operator/(const VariableModInt &r) const { return VariableModInt(*this) /= r; }
  VariableModInt operator+(const long long &r) const { return VariableModInt(*this) += VariableModInt(r); }
  VariableModInt operator-(const long long &r) const { return VariableModInt(*this) -= VariableModInt(r); }
  VariableModInt operator*(const long long &r) const { return VariableModInt(*this) *= VariableModInt(r); }
  VariableModInt operator/(const long long &r) const { return VariableModInt(*this) /= VariableModInt(r); }
  friend VariableModInt operator+(const long long &l, const VariableModInt &r) { return VariableModInt(l) += r; }
  friend VariableModInt operator-(const long long &l, const VariableModInt &r) { return VariableModInt(l) -= r; }
  friend VariableModInt operator*(const long long &l, const VariableModInt &r) { return VariableModInt(l) *= r; }
  friend VariableModInt operator/(const long long &l, const VariableModInt &r) { return VariableModInt(l) /= r; }
  VariableModInt &operator++() { return *this += 1; }
  VariableModInt &operator--() { return *this -= 1; }
  VariableModInt &operator+=(const VariableModInt &r) {
    n_ += r.n_;
    if (n_ >= get_mod()) n_ -= get_mod();
    return *this;
  }
  VariableModInt &operator-=(const VariableModInt &r) {
    if (n_ < r.n_) n_ += get_mod();
    n_ -= r.n_;
    return *this;
  }
  VariableModInt &operator*=(const VariableModInt &r) {
    n_ = n_ * r.n_ % get_mod();
    return *this;
  }
  VariableModInt &operator/=(VariableModInt r) {
    long long exp = get_mod() - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r *= r;
      exp /= 2;
    }
    return *this;
  }
  static void set_mod(const long long mod_num) { mod() = mod_num; }
  static long long get_mod() { return mod(); }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
  friend std::istream &operator>>(std::istream &is, VariableModInt &r) {
    is >> r.n_;
    r.n_ %= r.get_mod();
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const VariableModInt &r) { return os << r.n_; }
};

using mint = VariableModInt;

mint f(lint i, mint &tenk, lint ten) {
  static map<tuple<lint, lint>, mint> memory;
  if (memory.find(tuple<lint, lint>(i, ten)) != memory.end()) return memory[tuple<lint, lint>(i, ten)];
  if (i == 0) return 0;
  mint ft;
  if (i & 1) {
    ft = f(i - 1, tenk, ten);
    ft = ft * ten + 1;
    tenk *= ten;
  } else {
    ft = f(i / 2, tenk, ten);
    ft = ft * (tenk + 1);
    tenk *= tenk;
  }
  return memory[tuple<lint, lint>(i, ten)] = ft;
}

mint g(lint i, mint &tenk, lint ten, mint &B, lint plusi) {
  if (i == 0) return 0;
  mint gt;
  if (i & 1) {
    lint bi = i - 1;
    gt = g(bi, tenk, ten, B, plusi);
    gt = gt * ten + B * (plusi + bi);
    tenk *= ten;
  } else {
    lint bi = i / 2;
    mint ctenk(tenk);
    gt = g(bi, tenk, ten, B, plusi);
    gt = gt * (tenk + 1) + B * bi * f(bi, ctenk, ten);
    tenk *= tenk;
  }
  return gt;
}

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

  lint l, a, b, m;
  cin >> l >> a >> b >> m;
  vector k;
  k.push_back(0);
  lint x = 1;
  rep1 (i, 18) {
    x *= 10;
    if (x - a < 0) {
      k.push_back(0);
    } else {
      lint t = (x - 1 - a) / b + 1;
      if (t > l) {
        k.push_back(l);
        break;
      }
      k.push_back(t);
    }
  }
  mint::set_mod(m);
  mint sum = 0;
  x = 1;
  mint A = a, B = b;
  rep1 (i, k.size() - 1) {
    x *= 10;
    lint len = k[i] - k[i - 1];
    if (len <= 0) continue;
    mint fk = 1, gk = 1;
    auto F = f(len, fk, x);
    auto G = g(len, gk, x, B, k[i - 1]);
    sum = sum * fk + A * F + G;
  }
  cout << sum << endl;
  return 0;
}

②

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto &&V : v)
#define all(x) (x).begin(), (x).end()
constexpr int INF = 1 << 30;
constexpr long long INFL = 1LL << 62;
constexpr int MOD = 1e9 + 7;
constexpr double EPS = 1e-9;
using lint = long long;

using namespace std;

class VariableModInt {
  long long n_;
  static long long &mod() {
    static long long mod_ = 1;
    return mod_;
  }

  public:
  VariableModInt(const long long num = 0) : n_(num % get_mod()) {}
  const long long &value() const { return n_; }
  bool operator==(const VariableModInt &r) const { return this->n_ == r.n_; }
  bool operator==(const long long &r) const { return this->n_ == r; }
  bool operator!=(const VariableModInt &r) const { return this->n_ != r.n_; }
  bool operator!=(const long long &r) const { return this->n_ != r; }
  bool operator<(const VariableModInt &r) const { return this->n_ < r.n_; }
  bool operator<(const long long &r) const { return this->n_ < r; }
  bool operator>(const VariableModInt &r) const { return this->n_ > r.n_; }
  bool operator>(const long long &r) const { return this->n_ > r; }
  bool operator<=(const VariableModInt &r) const { return this->n_ <= r.n_; }
  bool operator<=(const long long &r) const { return this->n_ <= r; }
  bool operator>=(const VariableModInt &r) const { return this->n_ >= r.n_; }
  bool operator>=(const long long &r) const { return this->n_ >= r; }
  VariableModInt operator+(const VariableModInt &r) const { return VariableModInt(*this) += r; }
  VariableModInt operator-(const VariableModInt &r) const { return VariableModInt(*this) -= r; }
  VariableModInt operator*(const VariableModInt &r) const { return VariableModInt(*this) *= r; }
  VariableModInt operator/(const VariableModInt &r) const { return VariableModInt(*this) /= r; }
  VariableModInt operator+(const long long &r) const { return VariableModInt(*this) += VariableModInt(r); }
  VariableModInt operator-(const long long &r) const { return VariableModInt(*this) -= VariableModInt(r); }
  VariableModInt operator*(const long long &r) const { return VariableModInt(*this) *= VariableModInt(r); }
  VariableModInt operator/(const long long &r) const { return VariableModInt(*this) /= VariableModInt(r); }
  friend VariableModInt operator+(const long long &l, const VariableModInt &r) { return VariableModInt(l) += r; }
  friend VariableModInt operator-(const long long &l, const VariableModInt &r) { return VariableModInt(l) -= r; }
  friend VariableModInt operator*(const long long &l, const VariableModInt &r) { return VariableModInt(l) *= r; }
  friend VariableModInt operator/(const long long &l, const VariableModInt &r) { return VariableModInt(l) /= r; }
  VariableModInt &operator++() { return *this += 1; }
  VariableModInt &operator--() { return *this -= 1; }
  VariableModInt &operator+=(const VariableModInt &r) {
    n_ += r.n_;
    if (n_ >= get_mod()) n_ -= get_mod();
    return *this;
  }
  VariableModInt &operator-=(const VariableModInt &r) {
    if (n_ < r.n_) n_ += get_mod();
    n_ -= r.n_;
    return *this;
  }
  VariableModInt &operator*=(const VariableModInt &r) {
    n_ = n_ * r.n_ % get_mod();
    return *this;
  }
  VariableModInt &operator/=(VariableModInt r) {
    long long exp = get_mod() - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r *= r;
      exp /= 2;
    }
    return *this;
  }
  static void set_mod(const long long mod_num) { mod() = mod_num; }
  static long long get_mod() { return mod(); }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
  friend std::istream &operator>>(std::istream &is, VariableModInt &r) {
    is >> r.n_;
    r.n_ %= r.get_mod();
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const VariableModInt &r) { return os << r.n_; }
};

template 
T power(T x, long long n) {
  T ret = 1;
  while (n) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
}

using mint = VariableModInt;

mint pow_10(lint k) {
  static unordered_map<lint, mint> memory{{0, 1}};
  if (memory.find(k) != memory.end()) return memory[k];
  if (k & 1) {
    return memory[k] = pow_10(k - 1) * 10;
  } else {
    mint x = pow_10(k / 2);
    return memory[k] = x * x;
  }
}

mint f(lint i, int k) {
  static map<tuple<lint, int>, mint> memory;
  if (memory.find(pair<lint, int>(i, k)) != memory.end()) return memory[pair<lint, int>(i, k)];
  if (i == 0) return 0;
  if (i & 1) {
    return memory[pair<lint, int>(i, k)] = f(i - 1, k) * pow_10(k) + 1;
  } else {
    return memory[pair<lint, int>(i, k)] = f(i / 2, k) * (pow_10(k * (i / 2)) + 1);
  }
}

mint g(lint i, int k, lint plusi, mint &B) {
  if (i == 0) return 0;
  mint gt;
  if (i & 1) {
    return g(i - 1, k, plusi, B) * pow_10(k) + B * (plusi + i - 1);
  } else {
    return g(i / 2, k, plusi, B) * (pow_10(k * (i / 2)) + 1) + B * (i / 2) * f(i / 2, k);
  }
}

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

  lint l, a, b, m;
  cin >> l >> a >> b >> m;
  vector k;
  k.push_back(0);
  lint x = 1;
  rep1 (i, 18) {
    x *= 10;
    if (x - a < 0) {
      k.push_back(0);
    } else {
      lint t = min((x - 1 - a) / b + 1, l);
      k.push_back(t);
      if (t == l) break;
    }
  }
  mint::set_mod(m);
  mint sum = 0, A = a, B = b;
  rep1 (i, k.size() - 1) {
    lint len = k[i] - k[i - 1];
    if (len <= 0) continue;
    sum = sum * power(pow_10(len), i) + A * f(len, i) + g(len, i, k[i - 1], B);
  }
  cout << sum << endl;
  return 0;
}

結局行列とか整数とかの繰り返し二乗法もやってることはダブリングじゃないのか？
と最初思ったが最終的に、「保持する情報が少ないために簡単に実装できるダブリングの一種」という認識になった。
今回の問題も最初関数のダブリングを計算する際、ビットの最下位が立っているかどうかの再帰を使わずループで回す形で実装しようと考えた。
しかし、ダブリングの計算にインデックスがいるのだが、どう考えてもこの方法だと正しいインデックスを得られない。
インデックスは0から上がっていくのに対し、この二乗法で計算されるインデックスはMAXから下がっていく方法だ。
どこで1加えてどこで2倍して・・・をどうやって保持しようか。
そう考えて解説のコードを見てみると、全員が再帰で実装している。
やはりダブリングは再帰でやるのがセオリーなのだろうか。
このことから、繰り返し二乗法は前述した「保持する情報が少ないために簡単に実装できるダブリングの一種」という結論に至った。

ダブリングの疑問は解決されたところで、実装がとにかくしんどかった。
追っていく変数が多すぎてどこでミスるか分かったものじゃない。
定義域がやたらと大きいことから、保持する情報を増やしてなるべく計算量を落とそうと思ったのだが、それが大きな間違いだった。
①が最初のコード、②が保持する情報を減らそうと頑張ったコードである。
10の自乗の状態を保存しておこうとしたのだが、それくらい計算しても全然問題なかった。
さっき計算したらlog(10^18)すら100に満たないんだな。
ちなみに関数内で値を保存するためのstatic変数を学生時代ぶりに使ったのがちょっとノスタルジック。
それでも色々保存するようにしたが、結局①も②も実行時間は2msで、最初から保持する情報を減らしておけばもうちょっとしんどくなかったかもしれない。
このブログでも何度目かのオーダーの把握は大事だなぁ・・・。
実装している最中、他のダブリング問題が出てきても解ける気がしておらず、完全に苦手問題なんだなと思っていたが、追うべき変数を減らすことを意識したら行けるかもしれない。

以下今回のしんどかったポイント。

しんどかったポイント①
行列演算クラスMatrixの実装
行列式の有理式での計算に謎に力を入れたせいですさまじい時間を取られた。

しんどかったポイント②
常にmodを取ってくれる整数値クラスModIntの実装
C++の仕様にちょっと苦労した。
行列の実装に比べると大したこと無い。

しんどかったポイント③
変数の値を追う
保持している情報と変化するポイントが多いのと、その段階での正しい値の計算の難しさと、常にmodを取っていることから、デバッグで変数の値を追うのが相当しんどかった。
後々のことを考えたら、楽できる(変数・情報を減らせる)ところは、苦労して(オーダーを把握するために計算して)でも楽すべきだった。


今週末はABCがあるみたいですね。
今週こそ参加なのです！

ついにこのブログにもシンタックスハイライトがやってきたぞ！

コード
https://atcoder.jp/contests/abc127/submissions/7097782

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto &&V : v)
#define all(x) (x).begin(), (x).end()
const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
using lint = long long;

using namespace std;

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

  int q;
  cin >> q;
  vector t(q), a(q), b(q);
  rep(i, q) {
    cin >> t[i];
    if (t[i] == 1) cin >> a[i] >> b[i];
  }
  multiset<int, greater> l;
  multiset r;
  int lmax = -INF, rmin = INF;
  lint lsum = 0, rsum = 0, bsum = 0;
  int mid;
  bool mid_ava = false;
  rep(i, q) {
    if (t[i] == 1) {
      if (mid_ava) {
        if (a[i] < mid) {
          r.insert(mid);
          rmin = mid;
          rsum += mid;
          l.insert(a[i]);
          lmax = max(lmax, a[i]);
          lsum += a[i];
        } else {
          l.insert(mid);
          lmax = mid;
          lsum += mid;
          r.insert(a[i]);
          rmin = min(rmin, a[i]);
          rsum += a[i];
        }
      } else {
        if (a[i] < lmax) {
          l.erase(l.begin());
          mid = lmax;
          l.insert(a[i]);
          lmax = *l.begin();
          lsum += a[i] - mid;
        } else if (a[i] > rmin) {
          r.erase(r.begin());
          mid = rmin;
          r.insert(a[i]);
          rmin = *r.begin();
          rsum += a[i] - mid;
        } else {
          mid = a[i];
        }
      }
      mid_ava = !mid_ava;
      bsum += b[i];
    } else {
      cout << (mid_ava ? mid : lmax) << " " << rsum - lsum + bsum << "\n";
    }
  }
  return 0;
}

シンタックスハイライトはやってきたものの入力が面倒くさい。
毎回このクソ面倒なタグ手打ちすんの・・・？
WordPressならテンプレートとかありそうで便利そうだなぁ。
そもそも解説ブログではないので必要ではないかもしれないが、わざわざリンクから飛ぶのも面倒で難しいところ。


今回は時間の見積もりは大事だよっていうお話。
今回はD問題とF問題でTLEをかましてやった。
TLEにはなったもの、WA1回もなしでA～Fまで答えにたどり着けたのはかなりの成長を感じる。

D問題は明らかに早い実装を思いついたのでそれでACになったが、F問題は思いついた後にこれは遅いだろうという間違った考えを挟んでしまった。
「aの中央値を求めてbは定数項にまとめて～」という問題の解き方自体は、クエリを数回適当に手書きしてみると分かった。

1,2回目の実装

最小のx：
ソートされたaの配列から中央値を求める。

最小のf(x)：
ソートされたaの配列の(右から1番目-左から1番目)+(左から2番目ー右から2番目)+...を繰り返す(奇数の場合は中央を含まない)。
(配列のサイズ/2)回繰り返すことで、奇数の場合も中央を含まないように合計できる。

この実装はaが大きくなってくるときついだろうとは思っていたものの、クエリの更新がないとaは増えないし、クエリの更新は処理が軽いし、いける可能性はあるのではという儚い願いは崩れ去る。
最初はvecterに入れて出力クエリの度にソートをしてTLEだったので、おそらく一番遅いであろうソートをなくすためにmultisetに入れてみるもTLE。
だめなのは(配列のサイズ/2)回繰り返すところなんだろうなぁと気づいて悩む。
クエリが2*10^5あるんだから、更新出力クエリが半々だとしても最大でO(10^10)くらいになっちゃうもんなぁ・・・。

たどり着いたのがaの配列を左半分と右半分に分けること。
左半分と右半分は合計値で保管しても良いというのに気付けるかが全てだった。
両端の差+2番目の差+...と考えずに、(a[n]-a[0])+(a[n-1]-a[1])+...と式としてとらえていれば移行してすぐに気付けたかもしれない。
これが上のコードなのだが、更新クエリの処理が明らかに色々やってて遅そう。
こうなるのが分かっていたから一旦諦めてしまった。
ループの中が単純な方が早そうだが、頑張って色々詰め込んだとしてもループなしの方が早いのである。
そりゃそうではあるんだけど、ループ回数とか考えるとなかなか正確な判断が下せない。
実行速度・オーダーに関する勘みたいなのを養っていかないとなぁ。

それでなんやかんや細かい処理頑張ってなんとかAC。
WA食らったのが、「multisetのeraseすると対象の値全てを削除する」ことを知らなかったため。
1つだけ削除するのかなと思って値を入れてeraseしていたので、イテレータで削除するようにするとACできた。
multiset使って正解にたどり着くの初めてやねん！
いつかの問題でmultiset使ってうまく行かずにやめた記憶があるが、うまく行っていればそこで同じミスをして、今回は間違わなかったかもしれない。
ABC127をAから通して初WAなので、間違わなければWAなしでABC127通せたわけでそっちの方が良かったなぁと少し。
それでもAから通して初WAがF問題は実装精度の向上を感じる。
解説を見ても右半分と左半分に分けていたので、思考面も向上していて嬉しい限り。
細かい部分はちょっと理解できなかったけど分けるまで同じでACできてるなら大筋は同じだろう。
BITでも解けるよと書いててどう実装するのか気になる部分ではある。
問題を読んでセグメントツリーとかBITとか使えそうと思わずにはいられなかったが、データをどう処理すれば良いのか全く分からなかった。
「凸性に基づいた値自体に対する三分探索」についてはマジで何言ってんのか分かんねぇ。

今回実行時間が300ms程度と結構かかっており、他の人のを見ると2桁msが結構あってはえーなーBITつかってんのかなーとか思ったわけです。
今回入出力多かったしここらで入出力の速度の違い見てみるかと、今までそこまでシビアなことしてなかったから良いかとテンプレートに入れていなかったこいつらを試してみた。

今日はABCなさそうだしあるとしたら明日かな？
あったら頑張って参加するぞい！

今週末にABCがあるのかどうか分からないが、あれば参加してみようと思う。
やったり休んだりで、結局競プロ歴はのべ2ヶ月もなさそうだが、レーティングに参加してモチベ上げていくぞ！

今年の目標は橙色と今年の最初に書いていたが、思ったより目標高かったんだなぁとちょっと調べて分かってしまった。
昔結構やってた某ゲームのGlicko ratingが2000くらいなので、2000以上の黄色を改めて目標にしようかな。
さすがにレーティングの仕組みは全然違うだろうが、2000あれば大体のレーティングで中級者以上は名乗れるイメージがある。
AtCoderのレーティングの仕組みに関する英語のPDFがあったが、それを読むほどの興味はない。

今までA～D問題まであるABCしかやったことがないので、最近のA～F問題まであるABCをちょっと練習しておこう。

C 白昼夢 / Daydream

コード
https://atcoder.jp/contests/abc049/submissions/6953590


微妙に迷った問題。
ちょっと考えて「これ後ろから調べていけば被らなくないか？」と思ったが、どうも裏道っぽかったからパスしてしまった。
というのも、仮に被るような文字列だった場合に解けないのはちょっとどうなんだろうということで、これは違うだろうと考えたからだ。
解いてから解説を見ると意外にもこれが想定解でびっくり。

その後しばらく考えて思いついたのがdp的な解法。
Sのi番目から始まる文字列で、指定の文字列(dream, dreamer, erase, eraser)が作れるかどうかは、Sのi-1番目以前には関係しないので、i=0から順に調べていこうという感じ。
こういうdpの典型例的な問題あっても良さそうだけどあるのかな？
重複なし優先度付きキューとしてSTLのSetを使ったが、dpでSetなんか使うのかなー違うのかなーとも思ったが一発でACできてほっこり。
計算量を計算しようと思ったけど思ったより難しかった・・・。
重複なしで計算量を多少落としたつもりだが、指定の文字列の文字数が短かったり、文字数のバリエーションが多かったりすると結局ほぼ全探索になる？
そういう場合は後ろから調べると被らない、という部分を活用しないといけないのかな。
そっちの解法も後で解いておこう。

D 連結 / Connectivity

コード
https://atcoder.jp/contests/abc049/submissions/7033954


今回はUnion-Find！やったー！
データ構造を扱う問題を調べながら理解できるとテンションが上がる。
何ならライブラリとして理解しながら実装していく瞬間が一番楽しいかもしれない。

もちろんUnion-Find使うよっていう部分は分からなかったから最初は解説頼り。
公式の解説は想像以上に簡素で、本当にUnion-Find使うよっていう部分しか分からなかった。
実際にUnion-Findを使って実装してみると、その後に工夫がまた1つ必要で、愚直に計算するとO(n^2)でTLEした。
「n<=2*10^5ならそんなに重い処理じゃないだろうしO(n^2)くらいけるのでは？」と思ったが全然そんなことはなかった。
10^8が相当軽い処理でギリギリとのことで、10^6,7程度を目安にするべきらしい、覚えておこう。

その後の工夫を実装してスッキリ解けたのだが、工夫部分説明がなかなかしっくり来るものがなかったから記録しておく。

Union-Findで道路のグループroadと鉄道のグループtrainを作成したとき、i番目の街とj番目の街が道路と鉄道のどちらでも繋がれているかどうかを求めるには、
・i番目の街が属する道路のグループにj番目の街が属しているか
・i番目の街が属する鉄道のグループにj番目の街が属しているか
この論理積を取れば良い。
これはグループ内で街が条件に合っていくか走査していくようなイメージだと思う。
これをi,jで2重ループすることで総数を数えられるが、この考え方に固執すると2重ループを外せず工夫部分をすんなり理解できない。

考え方を変えて、
・i番目の街が属する道路のグループとj番目の街が属する道路のグループが同じかどうか
・i番目の街が属する鉄道のグループとj番目の街が属する鉄道のグループが同じかどうか
の論理積を取ることを考える。
どちらもやっていることは同じだが、考え方は結構変わる。
片方が属するグループ内でもう片方の街を探していくのではなく、それぞれの街が属するグループを求めてから同じかどうか判別するイメージ。
こう考えると、道路と鉄道を分けて論理積で考えずに、(道路のグループ, 鉄道のグループ)のペアで保存しても良いことが分かる。
後は連想配列なりで総数を保存してあげれば1重ループで解けちゃう！

Union-Findの操作的には後者の方が近いが、単純に考えると前者の方が直感的だと思う。
自分は前者の考え方からなかなか抜け出せずに、多くの解説がなかなか理解できなかった。
図説を見て、さらに自分で書いてやっと抜け出せた。
考え方を固定してしまうのは怖い怖い。

C 単調増加

コード
https://atcoder.jp/contests/abc038/submissions/6927104


最初の提出ではいくつかのテストケースでWAをもらった。
なんでだろうと最大値を考えた場合に、10^5と10^4を書き間違えて1～10^4まで合計してもint型でいけるだろ！って思ってしまったせいで少し時間を食った。
本番ではWAはもちろん避けたいところだけど、こういうミスもするだろうなぁと思うと気が重いなぁ。

まぁさくっと解けて良かったのだが、解説を見てみるとどうも少し違う。
確かに計算結果を答えに加えつつ、それとは別にiの増加ごとに答えを+1するのは少し違和感があったが、数式の理解が自分とは違う感じ。

解説では

D プレゼント

コード
BIT
https://atcoder.jp/contests/abc038/submissions/6942401
LIS
https://atcoder.jp/contests/abc038/submissions/6934327


この問題は完全にお手上げだった。
dp使いそうという、ソートしたら計算量減りそう、という予想は合っていたが、添字に持たせる意味を思いつけなかった。
なんとか思いついたのが、添字に入れ子にする箱の(高さ,幅)のpairのvectorを載せて、対象の箱の高さと幅が、vectorの中でソートした場合の高さと幅が同じインデックスになった場合にdpに1追加する！、なんていうのはあまりにも無理そう。
そもそもこれは漸化式(そもそもなってる？)として入れ子にできるかどうかを判別するだけで、dp[vector]になんてしてしまうとそもそも添字が絶対に被らないからただの全列挙である・・・。

BIT

まずは解説にもあるBIT。
解説を見るとそもそも添字に持たせる意味じゃなくてdpに持たせる意味を変えてきた。
i番目までの箱で作れる入れ子の最大数ではなく、i番目を一番外側にした際の入れ個の最大数とは。
i番目まででなく全体の情報を入れてしまうとdpにならなくないか？、と思ったが、なるほどソートすれば実質i-1番目以内の情報のみで更新できるすごい。

これらの情報のみで実装したらきれいにTLE。
なるほどここでついにデータ構造、競技プログラミングらしくなってきたなと結構テンションが上がった。
BITは分かるようで分からないようでな状態でライブラリとしてクラスを作成したが、やはり書いているうちにかなり理解できてくる。
完全な単体の情報を一部しか持っていないため、更新関数・クエリ関数に求められる条件が組み合わせによって異なることはしっかり理解できた。
結局和を保存するBITと最大値を保存するBITを作成し、今回使用したのは最大値を保存するBIT。

ここからはすぐにAC！、と行きたかったがそうはいかず、BITの使いみちの理解に手こずった。
確かに最大値を素早く取り出したいからBITを使ったものの、結局2重ループになりそうだった。
というのも、dpをBITとして実装し、i番目のdpテーブルを更新するために、j番目(0<=j<i)までのdpから最大値を取り出す、という方向性で考えていたからだ。
BITに持たせる情報を、幅ごとの入れ子の最大数にするというのはなかなか理解できなかった。
要するにjループの情報をそのままBITに持たせられている。

確かな理解を持ってACすることができたが、難易度の高さに対する驚きもかなりあった。
ABCでこのレベルが出るのかと少し自信をなくした。
データ構造というものをそもそも使ったことがなかったためなんとも言えないが、このような使い方が一般的なのかどうか分からない。
この使い方の感覚を慣れで養えるなら良いが、そうでないならつらいものがあるなぁ・・・。
dpはかなりバリエーションがあるらしい中で典型的なdpしか知らないし、その上データ構造を使ったことがないときたら仕方がないのかもしれないが。

LIS

次にLIS(最長増加部分列)。
解いたのはLISが先だが文脈的に後に。
解説を見てもいまいちピンと来なかったので、調べてるうちに見つけた解説とは別解。
LISなんて言葉知らなかったし、知っててもこんなのなんのために計算するんだよと思うこと間違いなし。
この問題でLISが使える理由を理解すると、心からなるほどなぁと思えた。
こういう場面において有効に使える、というのが分かったのはかなりの収穫。
解説に乗っていたのは次のBITを使った方法だが、正直それよりもかなり直感的で納得のいく解法だと感じた。



いやー難しかった。
継続してかないとレベル上げられないな。

それと文章見にくいなーと思ったから見出し機能なんてものを見つけて使ってみた。
多少ましになったかな。