競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 312F問題

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \order #1{\lvert {#1} \rvert}\)

 

問題概要

\(N\) 頂点の tree \(G\) が与えられる． \begin{align} U &:= \set{(i,j,k) \in V(G)}{ i,j,k \text{は相異なる} }, \\ L &:= \set{(i,j,k) \in U}{i,j,k \text{は一直線状に並ぶ}} \end{align} とおく． ここで，\(i,j,k\) が一直線上に並ぶとは， 次のいずれかが成り立つことである．

  • \(k \in V(mini\text{-}path_{i,j})\),
  • \(i \in V(mini\text{-}path_{j,k})\),
  • \(j \in V(mini\text{-}path_{k,i})\).
解法

答えは \[ \begin{matrix} ans &=& \order{U} - \order{L} \\ &=& {}_{N} C_{3} - \sum_{i,j \in V(G) \\ i \neq j} (dis_{i,j} - 1)\\ &=& {}_{N} C_{3} - \sum_{e \in E(G)}\order{ \set{ (i,j) \in V(G)^{2} }{ i \neq j \text{かつ} e \in E(mini\text{-}path_{i,j})} } + {}_{N}C_{2} \end{matrix} \] となる．

頂点の組 \((i,j)\) を動かす代わりに， 辺 \(e = (i,j)\) を動かすことで，全探索する対象を減らしている．

Root を固定して DFS で求まる． \(i,j\) のうち，root から見て深い方を \(i\) とすると， \begin{align} &\order{ \set{ (i,j) \in V(G)^{2} }{ i \neq j \text{かつ} e \in E(mini\text{-}path_{i,j})} } \\ =& \order{V(G_{i})} \cdot( \order{ V(G) } - \order{V(G_{i})}). \end{align} ここで，\(V(G_{i})\) は \(i\) を root とする \(G\) における subtree.

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

int main() {
  ll n;
  cin >> n;
  vvll to(n);
  rep(i,n-1){
    ll a,b; cin >> a >> b;
    --a, --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  vll sz(n);
  ll ans = nCr(n,3LL) + nCr(n,2LL);
  auto dfs = [&](auto dfs, ll cu, ll pa = -1) -> void {
    sz[cu] = 1;
    for(auto ne: to[cu]) if(ne != pa){
      dfs(dfs, ne, cu);
      sz[cu] += sz[ne];
    }

    if(pa != -1){
      ans -= sz[cu] * (n - sz[cu]);
    }
  };
  dfs(dfs, 0);
 
  cout << ans << endl;

  return 0;
}

AtCoder Beginner Contest 314F問題

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)

ABC314F

問題概要

有向 tree \(T\) を構成する．

  • \(N := \{0, 1, \cdots, N-1\}\)
  • \(|V(T)| = 2N-1\)
  • The set \(L := \set{\{i\}}{ i \in N}\) is the set of leafs of T.
  • For any vertex \(x\) of \(V\) is a subset of \(L\).
  • There is a unique \(r \in V(T)\) such that \(r = N\). We denote that \(r\) is a root of \(T\).
  • For any distinct vertices \(x\) and \(y\) with same parents such that \(x \cap y\) is the empty set.
解法

プレイヤー \(i \in N\) が，どの vertex \(in V(T)\) に属すのかを \(gp : N \rightarrow V(T)\) で表す．

\(V(T)\) に対して，代表元を決めながら合併する． \(p, q \in N\) の試合の後に新しくできる vertex を \(v \in V(T)\) とおく．
試合の後にするべき操作は，

  • 頂点の更新:
    • \(gp(p)\) と \(gp(q)\) のマージ．
    • 代表元の更新: \(gp(leader(v)) = v\)
  • 辺の更新:
    • \(v \rightarrow gp(p)\), \(v \rightarrow gp(q)\) を作る．

するべき操作が決まれば，用意すべきものが決まる．
用意するものは，

  • 各 \(w in V(T)\) に対する代表元
  • 各 \(i \in N\) に対して，今 \(i\) が属している \(V(T)\) の元であって， 一番新しく作成されたもの．

これらは，Uinon-Find で実現できる．

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

int main() {
  ll n;
  cin >> n;

  UnionFind<ll> uf(n);
  vll gp(n); rep(i,n) gp[i] = i;
  vll sz(2*n-1,1);

  vvll to(2*n-1);
  rep(i,n-1){
    ll p,q; cin >> p >> q;
    --p, --q;
    p = uf[p];
    q = uf[q];

    // new vertex v
    ll v = i + n;
   
    // new edges
    // v -> gp[p],
    // v -> gp[q]
    to[v] = vll({gp[p], gp[q]});

    // vertex
    sz[v] = uf.size(p) + uf.size(q); // rem : not sz[uf.size(p)]
    uf.merge(p,q);
    gp[p] = v; // p = leader of v
  }

  ll root = 2*n-1 -1;
  vector<mint> dp(2*n-1);
  auto dfs = [&](auto dfs, ll cu) -> void {
    for(ll ne : to[cu]) {
      dp[ne] = dp[cu] + mint(sz[ne])/mint(sz[cu]);
      dfs(dfs, ne);
    }
  };
 
  dfs(dfs, root);
  rep(i,n) cout << dp[i].val() << " ";

  return 0;
}

AtCoder Beginner Contest 321F問題

 

ABC321F

問題概要

Muliset に対する部分和問題に，追加と削除クエリを与えたもの． 俗に戻すDPと呼ばれる．

解法

(0) まず，multiset が固定されている場合を考える． これは普通の部分和DP. とくに，配列を 1次元にした inplace DP で考えると， 今回の問題に応用するときに楽．
(1) 次に，multiset に1つ元 \(x\) を追加または削除することを考える． 簡単な追加の方を考える． (0)の考えを用いると，

\(dfor \ i \in [x,k]\)
   \(dp_{i} += dp_{i-x}\)

という処理をしている．
削除の方も同様に，

\(for \ i \in [x,k]\)    \(dp_{i} -= dp_{i-x}\)

と出来る．for の順番が反転することと，\(+\) と \(-\) も反転している．

注意

多項式を使った数え上げを考えると，操作が可換であることが用意に分かる． \(t\) に関する多項式とする． \(x\) を mutiset に追加することは，多項式に \(1+t^{x}\) を掛けることに対応して， \(x\) を mutiset から削除することは，多項式に \(1+t^{x}\) で割ることに対応する． 積と割り算は共に可換．
また，Multiset から元を選んで部分和を作るとき，一つの元に対して 1回しか使えないというルールなので \(dfor \ i \in [x,k]\)    \(dp_{i} += dp_{i-x}\) としている． もし，1つの元を何度でも使えるというルールなら， \(for\) になる．

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

int main() {
  ll q,k; cin >> q >> k;

  vector<mint> dp(k+1);
  dp[0] = 1;
  rep(qi,q){
    char c; ll x; cin >> c >> x;
    if(c == '+'){
      for(int i = k; i >= x; i--){
        dp[i] += dp[i-x];
      }
    }else{
      for(int i = x; i <= k; i++){
        dp[i] -= dp[i-x];
      }
    }
   
    cout << dp[k].val() << endl;
  }
 
  return 0;
}

AtCoder Beginner Contest 324F問題

ABC324F

解法

平均の最大化なので，binary search が典型． \(I \subset E\) に対して， $$ f_{I} := \frac{\sum_{i \in I}b_{i}}{\sum_{i \in I}c_{i}} $$ とおく． \(x \in \mathbb{R}\) を固定したとき，\(f_{I} \geq x\) となる \(I\) が存在するか， という判定問題を解けばよい．\(i \in I\) に対して \(w_{i} := b_{i} - c_{i}x\) とおく．
与えられたグラフが DAG なので，このグラフ上で DP が可能． \(i \in V\) に対して，

\(dp_{i} := \) \(0 \rightarrow i\) のパスとなる \(I \subset E\) の取り方のうち， \(\sum_{i \in I} w_{i}\) の最大値

とおく．これは DPで求まる．

注意

Double 型の binary search なので，while を使うよりは， 回数を決めて rep の方が安全．

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

int main() {
  ll n,m;
  cin >> n >> m;
  vector<vector<Edge>> to(n);
  rep(i,m){
    ll s,t,b,c; cin >> s >> t >> b >> c;
    --s, --t;
    to[s].emplace_back((Edge){t,b,c});
  }

  double ok = 0, ng = INFL;
  rep(_,150){
    double mid = (ok + ng)/2.0;

    vector<double> dp(n, -INFL);
    dp[0] = 0;
    rep(i,n){
      for(auto ed: to[i]){
        chmax(dp[ed.to], dp[i] + ed.b - ed.c*mid);
      }
    }

    if(dp[n-1] >= 0) ok = mid;
    else ng = mid;
  }
  printf("%.10lf", ok);

  return 0;
}

AtCoder Beginner Contest 325F問題

ABC325F

解法

まず，素直に bool 型 dp を考える．

\( dp_{i,j,k} := \) 区間 \(i\) まで， センサー 1 を \(j\) 個， センサー 2 を \(k\) 個 で可能か
\(\in Bool\)

とする． 次に，bool 型 dp の定義域のいくつかを値域に移すことを考える． このとき，\(i,j\) は対象な条件なのでどちらでも良い．

値域に移すものは，何か良い性質を持っていないと，高速化は難しい． 定義域は全探索するので，綺麗な性質である必要が無い．

今回は，\(i,j\) を固定した前提で \(k\) は単調性があるので，値域に持っていくと高速化できる．

\(dp_{i,j} := \) 区間 \(i\) まで， センサー 1 を \(j\) 個 のときの \(k\) の min の合計
\(\in \mathbb{Z}\)

とする． 区間\(i\) について，\(j\) が決まれば，\(k\) の min が求まる． また，\(i\) に関しては，単調性などの綺麗な性質が見当たらないので， 値域に持って行っても高速化は難しい．

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

int main() {
  ll n;
  cin >> n;
  vll d(n); rep(i,n) { cin >> d[i]; }
  vll l(2), c(2), k(2);
  rep(i,2) cin >> l[i] >> c[i] >> k[i];

  vll dp(k[0]+1, INFL);
  dp[0] = 0;
  rep(i,n){
    vll old(k[0]+1, INFL);
    swap(old,dp);

    rep(j,k[0]+1){
      // rep(add,k[0]+1)if(j+add <= k[0]){
      rep(add, k[0]+1-j){
        ll x = ceil(d[i] - add*l[0], l[1]);
        chmax(x, 0LL);
        chmin(dp[j+add], old[j] + x);
      }
    }
  }

  ll ans = INFL;
  rep(j,k[0]+1){
    if(dp[j] <= k[1]){
      chmin(ans, j*c[0] + dp[j]*c[1]);
    }
  }
  if(ans == INFL) ans = -1;
  cout << ans << endl;

  return 0;
}

AtCoder Beginner Contest 326F問題

ABC326F

解法

移動自体は，\(i \in N\) 回目の操作について \(i\) mod 2 で座標軸ごとに独立に分けることができる． \(M := N/2\) なら，\(O(2^{M}\) は間に合う．

実装

簡単のため，\(N \equiv 0\) mod 4 となる様に \(A\) の末尾に \(0\) を追加する．

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

vll solve(vll x,ll val ){
  ll n2 = x.size();
  ll n = n2/2;
  vll xl(x.begin(), x.begin()+n);
  vll xr(x.begin()+n, x.end());
  x.clear();

  vll res;
  unordered_map<ll,vll> mp;
  rep(ti,2){
    rep(msk,1LL<<n){
      vll s;
      ll tot = 0;
      rep(i,n){
        if(msk>>i&1) s.push_back(+1), tot += xl[i];
        else s.push_back(-1), tot -= xl[i];
      }
     
      if(ti==0) mp[tot] = s;
      else {
        auto it = mp.find(val - tot);
        if(it != mp.end()){
          vll *c = &*1;
          return (*c);
        }
      }
    }

    swap(xl, xr);
  }

  return vll();
}

int main() {
  ll n, x, y;
  cin >> n >> x >> y;
  vll a(n); rep(i,n) { cin >> a[i]; }
 
  ll added = 0;
  while(n%4) added++, n++, a.push_back(0);

  vll vx,vy;
  rep(i,n) {
    if(i%2) vx.push_back(a[i]);
    else vy.push_back(a[i]);
  }

  vll sx = solve(vx, x);
  vll sy = solve(vy, y);

  if(sx.size()*sy.size() == 0){
    cout << "No" << endl;
    return 0;
  }
 
  ll pre = 1;
  string ans;
  rep(i,n){
    ll q = pre;
    ll cu;
    if(i%2){
      cu = sx[i/2];
      q *= cu;
      pre = cu;
      q *= -1;
    }
    else {
      cu = sy[i/2];
      q *= cu;
      pre = cu;
    }

    if(q == 1) ans.push_back('L');
    else ans.push_back('R');
  }

  rep(i,added) ans.pop_back();
  cout << "Yes" << endl;
  cout << ans << endl;
 

  return 0;
}

*1:*it).second);

          (*c).insert((*c).end(), all(s

AtCoder Beginner Contest 327F問題

ABC327F

解法

リンゴを固定して，それを覆う籠の位置を動かす． 籠の左上や右上を，籠の位置と一対一対応させる．
縦軸を時刻，横軸を座標として 2次元で考える． リンゴ1個に対して，籠の範囲を考えると， 長方形領域が対応する． つまり，長方形領域(2次元)のグリッドに +1をして， 一番大きい数字が答え．

実装

愚直に行うと， 時刻: 2e5, 座標: 4e5 となり，MLT かつ TLE. そこで，座標だけ全探索して，時刻を高速に処理する．
座標を固定すると，時刻に対しては， 区間(1次元)に +1 をすることになる． これは，lazy_segtree で実装できる．

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

struct Event{
  ll l, r, val;
  Event(){}
  Event(ll l, ll r, ll val) : l(l), r(r), val(val){}

};

ll op(ll a, ll b) {return max(a,b);}
ll e() {return 0;}
ll mapping (ll f, ll x) {return x += f; }
ll composition(ll f, ll g) {return f+g;}
ll id() { return 0; }

int main() {
  ll n, d, w;
  cin >> n >> d >> w;
  const ll MT = (ll)4e5 + 5;
  vector<vector<Event>> events(MT);
  rep(i,n){
    ll t,x; cin >> t >> x;
    events[t].emplace_back(x,x+w,+1);
    events[t+d].emplace_back(x,x+w,-1);
  }

  lazy_segtree<ll,op,e,ll,mapping,composition,id> seg(MT);
  ll ans = 0;
  rep(t, MT){
    for(auto ev: events[t]){
      seg.apply(ev.l, ev.r, ev.val);
    }
    chmax(ans, seg.all_prod());
  }
  cout << ans << endl;

  return 0;
}