競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 332F問題

ABC332F

解法

簡単なバージョンで問題を考える． \(i \in N\) 毎に独立に解けるので，\(N=1\) として考える． \(y := A_{0}\) とおく． \(j \in [0,M]\) に対して，

\(y_{j} := \) \([0,j)\) まで終えたときの \(y\) の値の期待値

とする．
遷移を求める． \(x_{j+1}\) は， 確率\(p := \frac{1}{r-l}\) で \(x_{j}\) になり， 確率\*1;

   
    tr.apply(l,r,f);
  }


  rep(i,n){
    cout << tr.get(i).val() << endl;
  }



  return 0;
}

*1:q := 1-p\) で \(y_{j}\) のままである． よって遷移は $$ y_{j+1} = q y_{j} + px_{j} $$ となる．

実装

\(a,b \in \mathbb{Z}\) に対して， 写像 \(f: \mathbb{Z} \rightarrow \mathbb{Z},\ x \mapsto ax + b\) の全体 \(F\) を考える． 作用素 \(F\) とモノイド\((\mathbb{Z},\ +)\) に対して 遅延伝搬segtree を使えばよい．

注意

モノイドの演算は使わないので，別の演算でも代用できるかも．

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

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

  lazy_segtree<S,op,e,F,mapping, composition, id> tr(n);
  rep(i,n){
    tr.set(i, a[i]);
  }

  rep(i,m){
    ll l,r,x; cin >> l >> r >> x;
    --l;

    S p = mint(1)/mint(-l+r);
    S q = mint(1) - p;  
    F f(q, p*mint(x

AtCoder Beginner Contest 015D問題

ABC015D

解法

ナップザック問題の DPと同じで，部分和問題の DP. 状態数が少ない様に DP の定義域と値域を選ぶと， 空間計算量と時間計算量が小さくできる．

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


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


  const ll c = n * 100 + 5;
  vvll dp(c+1, vll(k+1, INFL)); // WA: init 1000*n + 5
  dp[0][0] = 0;
  rep(i,n) {
    drep(ki,k) drep(x,c+1){
      if(x + b[i] <= c) chmin(dp[x + b[i]][ki+1], dp[x][ki] + a[i]);
    }
  }

  ll ans = 0;
  drep(x,c+1) rep(ki,k+1){
    if(dp[x][ki] <= w){
      chmax(ans, x);
    }
  }

  cout << ans << endl;

  return 0;
}

AtCoder Beginner Contest 019D問題

ABC019D

解法

木の直径を求めるアルゴリズム．

  • 任意に頂点を選び，\(v_{0}\) とする．
  • \(v_{0}\) から最も遠い点の一つを \(v_{1}\) とする．
  • \(v_{1}\) から最も遠い点の一つを \(v_{2}\) とする．

\(v_{1}, v_{2}\) が直径の一つ．

実装

始点を固定したとき，最も遠い点は DFSで求まる． つまり DFSを 2回実行すれば，木の直径が求まる．

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

ll question(ll a,ll b){
  cout << "? " << a+1 << " " << b+1 << endl;
  ll x; cin >> x;
  return x;
}

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

  const ll inf = n * (ll)1e6;
  auto f = [&](ll src) -> pll {
    ll ma = -1, ind = -1;
    rep(i,n) if(i!=src){
      if(chmax(ma, question(src,i))){
        ind = i;
      }
    }

    return {ma, ind};
  };
 
  auto [_,i] = f(0);
  auto [ma,__] = f(i);

  cout << "! " << ma << endl;

  return 0;
}

AtCoder Beginner Contest 339D問題

 

解法

2人のプレイヤーの座標の組を頂点にもつグラフ上でBFS．

実装

移動先の位置は，今のマスにも依存することに注意． 壁に向かって移動しようとしたときは，今の位置にとどまるが， もう一方のプレイヤーが移動できる場合がある．

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

ll dis[65][65][65][65];
ll vis[65][65][65][65];

int main() {
  ll n;
  cin >> n;
  vector<string> s(n); cinv(s);

  auto valid = [&](ll& x) -> void {
    chmin(x, n-1);
    chmax(x, 0LL);
  };

  queue<vll> q;
  auto push = [&](ll d, ll x0, ll y0, ll x1, ll y1) -> void {
    if(vis[x0][y0][x1][y1]) return;
    vis[x0][y0][x1][y1] = true;

    dis[x0][y0][x1][y1] = d;
    q.push({x0,y0,x1,y1});
  };


  vll tmp;
  rep(x,n) rep(y,n){
    if(s[x][y] == 'P') tmp.push_back(x), tmp.push_back(y);
  }
  push(0, tmp[0], tmp[1], tmp[2], tmp[3]);
  while(q.size()){
    vll cu = q.front(); q.pop();
    ll x0 = cu[0];
    ll y0 = cu[1];
    ll x1 = cu[2];
    ll y1 = cu[3];
    ll cd = dis[x0][y0][x1][y1];

    vll dx = {1,0,-1,0};
    vll dy = {0,1,0,-1};
    rep(i,4) {
      ll nx0 = x0 + dx[i];
      ll nx1 = x1 + dx[i];
      ll ny0 = y0 + dy[i];
      ll ny1 = y1 + dy[i];
      valid(nx0);
      valid(ny0);
      valid(nx1);
      valid(ny1);
      if(s[nx0][ny0] == '#') nx0 = x0, ny0 = y0;
      if(s[nx1][ny1] == '#') nx1 = x1, ny1 = y1;

      push(cd + 1, nx0, ny0, nx1, ny1);
    }

  }


  ll ans = INFL;
  rep(x,n) rep(y,n) if(vis[x][y][x][y]){
    chmin(ans, dis[x][y][x][y]);
  }

  if(ans >= INFL) ans = -1;
  cout << ans << endl;

  return 0;
}

AtCoder Beginner Contest 338D問題

\(\def \ra {\rightarrow}\)

ABC338D

解法

1本封鎖されれば，通るべき path が一意に定まる． 相異なる vertices \(a,b \in N\) を固定する．\(a < b\) と仮定してよい． Edge \(e \not\in [a,b)\) を切断したとき，path は \(a \ra a+1 \ra \cdots \ra b\) となり， \(e \in [a,b)\) を切断したとき，path は \(a \ra a-1 \ra \cdots \ra b\) となる．

実装

区間に対する和を保留して，最後にまとめるので，imos 法で解ける．

注意

元のグラフの edge を vertex に， 元のグラフの vertex を 区間の境目と考える．

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

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

  vll v(n+1);
  // edge in [l,r) を切った場合
  auto add = [&](ll l, ll r, ll x) -> void {
    if(r < l) swap(l,r);
    v[l] += x;
    v[r] -= x;
  };

  rep(i,m-1){
    ll s = a[i];
    ll t = a[i+1];
    if(s > t) swap(s,t);
    ll a = t - s;
    ll b = n - a;

    add(0,s,a); // rem : a
    add(s,t,b); // rem : b
    add(t,n,a); // rem : a
  }

  rep(i,n){
    v[i+1] += v[i];
  }

  ll ans = *min_element(v.begin(), v.begin()+n);
  cout << ans << endl;

  return 0;
}

AtCoder Beginner Contest 345D問題

ABC345D

解法

回転と裏返しも良いと書いてあるが，裏返しは意味がない． 回転が高々 \(2^{N}\) 通り， 埋める順番が高々 \(N!\) 通り． \(N \leq 7\) なので，遷移に時間が多少掛かっても間に合う．
判定問題を試すときは，取りこぼしさえ無ければ十分． 数え上げ問題の場合は，取りこぼしがないだけでなく，重複も取り除かないといけない． 今回は判定問題なので，重複しても良い． 左上のマスから全探索して，長方形の左上を置くことにする． これを，並べ替え \(N!\) と回転 \(2^{N}\) に対して行う．

実装

DFSで実装した． next_permutation と bitmask でも可能．

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

int main() {
  ll n,h,w;
  cin >> n >> h >> w;
  vector<pll> ab(n);
  rep(i,n){
    cin >> ab[i].first >> ab[i].second;
  }

  using B = vector<string>; // board

  auto dfs = [&](auto dfs, B s, vector<bool>& used) -> bool {
    ll sx = -1, sy = -1;
    [&](){
      rep(x,h) rep(y,w) if(s[x][y] == '.'){
        sx = x;
        sy = y;
        // break; // 一つしか for を抜けない
        return ;
      }
    }();
   
    if(sx == -1) return true;

    bool any = true;
    rep(i,used.size()) any &= used[i];
    if(any) return false;

    // rectangle
    rep(ri,n) if(!used[ri]){ // used 判定
      auto [a,b] = ab[ri];
      rep(flip, 2){
        swap(a,b);

        B ns = s;
        bool ok = [&]() -> bool {
          if(sx + a > h) return false;
          if(sy + b > w) return false;

          rep(xi, a) rep(yi, b){
            ll nx = sx + xi;
            ll ny = sy + yi;
            if(ns[nx][ny] != '.') return false;
            ns[nx][ny] = '#';
          }

          return true;
        }();

        if(ok){
          used[ri] = true;
          if(dfs(dfs, ns, used)) return true;
          used[ri] = false;
        }
      }
    }

    return false;
  };
 
  B s(h, string(w,'.'));
  vector<bool> used(n);

  yesno(dfs(dfs, s, used));


  return 0;
}

AtCoder Beginner Contest 345C問題

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

ABC345C

解法
\(X := S\) から 1 swap で作れる string 全体の集合

とする．答えは \(|X|\).

  • \(S \in X \iff\) for some \(i\) and \(j\) \(\in N\) such that \(i < j\) and \(S_{i} = S_{j}\)
  • \begin{align} X - \{S\} &= \set{T}{for\,\,some\,\,i\,\,and\,\,j\,\,such\,\,that\,\,i\,\,<\,\,j\,\,and\,\,S_{i}\,\,\neq\,\,S_{j} and\,\,T\,\,is\,\,the\,\,string\,\,swap\,\,i\,\,and\,\,j\,\,on\,\,S}\,\,\\ &\cong \set{(i,j)\,\,\in\,\,N^{2}}{for\,\,some\,\,i\,\,and\,\,j\,\,such\,\,that\,\,i\,\,<\,\,j\,\,and\,\,S_{i}\,\,\neq\,\,S_{j}}\,\,\\ \end{align}

基本は \(X - \{S\} \) を数えればよく， \(S \in X\) のときだけ +1 すればよい．

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


int main() {
  string s; cin >> s;
  ll n = s.length();

  vll cnt(26);
  bool f = false;
  rep(i,n){
    cnt[s[i]-'a']++;
    if(cnt[s[i]-'a'] >= 2) f = true;
  }

  ll ans = f;
  ans += nC2(n);
  rep(i,26) ans -= nC2(cnt[i]);
  cout << ans << endl;


  return 0;
}