競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 447D問題

ABC447D

解法

3つの物を扱うので，真ん中に注目する．そうすれば，残りの2つが対称的になりやすいため． 'B' を固定した場合，使うべき 'A' と 'C' は先頭から貪欲に決めればよい．

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

int main() {
  string s; cin >> s;

  deque<ll> pos_a;
  deque<ll> pos_c;
  rep(i,s.length()){
    if(s[i] == 'A'){pos_a.push_back(i);}
    else if(s[i] == 'B'){}
    else if(s[i] == 'C'){pos_c.push_back(i);}
  }

  ll ans = 0;
  rep(i,s.length())if(s[i] == 'B'){
    if(pos_a.size() && pos_a.front() < i){
      while(pos_c.size() && pos_c.front() < i){
        pos_c.pop_front();
      }

      if(pos_c.size()){
        assert(pos_c.front() > i);
        ans++;
        pos_a.pop_front();
        pos_c.pop_front();
      }
    }
  }
  cout << ans << endl;

  return 0;
}

AtCoder Beginner Contest 447C問題

ABC447C

解法

まずは判定問題を解く．簡単にするという意味もあるが，判定問題が解ければ，判定した後は 条件を満たすと仮定できるという利点もある．
判定問題は，SとTの'A' を全て削除して，文字列として一致していることが必要十分．
次に，判定問題で true の場合に最小値を求める．先頭から貪欲に見る． Sの先頭とTの先頭が一致していれば消せば良いし，そうでなければ 'A'を追加すれば良い． 先頭の扱いは deque を用いたが，reverse して stack or vector でも良い．

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

int main() {
  string s,t; cin >> s >> t;

  auto solve = [&](void) -> ll {
    {// 判定
      string ss;
      string tt;
      for(auto c: s) if(c != 'A') ss.push_back(c);
      for(auto c: t) if(c != 'A') tt.push_back(c);
      if(ss != tt) return -1;
    }

    { // min
      deque<char> ss, tt;
      for(auto c: s) ss.push_back(c);
      for(auto c: t) tt.push_back(c);

      ll ans = 0;
      while(ss.size() || tt.size()){
        if(ss.front() == tt.front()) {
        }else{
          if(ss.size() == 0 || (ss.front() != 'A')) ss.push_front('A');
          else if(tt.size() == 0 || (tt.front() != 'A')) tt.push_front('A');
          else assert(false);
          ans++;
        }
        ss.pop_front();
        tt.pop_front();
      }
      return ans;
    }
  };
 
  cout << solve() << endl;


  return 0;
}

AtCoder Beginner Contest 427E問題

ABC427E

解法

\(H,W \leq 12\) と小さいことに注目． ごみ全体の座標を持ちながら BFS をしても間に合う． ごみ全体の配置として，常に長方形領域に収まるということから， 状態数は \*1{

      dis[trash] = d;
      que.push(trash);
    }
  };

  // init
  ll th, tw;
  {
    T trash;
    rep(h, max_h) rep(w, max_w){
      if(s[h][w] == 'T') { th = h, tw = w; }
      else if(s[h][w] == '#'){
        trash.push_back({h,w});
      }
    }
    que.push(trash);
  }

  // bfs
  while(que.size()){
    T cu = que.front(); que.pop();
    if(cu.size() == 0){
      cout << dis[cu] << endl;
      return 0;
    }

    vll dh = {-1, 0, 1, 0};
    vll dw = {0, -1, 0, 1};
    rep(i,4){
      T ne; // 一斉にシフトするので，ne に入っている pairs の order は崩れない．
      bool ok = true;
      for(auto [h,w]: cu){
        ll nh = h + dh[i];
        ll nw = w + dw[i];
        if(nh == th && nw == tw) { ok = false; break; }

        if(in(nh, max_h) && in(nw, max_w)) {
          ne.push_back({nh, nw});
        }
      }

      if(ok){
        push(dis[cu] + 1, ne);
      }
    }
  }

  cout << -1 << endl;
  return 0;
}

*1:{}_{13}C_{2})^2\) 以下， 遷移は \(12^2\) 以下で計算できる． また，遷移で 4方向を調べるため，定数倍が 4程度かかるが間に合う．

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

int main() {
  ll max_h, max_w; cin >> max_h >> max_w;
  vector<string> s(max_h); cinv(s);

  using T = vector<pll>; // trashes
  queue<T> que;
  map<T,ll> dis;

  auto push = [&](ll d, T trash) -> void {
    if(dis.find(trash) == dis.end(

AtCoder Beginner Contest 428E問題

ABC428E

解法

木の直径を求めるアルゴリズム(ダブルスイープ)で OK.

使っている記号，マクロ等 "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);
  }

  vector<pll> ans(n);
  auto dfs = [&](auto dfs,ll src, ll cu, ll pa = -1, ll dep = 0) -> pll {
    chmax(ans[cu], pll(dep, src));
   
    pll res = pll(dep, cu);
    for(auto ne: to[cu]) if(ne != pa){
      chmax(res, dfs(dfs, src, ne, cu, dep + 1));
    }

    return res;
  };

  ll a = dfs(dfs, 0, 0).second;
  ll b = dfs(dfs, a, a).second;
  dfs(dfs, b, b);
 
  rep(i,n){
    cout << ans[i].second + 1 << "\n";
  }


  return 0;
}

AtCoder Beginner Contest 429E問題

ABC429E

解法

多始点BFS. イメージとしては，始点とpath に色を付けて区別しながら BFS.

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

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

  using T = tuple<ll,ll,ll>; // <dist, vtx, source vtx>
  queue<T> que;
  vector<vector<pll>> dist(n); // <dist, source vtx>

  auto push = [&](ll d, ll v, ll sv) -> void {
    if(dist[v].size() >= 2) return;
    for(auto p: dist[v]) if(p.second == sv) return;
   
    que.push({d, v, sv});
    dist[v].push_back({d, sv});
  };
 
  rep(v,n) if(s[v] == 'S') push(0, v, v);
  while(que.size()){
    auto [d, v, sv] = que.front(); que.pop();

    for(auto nv: to[v]){
      push(d+1, nv, sv);
    }
  }

  rep(v,n) if(s[v] == 'D'){
    assert(dist[v].size() == 2);
    ll ans = dist[v][0].first + dist[v][1].first;
    cout << ans << '\n';
  }

  return 0;
}

AtCoder Beginner Contest 434E問題

ABC434E

解法

各ウサギについて，左右2通りが選べる． ウサギの座標を \(x\)として，左右の \(x-r, x+r\) の2つに辺を張ったグラフを考える． 左右を選ぶことは，辺の向きを選ぶことに対応する，もしくは辺の両端の一方に色をつけるという事に対応する． 頂点に色を付けたと考えて，以下話を進める． 色を付けた頂点の種類数の最大値を求める問題に帰着出来た．
連結成分毎に独立して解ける．連結成分の頂点数を \(order\), 辺の数を \(size\) とおく．

  • 連結成分が木の場合: \(order - 1\) 個の頂点に色を付けるのが最大となる．
  • 木でない場合: \(order\) 個の頂点に色を付けるのが最大となる．

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

int main() {
  ll n;
  cin >> n;
  map<ll,ll> used;
  map<ll,ll> id;
  vector<pll> es(n);
  rep(i,n){
    ll x, r; cin >> x >> r;

    for(auto sign: vll{1, -1}){
      if(used.find(x + sign*r) == used.end()){
        id[x + sign*r] = used.size();    
        used[x + sign*r];
      }
    }

    es[i] = {x+r, x-r};
  }


  ll vs = used.size();
  vvll to(vs);
  for(auto [a,b]: es){
    to[id[a]].emplace_back(id[b]);
    to[id[b]].emplace_back(id[a]);
  }

  vector<bool> vis(vs);
  ll vertices = 0;
  ll edges = 0;
  auto dfs = [&](auto dfs, ll cu) -> void {
    if(vis[cu]) return;
    vis[cu] = true;
    vertices++;

    for(auto ne: to[cu]){
      edges++;
      dfs(dfs, ne);
    }
  };
 
  ll ans = 0;
  rep(i, vs) {
    vertices = 0;
    edges = 0;
    dfs(dfs, i);
    assert(edges % 2 == 0);
    edges /= 2;

    if(edges < vertices) {
      assert(edges == vertices - 1);
      ans += vertices - 1;
    }else{
      ans += vertices;
    }
  }
  cout << ans << endl;


  return 0;
}

AtCoder Beginner Contest 444D問題

ABC444D

解法

今の桁数を保持しながら，筆算の要領で計算すればよい． 桁数を保持しておくことで，今の桁にいくつ \(1\) を足せばよいか確定する．

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

int main() {
  ll n;
  cin >> n;
  deque<ll> a(n); rep(i,n) { cin >> a[i]; }
  sort(all(a));

  vll ans;
  ll i = 1;
  ll kuri = 0; // kuriagari
  while(true){
    while(a.size() && a.front() < i) a.pop_front();

    ll x = kuri % 10;
    x += a.size();
    ans.push_back(x % 10);
   
    kuri /= 10;
    kuri += x / 10;
    i++;

    if(kuri == 0 && a.size() == 0) break;
  }
  reverse(all(ans));

  rep(i, ans.size()) {
    if(i==0 && ans[i] == 0) continue;
    cout << ans[i];
  }
  cout << endl;


  return 0;
}