ei1333の日記

ぺこい

AtCoder Regular Contest 075

95位. 3完. 2356->2357(+1) highest!!

4連続highestはうれしいぞい

C - Bugged

arc075.contest.atcoder.jp

解法

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

arc075.contest.atcoder.jp

解法

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

arc075.contest.atcoder.jp

解法

なんかぐっと睨むと, 端を固定したいいつものという気持ちになる.

あと累積和をしておきたい気持ちにもなる.  {[1, idx]} の累積和を  {x_{idx}} とする.

右端  {i} を固定する.

いつものように式を書いてみる.

平均が  {K} 以上なので

 {x_i - x_k \le K(i-k)} みたいなものを満たす  {k} の個数がわかればいい.

式を整理すると  {x_i - x_k \le Ki - Kk} なので  {x_i - Ki \le x_k - Kk} で, ある値以下の  {k} の個数みたいになるので, その値を座標圧縮してBITにのせればよい.

ソース

制約が  {100000} だと錯覚して 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

arc075.contest.atcoder.jp

解法

差が  {rev(N)-N} を考える.

 {N} {k} 桁の数だとすると,  {a_{k-1} 10^{k-1} + a_{k-2} 10^{k-2} + \dots + a_{0} 10^{0}} みたいに表せる.

 {rev(N)} を考えると,  {a_{0} 10^{k-1} + a_{1} 10^{k-2} + \dots + a_{k-1} 10^{0}}.

これらの差をとると,  {10^{k-1}(a_{k-1}-a_{0}) + 10^{k-2}(a_{k-2}-a_{1}) + \dots + 10^{0}(a_{0}-a_{k - 1})} みたいな感じなる.

ここらへんからうーんってなってた.

両端から  {a_{k-i-1}, a_{i}} を決めていくことができるので, 候補を結構しぼることができる.

考えるのが面倒なので, 作れる値の範囲を考えながら適当に嘘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;
 
}