競技プログラミング日記

主に AtCoder の記事です

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;
}

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;
}