AtCoder abc382 参加メモ

ABC AtCoder

AtCoder Beginner Contest 382 - AtCoder

A - Daily Cookie

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,d; string s; cin >> n >> d >> s;
  for(auto c: s) if (c == '@') n--;
  cout << n+d << endl;
  return 0;
}

B - Daily Cookie 2

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,d; string s; cin >> n >> d >> s;
  for(int i = n-1; i >= 0; i--) if (d && s[i] == '@') s[i] = '.', d--;
  cout << s << endl;
  return 0;
}

C - Kaiten Sushi

寿司はどの順番で流しても結果に変わりはない。

寿司の美味しさの降順に処理することにすれば、美味しさが大きいものは先頭から取っていくので、a[cur] 以降の人だけをチェックしていくだけで良くなる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using P = pair<int,int>;

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(n),b(m);
  REP(i,n) cin >> a[i];
  REP(i,m) cin >> b[i];
  vector<P> pb;
  REP(i,m) pb.emplace_back(b[i],i);
  sort(pb.rbegin(),pb.rend());

  vector<int> ans(m,-1);
  int cur = 0;
  REP(i,m) {
    while(cur < n) {
      if (a[cur] <= pb[i].first) {
        ans[pb[i].second] = cur+1;
        break;
      }
      cur++;
    }
  }
  for(auto v: ans) cout << v << endl;
  return 0;
}

D - Keep Distance

DFS がうまく書けますかという問題。DFS の計算量怪しいなと思いつつも i <= m で投げて TLE を出してしまった。 達成不可能な数列をちゃんと枝刈りすれば間に合った。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,m; cin >> n >> m;
  vector<int> a;
  vector<vector<int>> ans;

  auto dfs = [&](auto dfs) -> void {
    int sz = a.size();
    if (sz == n) { ans.push_back(a); return; }

    for(int i = sz ? a.back()+10 : 1; i <= m-(10*(n-1-sz)); i++) {
      a.push_back(i);
      dfs(dfs);
      a.pop_back();
    }
  };

  dfs(dfs);
  cout << ans.size() << endl;
  for(auto v: ans) {
    for(auto w: v) cout << w << " ";
    cout << endl;
  }
  return 0;
}

E - Expansion Packs

期待値問題。難しい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,x; cin >> n >> x;
  vector<double> p(n);
  REP(i,n) cin >> p[i], p[i] /= 100.0;

  // dp[i][j] := パック内の i 枚目まででレアカードを j 枚持つ確率
  vector<double> dp(n+1);
  dp[0] = 1.0; // レアカード 0 枚は 100 %
  REP(i,n) {
    vector<double> prev(n+1);
    swap(dp,prev);
    REP(j,i+1) {
      dp[j] += prev[j] * (1.0 - p[i]); // レアカードが出ない
      dp[j+1] += prev[j] * p[i]; // レアカードが出る
    }
  }

  // f[i] := レアカードが x 枚になるまで必要なパック数の期待値
  vector<double> f(x+1);
  for(int i = 1; i <= x; i++) {
    double sum = 0.0;
    for(int j = 1; j <= min(i-1,n); j++) sum += dp[j] * f[i-j];
    sum += 1.0;
    // f[i] = dp[0] * f[i] + sum
    // f[i] = sum / (1 - dp[0])
    f[i] = sum / (1.0 - dp[0]);
  }

  printf("%.10f\n", f[x]);
  return 0;
}

F - Falling Bars

hの大きい(下にある)バーから順に処理。 遅延セグ木で range min を求めることで、バーをどこまで移動できるかを管理する

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using T = tuple<int,int,int>;
const int INF = numeric_limits<int>::max();

using S = int;
using F = int;
S op(S a, S b) { return min(a,b); }
S e() { return INF; }
S mapping(F f, S x) { return min(x,f); }
F composition(F f, F g) { return min(f,g); }
F id() { return INF; }

int main() {
  int h,w,n; cin >> h >> w >> n;
  vector bars(h,vector<T>());
  REP(i,n) {
    int r,c,l; cin >> r >> c >> l; r--; c--;
    bars[r].emplace_back(c,l,i);
  }

  lazy_segtree<S, op, e, F, mapping, composition, id> seg(w);
  seg.apply(0,w,h-1);
  vector<int> ans(n);
  for(int r = h-1; r >= 0; r--) {
    for(auto [c,l,id]: bars[r]) {
      int now = seg.prod(c,c+l);
      ans[id] = now;
      seg.apply(c,c+l,now-1);
    }
  }

  REP(i,n) cout << ans[i]+1 << endl;
  return 0;
}

雑感

hightest 更新！順位も過去最高だった。G は手も足も出ず。

tic40さんのAtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）での成績：325位
パフォーマンス：1911相当
レーティング：1233→1322 (+89) :)
Highestを更新しました！
#AtCoder #AtCoderプログラミングコンテスト2024（ABC382） https://atcoder.jp/users/tic40/history/share/abc382?lang=ja