unrated(というかA 問題が TLE で落ちて 完だったのでそうじゃないと大変なことになってた
A. Efim and Strange Grade
問題概要
長さが の小数が与えられる. 小数は, 小数点の後に少なくとも 桁を含む正の数で, 小数の末尾が でないことが保証されている.
小数点以下の任意位置で四捨五入できる操作を 回まで行えるとき, 得られる最大値を求めよ. 解が整数になるとき小数点は出力しない.
解法
問題文を読んで, それをそのまま実装する問題.
小数点以下で上の桁から見ていったとき, 最初に出現する 以上の位置で四捨五入するのが省エネ.
四捨五入するとその前の桁が繰り上がって, また四捨五入できるときがあるので の間その操作を繰り返す.
コーナーケースに注意する. 計算量は明らかに .
ソース
桁を丸めるところで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
問題概要
長さ の整数列 がある. 以下の 個のクエリを実行する.
- から 番目の要素へ 一様に を加える.
- を計算する. は 番目のフィボナッチ数である.
タイプ のそれぞれのクエリについて, その値を で割った余りで出力せよ.
解法
(僕の頭が悪いのでとても丁寧に書きます...)
フィボナッチ数列の漸化式は以下の行列で表すことができる.
よって,
行列の累乗は繰り返し二乗法を使って効率的に計算できるので, 番目のフィボナッチ数は で求めることができる(詳しくは蟻本.
ここで, を計算したいとき, 上の式に当てはめると
である.
分配法則が成立するので,
としてもよい.
また に を加算すると であり, これは
である.
これを拡張して, 全体に を加算することを考えると,
よって区間に一様に足す操作は, 区間に を掛ける操作である.
区間に を掛ける操作, 区間の和を求める操作が高速にできればいいので, 一般的な Starry Sky Tree を使えば良いことがわかる. 計算量は .
ソース
これは勉強になったなぁ. さすがに 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)); } } }