競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 391F問題

F

ABC391F

解法

priority queue を用いて解く． 実際に候補を列挙していけばよい． 重複した \(\ (i,j,k)\ \) の組を調べないために，used 変数を用意しても良いが，別の解決策がある． Path が一意に定まれば良いので，

  • \(j\) の遷移は \(i = 0\) のときのみ，
  • \(k\) の遷移は \(i = 0\) かつ \(j = 0\) のときのみ，

とすれば良い．

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

int main() {
  ll n,K;
  cin >> n >> K;
  vll a(n); rep(i,n) { cin >> a[i]; }
  vll b(n); rep(i,n) { cin >> b[i]; }
  vll c(n); rep(i,n) { cin >> c[i]; }
  sort(rall(a));
  sort(rall(b));
  sort(rall(c));

  using T = tuple<ll,ll,ll,ll>;
  // set<tuple<ll,ll,ll>> used;
  priority_queue<T> pq;
  auto push = [&](ll i, ll j, ll k) -> void {
    // if(pq.size() >= K) return; // WA
    if(!in(i,n)) return;
    if(!in(j,n)) return;
    if(!in(k,n)) return;
    // if(in({i,j,k}, used)) return;

    ll val = a[i]*b[j] + b[j]*c[k] + c[k]*a[i];
    pq.push({val,i,j,k});
    // used.insert({i,j,k});
  };

  push(0, 0, 0);

  ll ans;
  rep(_ki, K){
    auto [val,i,j,k] = pq.top(); pq.pop();
    ans = val;

    push(i+1, j, k);
    if(i==0) push(i, j+1, k);
    if(i==0 && j==0) push(i, j, k+1);
  }
  cout << ans << endl;

  return 0;
}

AtCoder Beginner Contest 357E問題

ABC357E

問題概要

Functional graph において，サイクル部分と tree 部分を求める．

解法

Cycle 部分と tree 部分を分けて処理する方がミスが少ない． Tree 部分は，元のグラフの反転を考えれば dp 出来る．

Cycle 部分は，cycle の長さを求める．これは DFS で，vis の値を 0~2 にして区別する事で可能． また，一つ cycle を見つけるだけなら，\(V\)回程度移動を繰り返せば cycle 内部の点に移動出来るので， そこから遷移を繰り返せば良い．

注意

Functional graph \(G\) の反転は，functional graph とは限らない． 実際，\(G\) においては複数の頂点から一つの頂点への辺が有り得る．Tree と cycle が交わる部分にあたる．

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

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

  vll dp(n);
 
  // cycle
  {
    vll vis(n);
    vll path;
    auto dfs = [&](auto dfs, ll cu) -> bool {
      if(vis[cu] == 2) return false;
      if(vis[cu] == 1){ // cycle
        vll cycle;
        cycle.emplace_back(cu);
        while(path.back() != cu){
          cycle.emplace_back(path.back());
          path.pop_back();
        }
        ll cycle_length = cycle.size();
        for(auto i: cycle){
          dp[i] = cycle_length;
        }

        return true;
      }
      vis[cu] = 1;
      path.push_back(cu);

      for(auto ne: to[cu]){
        if(dfs(dfs, ne)) {
          vis[cu] = 2;
          return true;
        }
      }

      vis[cu] = 2;
      return false;
    };

    rep(i,n) if(vis[i] != 2){
      path = vll();
      dfs(dfs, i);
    }

  }

  // remain
  {
    auto dfs2 = [&](auto dfs2, ll cu) -> void {
      for(auto ne: to_op[cu]) if(dp[ne] == 0){
        dp[ne] = dp[cu] + 1;
        dfs2(dfs2, ne);
      }
    };

    rep(i,n) if(dp[i] != 0){
      dfs2(dfs2, i);
    }

  }
 
  ll ans = 0;
  rep(i,n) ans += dp[i];
  cout << ans << endl;


  return 0;
}

AtCoder Beginner Contest 369E問題

ABC369E

解法

簡単のため，\(K\) が 1のときを考える． 辺 \(e = (a,b)\) を経由して \(s\) から \(t\) に行く場合， \(s \rightarrow a \xrightarrow{e} b \rightarrow t\) というルートを通れば良い．つまり，cost[s][a], cost[b][t] が分かれば十分で，これは 全点間距離を求めておけば十分．つまり W-F で求めれば良い． \(s \rightarrow b \xrightarrow{e} a \rightarrow t\) の場合も同様．

\(K \leq 5\) でも同様に，経由する辺すべての順と向きを全探索すれば十分．

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

int main() {
  ll n,m;
  cin >> n >> m;
  vector<tuple<ll,ll,ll>> edges(m);
  const ll inf = 1e18;
  vvll cost(n,vll(n,inf));
  rep(i,m){
    ll a,b,c; cin >> a >> b >> c;
    --a, --b;
    chmin(cost[a][b], c);
    chmin(cost[b][a], c);
    edges[i] = {a,b,c};
  }
  rep(i,n) cost[i][i] = 0;

  rep(k,n) rep(i,n) rep(j,n) chmin(cost[i][j], cost[i][k] + cost[k][j]);

  ll q; cin >> q;
  auto solve = [&](void) -> void {
    ll k; cin >> k;
    vll e(k); cinv(e);
    rep(i,k) e[i]--;

    vll perm(k); rep(i,k) perm[i] = i;
    ll ans = inf;
    do{
      rep(msk, 1LL << k){
        ll tmp_ans = 0;
        ll v = 0;
       
        rep(i,k){
          auto [a,b,c] = edges[e[perm[i]]];
          if(msk >> i & 1) swap(a,b);
          tmp_ans += cost[v][a];
          tmp_ans += c;
          v = b;

        }
        tmp_ans += cost[v][n-1];
       
        chmin(ans, tmp_ans);
      }
    }while(next_permutation(all(perm)));

    cout << ans << "\n";
  };
 
  rep(qi,q){
    solve();
  }

  return 0;
}

AtCoder Beginner Contest 401E問題

 

問題概要

ABC401E

解法

最初に判定問題を考える． \(1, \cdots , k\) 以外の頂点を全て消したとき，接続されていることが必要十分． これは， \(k\) について昇順に頂点を追加していき，小さい番号に向かう辺だけ追加すれば， 頂点 \(1, \cdots, k\) からなる fullsubgraph が作れる．

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

int main() {
  ll n,m;
  cin >> n >> m;
  UnionFind<ll> uf(n);
  vvll to(n);
  rep(i,m){
    ll a,b; cin >> a >> b;
    --a, --b;
    to[a].emplace_back(b);
    to[b].emplace_back(a);
  }


  vector<bool> connected(n); ll cc_vx_cnt = 0;
  rep(cu,n){
    for(auto ne: to[cu]){
      if(cu > ne) {
        uf.merge(cu,ne); // 判定
      }
      if(cu < ne){
        if(connected[ne]) continue;
        connected[ne] = true;
        cc_vx_cnt++;
      }
    }
    if(connected[cu]) cc_vx_cnt--;

    ll ans;
    if(uf.size(cu) != cu + 1){ // 判定
      ans = -1;
    }else{
      ans = cc_vx_cnt;
    }
    cout << ans << "\n";
  }


  return 0;
}

蟻本 4-4 slide-min

 

問題概要

slide-min.

解法

deque の中は，次を満たす．

  • assending order で index がはいっている．
  • a_{deque} も assending order.


右端を全探索する．\(a\) は綺麗な形とは限らないので全探索する．
front の pop を行わなければ，先頭からの min と一致．front の pop は，長さを \(k\) にするために行う．

実装
注意

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

int main() {
  ll n, k;
  cin >> n >> k;
  vll a(n); rep(i,n) { cin >> a[i]; }

  vector<ll> ans;
  deque<ll> deq;
  rep(i,k-1) deq.push_back(i);
  srep(i,k-1,n){
    // add
    while(a[deq.back()] > a[i]) deq.pop_back();
    deq.push_back(i);
   
    // del
    while(deq.front() <= i-k){
      deq.pop_front();
    }

    ans.push_back(a[deq.front()]);
  }
 
  coutv(ans);

  return 0;
}

蟻本 4-4 LRH

 

問題概要

Largest Rectangle in a Histgram

解法

stack の中には，descending order で入っている． \(h_{stack}\) も descending order．

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

int main() {
  ll n;
  cin >> n;
  vll h(n); cinv(h);

  vll l(n), r(n);
  rep(_flip,2){
    vector<ll> st; // stack
    st.push_back(-1);

    rep(i,n){
      while(st.back() >= 0 && h[st.back()] >= h[i]){
        st.pop_back();
      }
      l[i] = i - st.back();

      st.push_back(i);
    }

    reverse(all(h));
    swap(l,r);
  }
  reverse(all(r));

  ll ans = 0;
  rep(i,n){
    chmax(ans, h[i] * (r[i] + l[i] - 1));
  }
  cout << ans << endl;

  coutv(l);
  coutv(r);

  return 0;
}

AtCoder Beginner Contest 414E問題

 

解法

\(\sum_{b \in n} \lfloor n/b \rfloor\) を計算できれば十分． \(b \geq \sqrt{N}\) のとき \(\lfloor n/b \rfloor \leq \sqrt{n}\) より高々 \(\sqrt{n}\) 通り， \(b \leq \sqrt{N}\) のとき \(\lfloor n/b\) は高々 \(\sqrt{n}\) 通りであるから， 合計で高々 \(2 \sqrt{n}\) 通り．
また，\(\rfloor n/b \lfloor =: k\) とおく．\(b\) の範囲は， \(k \leq n/b < k+1\) を変形して \(\lfloor n/(k+1) \rfloor + 1 \leq b < \lfloor n/k \rfloor\) となる．

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

int main() {
  ll n; cin >> n;
  // mint ans = nC2(n+1); // rem : 桁あふれ
  mint ans = mint(n)*mint(n+1)/mint(2);

  for(ll b = 1; b <= n; ){
    ll k = n/b;
    ll nb = n/k + 1;
    ans -= mint(nb - b) * mint(k);
   
    b = nb;
  }
  cout << ans.val() << endl;

  return 0;
}