ei1333の日記

ぺこい

Codeforces Round #373 (Div. 1)

unrated(というかA 問題が TLE で落ちて  {0} 完だったのでそうじゃないと大変なことになってた

A. Efim and Strange Grade

問題概要

長さが  {n(1 \le n \le 200\ 000)} の小数が与えられる. 小数は, 小数点の後に少なくとも  {1} 桁を含む正の数で, 小数の末尾が  {'0'} でないことが保証されている.

小数点以下の任意位置で四捨五入できる操作を  {t(1 \le t \le 10^9)} 回まで行えるとき, 得られる最大値を求めよ. 解が整数になるとき小数点は出力しない.

解法

問題文を読んで, それをそのまま実装する問題.

小数点以下で上の桁から見ていったとき, 最初に出現する  {'5'} 以上の位置で四捨五入するのが省エネ.

四捨五入するとその前の桁が繰り上がって, また四捨五入できるときがあるので  {t \gt 0} の間その操作を繰り返す.

コーナーケースに注意する. 計算量は明らかに  {\mathcal{O}(n)}.

ソース

桁を丸めるところでsubstrとかやってたので, それはTLEだよね.

#include<bits/stdc++.h>

using namespace std;

void inc(string& s)
{
  int idx = s.size() - 1;
  while(idx >= 0 && s[idx] == '9') s[idx--] = '0';
  if(idx == -1) s = "1" + s;
  else s[idx]++;
}

int main()
{
  int N, T;
  string K;

  cin >> N >> T;
  cin >> K;

  int ptr = 0;
  while(ptr < K.size() && K[ptr] != '.') ++ptr;
  string L = K.substr(0, ptr);
  string R = "0" + K.substr(ptr + 1);
  int delta = 1;
  for(int i = 0; 0 <= i && i < R.size() && T > 0; i += delta) {
    if(R[i] >= '5') {
      while(i < R.size()) R.pop_back();
      --T;
      inc(R);
      delta = -1;
    }
  }
  if(R.front() == '1') inc(L);
  if(R.size() == 1) cout << L << endl;
  else cout << L << "." << R.substr(1) << endl;
}

C. Sasha and Array

問題概要

長さ  {n(1 \le n \le 100\ 000)} の整数列  {a_i(1 \le a_i \le 10^9)} がある. 以下の  {m(1 \le m \le 100\ 000)} 個のクエリを実行する.

  •  {1\ l\ r\ x :}  {l} から  {r} 番目の要素へ 一様に  {x(1 \le x \le 10^9)} を加える.
  •  {2\ l\ r :}  {\displaystyle \sum_{ i = l }^{ r } f(a_i)} を計算する.  {f(x)} {x} 番目のフィボナッチ数である.

タイプ  {2} のそれぞれのクエリについて, その値を  {10^9 + 7} で割った余りで出力せよ.

解法

(僕の頭が悪いのでとても丁寧に書きます...)

フィボナッチ数列の漸化式は以下の行列で表すことができる.

 {\begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1\ 1 \\ 1\ 0 \end{pmatrix} \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix} }

よって,

 {\begin{pmatrix} F_{n} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 0\ 1 \\ 1\ 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix} = A^n \begin{pmatrix} 0 \\ 1 \end{pmatrix} }

行列の累乗は繰り返し二乗法を使って効率的に計算できるので,  {n} 番目のフィボナッチ数は  {\mathcal{O}(\log n)} で求めることができる(詳しくは蟻本.

ここで,  {F_a + F_b + ... + F_z} を計算したいとき, 上の式に当てはめると

 {A^a \begin{pmatrix} 0 \\ 1 \end{pmatrix} + A^b \begin{pmatrix} 0 \\ 1 \end{pmatrix} + ... + A^z \begin{pmatrix} 0 \\ 1 \end{pmatrix}} である.

分配法則が成立するので,

 {(A^a + A^b + ... + A^z) \begin{pmatrix} 0 \\ 1 \end{pmatrix}} としてもよい.

また  {F_a} {x} を加算すると  {F_{a+x}} であり, これは

 {\begin{pmatrix} F_{a+x} \\ F_{a+x+1} \end{pmatrix} =  A^{a+x} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = A^a A^x \begin{pmatrix} 0 \\ 1 \end{pmatrix}} である.

これを拡張して,  {F_a, F_b, ..., F_z} 全体に  {x} を加算することを考えると,

 {A^a A^x \begin{pmatrix} 0 \\ 1 \end{pmatrix} + A^b A^x \begin{pmatrix} 0 \\ 1 \end{pmatrix} + ... +  A^z A^x \begin{pmatrix} 0 \\ 1 \end{pmatrix} = A^x(A^a + A^b + ... + A^z) \begin{pmatrix} 0 \\ 1 \end{pmatrix}}

よって区間に一様に足す操作は, 区間 {A^x} を掛ける操作である.

区間 {A^x} を掛ける操作, 区間の和を求める操作が高速にできればいいので, 一般的な Starry Sky Tree を使えば良いことがわかる. 計算量は  {\mathcal{O}((N + M) \log N)}.

ソース

これは勉強になったなぁ. さすがに Matrix のライブラリくらいは作っておいたほうがよさそうだと思った.

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

struct Matrix
{
  int a[2][2];

  Matrix operator+(const Matrix& kj)
  {
    Matrix ret;
    for(int i = 0; i < 2; i++) {
      for(int j = 0; j < 2; j++) {
        ret.a[i][j] = a[i][j] + kj.a[i][j];
        ret.a[i][j] %= mod;
      }
    }
    return (ret);
  }

  Matrix operator*(const Matrix& kj)
  {
    Matrix ret = Matrix::Zero();
    for(int i = 0; i < 2; i++) {
      for(int j = 0; j < 2; j++) {
        for(int k = 0; k < 2; k++) {
          ret.a[i][j] = (ret.a[i][j] + 1LL * a[i][k] * kj.a[k][j]) % mod;
        }
      }
    }
    return (ret);
  }

  Matrix operator^(int n)
  {
    Matrix ret = Matrix::I();
    Matrix x = *this;
    while(n > 0) {
      if(n & 1) (ret = ret * x);
      x = x * x;
      n >>= 1;
    }
    return (ret);
  }

  static Matrix Zero()
  {
    Matrix ret;
    memset(ret.a, 0, sizeof(ret.a));
    return (ret);
  }

  static Matrix I()
  {
    Matrix ret;
    memset(ret.a, 0, sizeof(ret.a));
    for(int i = 0; i < 2; i++) ret.a[i][i] = 1;
    return (ret);
  }
};

struct SegmentTree
{
  vector< Matrix > seg, add;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, Matrix::Zero());
    add.assign(2 * sz - 1, Matrix::I());
  }

  void update(int a, int b, Matrix& x, int k, int l, int r)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      add[k] = add[k] * x;
      return;
    }
    update(a, b, x, 2 * k + 1, l, (l + r) >> 1);
    update(a, b, x, 2 * k + 2, (l + r) >> 1, r);
    seg[k] = seg[2 * k + 1] * add[2 * k + 1] + seg[2 * k + 2] * add[2 * k + 2];
  }

  Matrix query(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (Matrix::Zero());
    if(a <= l && r <= b) return (seg[k] * add[k]);
    Matrix L = query(a, b, 2 * k + 1, l, (l + r) >> 1);
    Matrix R = query(a, b, 2 * k + 2, (l + r) >> 1, r);
    return (add[k] * (L + R));
  }

  void update(int a, int b, Matrix x)
  {
    update(a, b, x, 0, 0, sz);
  }

  int query(int a, int b)
  {
    return (query(a, b, 0, 0, sz).a[0][1]);
  }

  void set(int k, Matrix x)
  {
    seg[k + sz - 1] = x;
  }

  void build()
  {
    for(int i = sz - 2; i >= 0; i--) {
      seg[i] = seg[2 * i + 1] + seg[2 * i + 2];
    }
  }
};

int main()
{
  Matrix tt;
  tt.a[0][0] = 0;
  tt.a[1][0] = tt.a[0][1] = tt.a[1][1] = 1;

  int N, M;

  scanf("%d %d", &N, &M);

  SegmentTree tree(N);

  for(int i = 0; i < N; i++) {
    int A;
    scanf("%d", &A);
    tree.set(i, tt ^ A);
  }
  tree.build();

  for(int i = 0; i < M; i++) {
    int type, l, r, x;
    scanf("%d", &type);
    if(type == 1) {
      scanf("%d %d %d", &l, &r, &x);
      tree.update(--l, r, tt ^ x);
    } else {
      scanf("%d %d", &l, &r);
      printf("%d\n", tree.query(--l, r));
    }
  }
}