AtCoder Beginner Contest 379E問題

ABC379E

考えた事

素直に考えれば，累積和を使えば解ける． 今回は，その方法だと桁が大きくなるのが問題で，足し算にO(1)でなくO(N)程度かかる．
何を全探索するか考えると，10 の指数 \(k \in N\) になる． 繰り上がりを無視すれば，答えは \(N\) 桁の自然数で書ける． 答えの \(k \in N\) 桁目の値は 累積和で求まる．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  string s; cin >> s;

  reverse(all(s));

  vll v(n);

  ll sum = 0;

  drep(k,n){

    sum += (n-k)*(s[k]-'0');

    v[k] = sum;

  }

   

  string ans;

  ll up = 0; // 繰り上がり

  rep(i,v.size()){

    ll x = v[i];

    ans.push_back(x % 10 + '0');

    up = x / 10;

    if(!up) continue;

    if(i+1 < v.size()) v[i+1] += up;

    else v.emplace_back(up);

  }

  reverse(all(ans));

  cout << ans << endl;

  return 0;

}

AtCoder Regular Contest 177A問題

ARC177A

考えた事

通貨 \(P\) が，\(P_{i} \leq_{div} P_{i+1}\) \(\forall i \in (P.size()-1)\) であるから， 高い通貨から貪欲に使えばよい．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  vll m = { 1, 5, 10 , 50, 100, 500};

  vll b(6); cinv(b);

 

  ll n;

  cin >> n;

  vll x(n); rep(i,n) { cin >> x[i]; }

  rep(i,n){

    drep(j,6) if(x[i] > 0){

      ll c = min(b[j], x[i]/m[j]);

      x[i] -= c * m[j];

      b[j] -= c;

      assert(x[i] >= 0);

    }

    if(x[i] > 0) {

      cout << "No" << endl;

      return 0;

    }

  }

  cout << "Yes" << endl;

  return 0;

}

AtCoder Beginner Contest 110D問題

ABC110D

解法

\(N,M\) が固定で，\(M\) の素因数 \(p\) を重複込みで \(N\) 個の箱に入れる． より詳しくは，\(M = \Pi_{p: prime \\ e_{p} > 0}\ p^{e_{p}}\) としたとき， \(e_{p}\) 個の \(p\) を \(N\)個の箱に入れる場合の数を， 素因数 \(p\) の種類ごとに独立に求める． つまり重複組み合わせをすればよい．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

vector<pll> pf(ll m){

  vector<pll> v;

  srep(p,2,m+1){

    ll e = 0;

    while(m % p == 0){

      m /= p;

      e++;

    }

    if(e) v.emplace_back(p,e);

  }

  return v;

}

int main() {

  ll n,m;

  cin >> n >> m;

  vector<pll> v = pf(m);

  // Comb<mint, (ll)1e9 + 5> co; // MLE

  mint ans = 1;

  for(auto [_p,e]: v){

    // mint tmp = co.nCr(e+n-1,n-1);

    mint tmp = 1;

    rep(i,n-1) tmp *= mint(e+n-1-i);

    rep1(i,n-1) tmp /= mint(i);

   

    ans *= tmp;

  }

  cout << ans.val() << endl;

  return 0;

}

AtCoder Regular Contest 098E問題

ARC098E

解法

min を固定して考える．\(i \in N\) に対して \(y := A_{i}\) が min になる場合を考える． このとき，max となる \(x\) を求める． \(x-y\)を最小化したいので，\(x\) を最小化したい．
\(y\) を min にする場合，\(a \in A\) のうち \(a < y\) のものは使えなくなる． よって，そのような \(a\) で \(A\) を分割することができ，分割した区間で独立に考えることが出来る． 分割した区間の集まりを \([I_{\lambda}]_{\lambda}\) とおく．
\(| I_{\lambda} | \geq K\) のときしか操作できない． また，\(I_{\lambda}\) からは小さいほうから貪欲にとればよい． これらをすべての \(\lambda\) に対して行い集めて来た元全体の小さいほうから \(Q\) 番目の元が答え．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n,k,q;

  cin >> n >> k >> q;

  vll a(n); rep(i,n) { cin >> a[i]; }

  const ll inf = (ll)1e9 + 5;

  ll ans = inf;

  rep(i,n){

    ll y = a[i]; // min, fix

    // devide

    using Q = min_priority_queue<ll>;

    vector<Q> pqs;

    pqs.push_back(Q());

    rep(j,n) {

      if(a[j] < y){

        pqs.push_back(Q());

      }else{

        pqs.back().push(a[j]);

      }

    }

    // 取り除く候補すべてを求めてソートする

    vector<ll> remove; // 取り除く候補

    for(Q pq: pqs){

      while(pq.size() >= k){

        remove.push_back(pq.top());

        pq.pop();

      }

    }

    if(remove.size() < q) continue;

    sort(all(remove));

    // update ans

    ll x = remove[q-1];

    assert(x >= y);

    chmin(ans, x-y);

  }

  assert(ans < inf);

  cout << ans << endl;

  return 0;

}

AtCoder Regular Contest 100D問題

ARC100D

解法

4 つの区間に分けるので，仕切りは 3つで，それを \(i,j,k\ (i < j < k)\) とする． 3つの仕切りのうち，真ん中 \(j\) にあるものを固定すると，残りの 2つが対称になりそうで楽そう． \(j\) を固定したときのベストな \(i,k\) を \(i_{j}, k_{j}\) とおく．
\(j\) により左右 2つに分解したとき，\(i\) の位置は

• \(P = sum_{[0,i)} A \)と\(Q = sum_{[i,j)} A\) が同じくらいになるとよい．
• \(A\) の元はすべて \(0\)以上なので，\(i_{j}\) は単調増加．

後者から，\(i_{j}\) は尺取り法で求められる． 前者に注意しながら尺取り法を実装する． \(P\) と \(Q\) が同じ位になるには，\(P\) と \(Q\) の大小関係が入れ替わる高々 2つが \(i_{j}\) の候補となる．
\(k_{j}\) についても同様． 各 \(j\) に対して，\(i_{j}\) と \(k_{j}\) が高々 2通りずつあるで，高々 2x2通り試せば良い．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  vll a(n); rep(i,n) { cin >> a[i]; }

  vll sum(n+1); rep(i,n) sum[i+1] = sum[i] + a[i];

  using I = ll; // index or partition of vector

  // a,b,i: partitions of n

  // i in [a,b]

  auto f = [&](I a, I b, I& i) -> vector<pll> {

    vector<pll> ret;

    while(i <= b && sum[i] - sum[a] < sum[b] - sum[i]){

      i++;

    }

    i--;

    srep(j,i,i+2){

      if(in(j, a+1, b)) {

        ll ma = max(sum[j]-sum[a], sum[b] - sum[j]);

        ll mi = min(sum[j]-sum[a], sum[b] - sum[j]);

        ret.emplace_back(ma, mi);

      }

    }

    return ret;

  };

 

  const ll inf = 2e14 + 100;

  ll ans = inf;

  ll l = 0, r = 0;

  rep(i,n+1){

    chmax(r,i); chmin(r,n);

    chmin(l,i); chmax(l,0LL);

    for(auto [ma_l, mi_l]: f(0,i,l)){

      for(auto [ma_r, mi_r]: f(i,n,r)){

        ll ma = max(ma_l, ma_r);

        ll mi = min(mi_l, mi_r);

        chmin(ans, ma - mi);

      }

    }

     

  }

  cout << ans << endl;

  return 0;

}

AtCoder Grand Contest 026C問題

\(\def \dcup {\dot{\cup}}\)

AGC026C

解法

まず，制約から半分全列挙(直積分解)なら間に合う． そこで，前半と後半に分解すると，確かに前半と後半で独立に選べるので直積に分解できるので， 半分全列挙が適用できる． 以下，前半 \(N\)文字と 後半 \(N\)文字に分解する．
次に問題文を扱いやすく言い換える．

• 文字列は左から読むことに統一するため，後半の文字列を reverse しておく．
• 青と赤は対称な条件なので，後半で青に塗る場所を赤， 赤で塗る場所を青と置き換える． (青で塗った文字列は使わない)

以下，この塗り方で考える．
前半と後半は対称の条件になる． 前半を全探索して，後半を高速に求めることを考える． 一致する個数を数えればよく，それは map で前処理しておけば良い． $$ Ans = \dcup_{p \in 2^{N}} Y_{p}. $$ ここで，\(p\) は前半の塗り方全体を動いており， \(Y_{p}\) は後半を \(p\)で塗った時に，赤色部分が前半の赤色部分と一致するもの全体とする．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  string s; cin >> s; // len 2n

  reverse(s.begin()+n, s.end());

  map<pair<string, string>,ll> mp; // remark: 選ぶ indices <msk> in 2^n を区別するので，set では WA.

  // pre calc: suffix of s

  rep(msk, 1LL<<n){

    string a, b; // a: red, b: blue

    rep(i,n){

      if(msk >> i & 1) a.push_back(s[n+i]);

      else b.push_back(s[n+i]);

    }

    mp[{a,b}]++;

  }

  // main calc : prefix of s

  ll ans = 0;

  rep(msk, 1LL<<n){

    string a, b; // a: red, b: blue

    rep(i,n){

      if(msk >> i & 1) a.push_back(s[i]);

      else b.push_back(s[i]);

    }

    ans += mp[{a,b}];

  }

  cout << ans << endl;

  return 0;

}

AtCoder Grand Contest 025B問題

\(\def \dcup {\dot{\cup}}\)

AGC025B

解法

\(G\)で塗って \(A+B\)点となるのを， \(R\)と\(B\)で塗って \(A+B\)点と言い換える． この言い換えにより， 使える色が \(R,G,B\) から \(R,B\)の 2色に減り，さらに塗るマスを重複して良いことになる．
\(R\)を塗るマスの個数を \(x\), \(B\)を塗るマスの個数を \(y\) とする． $$ Ans = \dcup_{x \in [0,N] \\ y \in [0,N] \\ Ax + By = K} {}_{N}C_{x} \times {}_{N}C_{y}. $$ これは \(x\)を動かせば \(y\) は一意なので \(O(N)\).

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  ll a,b,k; cin >> a >> b >> k;

  Comb<mint, (ll)3e5+5> co;

  mint ans;

  rep(x,n+1) {

    ll t = k - a*x;

    if(t < 0 || t % b) continue;

    ll y = t / b; // i.e. if(a*x + b*y == k)

    ans += co.nCr(n,x) * co.nCr(n,y);

  }

  cout << ans.val() << endl;

  return 0;

}