"競技プログラミング問題"カテゴリーの記事一覧

- 2025/07/08
[PR]
×
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
- CM

2019/09/10

ABC014 D 閉路

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(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(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst) : src(src), dst(dst) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector;
using Graph = vector;

void edges_to_graph(Graph &graph, const Edges &edges, const int vertices, const bool directed = true) {
  graph.resize(vertices);
  for (const auto &e : edges) {
    graph[e.src].push_back(e);
    if (!directed) graph[e.dst].emplace_back(Edge(e.dst, e.src, e.weight));
  }
}

template 
class SparseTable {
  vector<vector> st;
  vector lookup;
  vector   vec;

  public:
  SparseTable(void) {}
  SparseTable(const vector &original_vecter) { init(original_vecter); }
  void init(const vector &original_vecter) {
    vec = original_vecter;
    int lgsize = 0, vsize = vec.size();
    while ((1 << lgsize) <= vsize) ++lgsize;
    st.assign((1 << lgsize), vector(lgsize));
    for (int i = 0; i < vsize; ++i) st[i][0] = i;
    for (int j = 1; j < lgsize; ++j) {
      for (int i = 0; i + (1 << j) <= (1 << lgsize); ++i) {
        int l = st[i][j - 1], r = st[i + (1 << (j - 1))][j - 1];
        st[i][j] = vec[l] <= vec[r] ? l : r;
      }
    }
    lookup.assign(vsize + 1, 0);
    for (int i = 2; i <= vsize; ++i) lookup[i] = lookup[i >> 1] + 1;
  }
  T query(int l, int r) {
    ++r;
    int lgsize = lookup[r - l];
    return min(vec[st[l][lgsize]], vec[st[r - (1 << lgsize)][lgsize]]);
  }
  int query_index(int l, int r) {
    ++r;
    int lgsize = lookup[r - l];
    T   lv = vec[st[l][lgsize]], rv = vec[st[r - (1 << lgsize)][lgsize]];
    if (lv < rv) return st[l][lgsize];
    else if (lv > rv) return st[r - (1 << lgsize)][lgsize];
    else return min(st[l][lgsize], st[r - (1 << lgsize)][lgsize]);
  }
};

class EulerTour {
  int num = 0;
  void et_dfs(const Graph &graph, const int v, const int p, const int dep) {
    tour.push_back(v);
    in[v] = num++;
    depth_tour.push_back(dep);
    depth[v] = dep;
    for (const auto &e : graph[v]) {
      if (e.dst == p) continue;
      et_dfs(graph, e.dst, v, dep + 1);
      tour.push_back(v);
      depth_tour.push_back(dep);
      ++num;
    }
    out[v] = num - 1;
  }

  public:
  vector tour, depth_tour, in, out, depth;
  EulerTour(void) {}
  EulerTour(const Graph &graph, const int v) { init(graph, v); }
  void init(const Graph &graph, const int v) {
    tour.clear();
    depth_tour.clear();
    in.assign(graph.size(), 0);
    out.assign(graph.size(), 0);
    depth.assign(graph.size(), 0);
    et_dfs(graph, v, -1, 0);
  }
};

class LowestCommonAncestor {
  class PM1RangeMinimumQuery {
    int block_size, block_num;
    vector vec, block_bit;
    vector<vector<vector>> lookup;
    SparseTable<pair<int, int>> st;

    public:
    PM1RangeMinimumQuery(void) {}
    void init(const vector &original_vecter) {
      vec = original_vecter;
      int vsize = vec.size();
      block_size = 0;
      while ((1 << block_size) < vsize) ++block_size;
      block_size = max(1, (block_size >> 1));
      while (vsize % block_size) {
        vec.push_back(vec.back() + 1);
        ++vsize;
      }
      block_num = vsize / block_size;
      vector<pair<int, int>> block_min(block_num, {INT_MAX, INT_MAX});
      for (int i = 0; i < vsize; ++i) block_min[i / block_size] = min(block_min[i / block_size], {vec[i], i});
      st.init(block_min);
      block_bit.assign(block_num, 0);
      for (int i = 0; i < block_num; ++i) {
        int left = block_size * i;
        for (int j = 0; j < block_size - 1; ++j) {
          if (vec[left + j] < vec[left + j + 1]) block_bit[i] |= (1 << j);
        }
      }
      int bit_all = 1 << (block_size - 1);
      lookup.assign(bit_all, vector<vector>(block_size, vector(block_size)));
      for (int b = 0; b < bit_all; ++b) {
        for (int i = 0; i < block_size; ++i) {
          int mini = 0, now = 0;
          for (int j = i + 1; j < block_size; ++j) {
            b&(1 << (j - 1)) ? ++now : --now;
            if (mini > now) {
              mini = now;
              lookup[b][i][j] = j - i;
            } else {
              lookup[b][i][j] = lookup[b][i][j - 1];
            }
          }
        }
      }
    }
    int query_index(int l, int r) {
      int lb = l / block_size, rb = r / block_size;
      int lbpos = l % block_size, rbpos = r % block_size;
      if (lb == rb) return l + lookup[block_bit[lb]][lbpos][rbpos];
      int lbmini = l, rbmini = r;
      if (lbpos != 0) {
        lbmini = l + lookup[block_bit[lb]][lbpos][block_size - 1];
        ++lb;
      }
      if (rbpos != block_size - 1) {
        rbmini = r - rbpos + lookup[block_bit[rb]][0][rbpos];
        --rb;
      }
      int mini = vec[lbmini] < vec[rbmini] ? lbmini : rbmini;
      if (lb <= rb) {
        pair<int, int> stpair = st.query(lb, rb);
        if (stpair.first < vec[mini]) mini = stpair.second;
      }
      return mini;
    }
  };
  PM1RangeMinimumQuery rmq;

  public:
  EulerTour et;
  LowestCommonAncestor(void) {}
  LowestCommonAncestor(const Graph &graph, const int v) { init(graph, v); }
  void init(const Graph &graph, const int v) {
    et.init(graph, v);
    rmq.init(et.depth_tour);
  }
  int query(const int a, const int b) {
    int l = et.in[a], r = et.in[b];
    if (l > r) swap(l, r);
    int idx = rmq.query_index(l, r);
    return et.tour[idx];
  }
};

Edges edges;
Graph graph;
int main(void) {
  int n;
  cin >> n;
  edges.resize(n - 1);
  rep (i, n - 1) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    edges[i] = {x, y};
  }
  int q;
  cin >> q;
  vector<pair<int, int>> ab(q);
  rep (i, q) cin >> ab[i].first >> ab[i].second;
  edges_to_graph(graph, edges, n, false);
  LowestCommonAncestor lca(graph, 0);
  vector ans(q);
  rep (i, q) {
    int a = ab[i].first - 1, b = ab[i].second - 1;
    int v = lca.query(a, b);
    ans[i] = lca.et.depth[a] + lca.et.depth[b] - 2 * lca.et.depth[v] + 1;
  }
  rep (i, q) cout << ans[i] << "\n";
  return 0;
}

LCAを解こうとして確認できそうな問題を探したらこれが良さそうだった。
バグりまくってすごく時間かかった。
実装力が+2くらいされた。

いわゆるEuler Tree + ±1RMQの形。
記号だからかなんなのか、±1RMQを検索しようとしてもほとんど引っかからない。
他人のコードを見てなんとか理解した。
頑張って実装した結果確かに速いが、定数倍重いなぁという印象。
RMQ→LCAはもっと重そうだから普通にセグメントツリーとかで良いかなぁ。
LCAに帰着しない形でSparse Table使ってO構築(n)クエリO(1)で解くアルゴリズムもあるみたいだが、理解に頭を使うことに疲れた・・・。
また今度余裕ができたらそっちも試してみよう。

競技プログラミング問題
0CM

2019/09/06

ABC133 E Virus Tree 2

問題

ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP()(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(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(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector;
using Graph = vector;

Graph edges_to_graph(const Edges &edges, const int vertices_num, const bool directed = true) {
  Graph ret(vertices_num);
  for (const auto &e : edges) {
    ret[e.src].push_back(e);
    if (!directed) ret[e.dst].push_back(Edge(e.dst, e.src, e.weight));
  }
  return ret;
}

template 
class ModInt {
  long long n_;

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

using mint = ModInt;
void dfs(const Graph &g, int v, int p, int k, mint &sum) {
  if (g[v].size() == 1) return;
  rep (i, g[v].size() - 1) {
    sum *= k - 2 - i;
  }
  for (const auto &es : g[v]) {
    if (es.dst == p) continue;
    dfs(g, es.dst, v, k, sum);
  }
}
Graph graph(100001);
Edges edges(100001);
int main(void) {
  int n, k;
  cin >> n >> k;
  // Edges edges(n - 1);
  rep (i, n - 1) {
    cin >> edges[i].src >> edges[i].dst;
    --edges[i].src;
    --edges[i].dst;
  }
  // Graph graph = edges_to_graph(edges, n, false);
  rep (i, n - 1) {
    graph[edges[i].src].push_back(edges[i]);
    graph[edges[i].dst].push_back(Edge(edges[i].dst, edges[i].src, edges[i].weight));
  }
  int start, next;
  rep (i, n) {
    if (graph[i].size() == 1) {
      start = i;
      next  = graph[i][0].dst;
      break;
    }
  }
  mint sum = k;
  if (n > 1) {
    sum *= (k - 1);
    dfs(graph, next, start, k, sum);
  }
  cout << sum << endl;
  return 0;
}

今回の学びはスタック領域は思ったよりも弱いということ・・・。
解き方は分からなかったので解説を見た。
思ったより単純でグラフの苦手意識が抜けてないのかなと思う。
方針だけ見て後は自力で！と思ったんだけど全然ACできない。
最初の3つのテストケースだけまさかのRE。
割り算とかやってないし範囲外アクセスしかないかなぁと悩み続け、範囲外アクセスの原因になりそうなところ(グラフの次数が1の頂点を探す部分)を変えて全部WAにするつもりで提出したら1つだけACで他WA。
おそらく答えが0になる部分なんだけろうけど、やはりここが間違いだった？と思うもどう考えても間違っているはずがない。
グラフが木なら次数が1の頂点が必ずあるはず。

そこから色々探って最終的に、Vectorのメモリ足りてないのでは？と思い立つ。
今までVectorには基本的にプリミティブ型やそのPair等しか入れていなかったが、今回は構造体を入れている。
最近作ったグラフ関連の構造体だ。
上限は10^5なのでもしやということでヒープ領域に取ってみるとREの2つがWAになり、おそらく答えが0になるテストケースがACになった。

残りの2つは、自分の実装が「根とその子は初期値として最初に計算して残りをDFSで計算する」という形だったため、n=1のときに根の子がないのにある体で初期化してしまっていたのが原因だった。

今までも10^5くらいのVectorはスタック領域に取っていたような気はするのだが、今回ついに問題になった。
世間ではグローバル変数はあまり使うべきではないと言われているが、自分もそれを学生時代に感じたため、基本的には全てローカル変数として宣言している。
学生時代には基礎だけで事足りており、その後プログラミングすることがなかったので、グローバル変数に対する考え方もその頃のままだった。
取れるメモリの上限に引っかかる問題を解決する方法はいくつかあるようだが、グローバル変数も手段の1つとして入れても良いかもしれない。
競技プログラミングにおいてはグローバル変数一択だとは思うが。

競技プログラミング問題
0CM

- 2019/08/31
ABC131 F Must Be Rectangular!
https://atcoder.jp/contests/abc131/submissions/7223770

#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() using lint = long long; constexpr int INF = 1 << 30; constexpr lint INFL = 1LL << 62; constexpr int MOD = 1e9 + 7; constexpr double EPS = 1e-9; using namespace std; class UnionFind { std::vector parent_; public: UnionFind(int size_num) : parent_(size_num, -1) {} int find(int x) { if (parent_[x] < 0) return x; return parent_[x] = find(parent_[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (parent_[x] > parent_[y]) std::swap(x, y); parent_[x] += parent_[y]; parent_[y] = x; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -parent_[find(x)]; } }; int main(void) { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(10); int n; cin >> n; vector x(n), y(n); rep (i, n) cin >> x[i] >> y[i]; UnionFind uf(100001); unordered_map<int, int> firstx; rep (i, n) { if (firstx.find(y[i]) == firstx.end()) { firstx[y[i]] = x[i]; } uf.unite(firstx[y[i]], x[i]); } unordered_set checkedy; lint cnt = 0; rep (i, n) { if (checkedy.find(y[i]) == checkedy.end()) { cnt += uf.size(x[i]) - 1; checkedy.insert(y[i]); } else { --cnt; } } cout << cnt << endl; return 0; }

ABCの最終問題は3回に1回くらいの割合でほぼ自力で解けるイメージなのだが、最近は難しい問題が続いていたのと、行列とかセグメントツリーとかの実装に時間を費やしたおかげで、自力で解けた！という感覚が久しぶり。
1回しか使ったことないのにUnionFind使えそうだなって気づけたのは成長感じる。
前回はインデックスを保存していたので、値に対してもUnionFindを使えると気づくのに少し手間取ったが、気づけば方向性の決定はすぐだった。

今回は実は完全に自力ではなく、WAしてからテストケースをチラ見してACした。
int型じゃ答えが入り切らなかった・・・。
ここ2,3日だけでこのミス3回くらいした気がする、マジで気をつけよう。

自力で解けた基本的には書くことがないのだが、他の解説と本質は同じ(だと思う)だが見かけの考え方が書かれてなくて後でどう考えたんだろうってなりそうなのでメモ。
二部グラフなんて二色で塗れますかしか知らないので思いつくはずもない。

考え方
x軸を主にしてもy軸を主にしても良いが、ここではx軸を主にする。

とりうるy座標の値全てに対して、そのy座標を持つ点のx座標の集合を作成する。
ある点Pと同じy座標に新たに点を追加することを考えた場合、その点Pのx座標[Px]が含まれる全ての集合の、[Px]以外の全てのx座標[Xi]を持つ点[Xi, Py]が追加される。
全てのy軸に対してこの操作を行うと、点Pを点に持つ長方形を全て作成できる。
※ここでは追加したい点に既に点があることは考えない。

すなわち、x座標が与えられたときに、そのx座標が属している集合を全て求められれば良い。
ここで、点を追加する際に、点Pのy座標以外のy座標は考えなくても良いことに気づくので、x座標が含まれる集合はy座標ごとに保持する必要はなく、集合間に重複する要素がある場合は結合しても良いことが分かる。
結合することでO(n*yMAX)からO(n)になって間に合う。

なぜ結合して良いのか、なぜy軸についても同じ操作をしなくて良いのか、感覚的にあやふやになりそうなので僅かに理論的な説明。

まず、なぜy軸についても同じ操作をしなくて良いのかについて。
点を追加しきった最終的な形を見ると、長方形を成している4つの点と、同じx座標かy座標を持つ点が3つ以上無く、2つ以下で独立している点に分けられる。
3つの点から長方形を作るパターンでは、左上・右上・左下・右下のどの点が欠けている場合でも、上記の方法で正しく長方形を作成することができる。
長方形は3つの点からしか作ることができないので、x軸かy軸いずれかを主にして考えるだけで全ての長方形を作成することができる。
2つ以下で独立した場合については、どちらを主にして考えても長方形を作ることができないので、どちらで考えても良い(どちらでも考える必要がない)。
よって、どちらか片方のみについて考えるだけで良い。

次に、なぜ結合して良いのかについて。
点Pを基点に点を追加して長方形を作成するためには、問題文の条件から、
・点Pと同じx座標を持つ点X1& 点Pと同じy座標を持つ点Y1
・点Pと同じx座標を持つ点X2, 点X2と同じy座標を持つ点Y2
・点Pと同じy座標を持つ点X3, 点X3と同じx座標を持つ点Y3
これらのパターンのどれかの点Xと点Yが同時に存在することが必要になる。
「点Pのx座標[Px]が含まれる集合があること」は、同じx座標を持つ点Xがあることを示す。
また、集合は同じy座標を持つ点について考えており、重複する要素がある場合は結合するが、「重複して集合の要素数が増加する=結合前の集合はそれぞれ少なくとも要素が2つ以上存在する」ことが言える。
集合を結合するとy軸の値の情報を無くしてしまうが、重複した要素は別の集合とのy軸の違いの架け橋になってくれる。
重複した点を点A(Ax, Ay)とすると、(点A, 追加された点(Ax, Py), 結合したい集合に含まれる点)を元に新たに長方形を作成できる。
よって、結合しても問題なく長方形を作成することができる。

話は戻って、結合した集合を作成できれば、後は数え上げるだけである。
点Qを基点にして考える場合、点Qのx座標が含まれる集合の要素数-1(自身の分は追加しない)だけカウントを追加する。
全ての点に対してこの操作を行うと、「同じy座標に対して何度も点の追加作業をしてしまう」という問題が発生する。
重複で追加をしなくても、先程は考えなかった、「追加すべき点に既に点があった場合、無駄に点を追加してしまう」という問題がある。
これらの問題を解決するために、以下の操作を行う。
・点を追加したy座標を記録する。
・点Qのy座標がすでに記録されていた場合、点の追加は行わず、自身と重複する点の追加を防ぐためにカウントを-1する。

実装
後で書くかも

頭の中のイメージはほとんど完成してるのに実装に結構時間を取られた。
集合の結合なんてせずに、○○が含まれる集合簡単に列挙できるデータ構造とかコンテナの使い方とか知ってればもっと楽だったんだけどあるのかしら。
どうやって実装するかの部分で悩んだのは結構久々だった。

今日はABC・・・と思ったら明日に延期されたみたいですね。
21:00開始予定だったけど実は18:30時点でもう結構眠いので延期されてよかった。
- 競技プログラミング問題
- 0CM

2019/08/29

ABC129 F Takahashi's Basics in Education and Learning

コード
行列累乗
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があるみたいですね。
今週こそ参加なのです！

競技プログラミング問題
0CM

- 2019/08/24
ABC127 F Absolute Minima
ついにこのブログにもシンタックスハイライトがやってきたぞ！

コード
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つかってんのかなーとか思ったわけです。
今回入出力多かったしここらで入出力の速度の違い見てみるかと、今までそこまでシビアなことしてなかったから良いかとテンプレートに入れていなかったこいつらを試してみた。

cin.tie(0);

ios::sync_with_stdio(false);
同じコードにこれを入れて試してみると342ms→277msと70msほど早くなった。
まぁそこそこ効くんだなぁとテンプレートに入れることにした。
「テンプレートに入れるならコード書くときは1行空けるかな？空けないかな？んーーーー空けよう！」
と1行空けたのを無駄に再度提出したら110msになった。
「凸性に基づいた値自体に対する三分探索」よりも意味が分からない・・・。
1行空けると170ms縮む・・・。

今回記事を書こうと思った最大の理由はこいつ。
実行時間に関する感覚を養わないといけないのは間違いないが、問題自体はそこまで記録しておきたいことはなかった。
だがこれだけは納得できない・・・。

今日はABCなさそうだしあるとしたら明日かな？
あったら頑張って参加するぞい！
- 競技プログラミング問題
- 0CM

"競技プログラミング問題"カテゴリーの記事一覧

考え方

行列累乗

ダブリング

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

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

1,2回目の実装