95位. 3完. 2356->2357(+1) highest!!
4連続highestはうれしいぞい
C - Bugged
解法
300点問題であることをわすれないように, 30秒ぐらい問題を睨むとDPができそうだとわかる.
部分和DP.
bitsetで常勝.
ソース
#include<bits/stdc++.h> using namespace std; int main() { int N; bitset< 100 * 101 > dp; dp[0] = 1; cin >> N; for(int i = 0; i < N; i++) { int K; cin >> K; dp |= dp << K; } int ret = 0; for(int i = 0; i < 100 * 101; i++) { if(i % 10 != 0 && dp[i]) ret = max(ret, i); } cout << ret << endl; }
D - Widespread
解法
400点問題であることをわすれないように, 5 分くらいかんがえると二分探索であることがわかる.
なんかきれいに解ける.
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; int main() { int64 N, A, B, H[100000]; cin >> N >> A >> B; for(int i = 0; i < N; i++) { cin >> H[i]; } auto check = [&](int v) { int64 sa = A - B; int64 ret = 0; for(int i = 0; i < N; i++) { int64 get = H[i] - v * B; if(get > 0) ret += (get + sa - 1) / sa; } return (ret <= v); }; int low = 0, high = 1 << 30; while(high - low > 0) { int mid = (low + high) / 2; if(check(mid)) high = mid; else low = mid + 1; } cout << low << endl; }
E - Meaningful Mean
解法
なんかぐっと睨むと, 端を固定したいいつものという気持ちになる.
あと累積和をしておきたい気持ちにもなる. の累積和を とする.
右端 を固定する.
いつものように式を書いてみる.
平均が 以上なので
みたいなものを満たす の個数がわかればいい.
式を整理すると なので で, ある値以下の の個数みたいになるので, その値を座標圧縮してBITにのせればよい.
ソース
制約が だと錯覚して 1 RE した.
制約くらい確認しようね.
#include<bits/stdc++.h> using namespace std; typedef long long int64; template< class T > struct BinaryIndexedTree { vector< T > data; BinaryIndexedTree(int sz) { data.assign(++sz, 0); } T sum(int k) { T ret = 0; for(++k; k > 0; k -= k & -k) ret += data[k]; return (ret); } void add(int k, T x) { for(++k; k < data.size(); k += k & -k) data[k] += x; } }; int main() { int64 N, K, A[200000]; cin >> N >> K; for(int i = 0; i < N; i++) cin >> A[i]; int64 sum = 0; vector< int64 > odd; odd.push_back(0); for(int i = 0; i < N; i++) { sum += A[i]; odd.push_back(sum - (i + 1) * K); } sort(begin(odd), end(odd)); odd.erase(unique(begin(odd), end(odd)), end(odd)); sum = 0; int64 ret = 0; BinaryIndexedTree< long long > bit(odd.size() + 2); bit.add(lower_bound(begin(odd), end(odd), 0) - begin(odd), 1); for(int i = 0; i < N; i++) { sum += A[i]; ret += bit.sum(lower_bound(begin(odd), end(odd), sum - (i + 1) * K) - begin(odd)); bit.add(lower_bound(begin(odd), end(odd), sum - (i + 1) * K) - begin(odd), 1); } cout << ret << endl; }
F - Mirrored
解法
差が を考える.
が 桁の数だとすると, みたいに表せる.
を考えると, .
これらの差をとると, みたいな感じなる.
ここらへんからうーんってなってた.
両端から を決めていくことができるので, 候補を結構しぼることができる.
考えるのが面倒なので, 作れる値の範囲を考えながら適当に嘘DP(嘘はしてないが)するととおる(?)
ソース
終了4分後くらいに通ってえぇってなった.
それもまたうし.
#include<bits/stdc++.h> using namespace std; #define int long long typedef long long int64; const int64 INF = 1LL << 60; int64 fact[19]; signed main() { fact[0] = 1; for(int i = 1; i < 19; i++) fact[i] = fact[i - 1] * 10; int D; cin >> D; int64 ret = 0; for(int length = 2; length <= 18; length++) { unordered_map< int64, int64 > dp; dp[0] = 1; for(int keta = 0; keta < length / 2; keta++) { map< int64, int64 > cat; unordered_map< int64, int64 > nextdp; int revketa = length - keta - 1; int64 aa = 0, bb = 0; for(int k = keta + 1; k < length / 2; k++) { int64 latte = INF, malta = -INF; for(int p = 0; p < 10; p++) { for(int q = 0; q < 10; q++) { latte = min(latte, (p - q) * fact[k] + (q - p) * fact[length - k]); malta = max(malta, (p - q) * fact[k] + (q - p) * fact[length - k]); } } aa += latte; bb += malta; } for(int p = 0; p < 10; p++) { if(revketa + 1 == length && p == 0) continue; for(int q = 0; q < 10; q++) { ++cat[(p - q) * fact[keta] + (q - p) * fact[revketa]]; } } for(auto p : cat) { for(auto q : dp) { int64 sum = p.first + q.first; if(sum + aa > D || sum + bb < D) continue; nextdp[p.first + q.first] += q.second * p.second; } } swap(dp, nextdp); } if(length % 2 == 1) ret += dp[D] * 10; else ret += dp[D]; } cout << ret << endl; }