AtCoder abc303 参加メモ

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） - AtCoder

B - Discord

隣接行列で人 i が人 j と前後で並んでいたか？を持っておいて、一度も並んでいない二人組の数を集計する

#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 a(m, vector<int>(n));
  REP(i,m) REP(j,n) { cin >> a[i][j]; a[i][j]--; }

  vector s(n, vector<bool>(n));
  REP(i,m) REP(j,n) {
    int now = a[i][j];
    int prev = a[i][max(0,j-1)];
    int nx = a[i][min(n-1,j+1)];
    s[now][prev] = s[now][nx] = true;
  }

  int ans = 0;
  REP(i,n) for(int j = i+1; j < n; j++) if (!s[i][j]) ans++;
  cout << ans << endl;
  return 0;
}

C - Dash

そのままシュミレーションする。

今いる地点に回復アイテムがあるかの判定は set を使うと楽。回復アイテムは複数回使うことはできないので、使ったら set から削除しておく。

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

map<char,P> mp {
  {'R', {1,0}},
  {'L', {-1,0}},
  {'U', {0,1}},
  {'D', {0,-1}}
};

int main() {
  int n,m,h,k; cin >> n >> m >> h >> k;
  string s; cin >> s;

  set<P> st;
  REP(i,m) {
    int x,y; cin >> x >> y;
    st.emplace(x,y);
  }

  int nx = 0, ny = 0;
  bool ok = true;
  REP(i,n) {
    auto [dx,dy] = mp[s[i]];
    nx += dx, ny += dy;
    h--;
    if (h < 0) { ok = false; break; }
    if (st.count({nx,ny}) && (h < k)) {
      h = k;
      st.erase({nx,ny});
    }
  }

  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

D - Shift vs. CapsLock

以下のように DP を定義して解いた

dp[i][j] := i 文字目までみたとき、 CapsLock の状態が j( on/off ) のときの最短の時間

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;
const ll LINF = 1e18;
template<class T> void chmin(T& a, T b) { a = min(a,b); }

int main() {
  ll x,y,z; cin >> x >> y >> z;
  string s; cin >> s;
  int n = s.size();

  vector dp(n+1, vector<ll>(2,LINF));
  dp[0][0] = 0;
  dp[0][1] = z;
  REP(i,n) {
    // CapsLock off
    if (s[i] == 'a') {
      chmin(dp[i+1][0], dp[i][0] + x);
      chmin(dp[i+1][1], dp[i][0] + z + y);
    } else {
      chmin(dp[i+1][0], dp[i][0] + y);
      chmin(dp[i+1][1], dp[i][0] + z + x);
    }
    // CapsLock on
    if (s[i] == 'a') {
      chmin(dp[i+1][1], dp[i][1] + y);
      chmin(dp[i+1][0], dp[i][1] + z + x);
    } else {
      chmin(dp[i+1][1], dp[i][1] + x);
      chmin(dp[i+1][0], dp[i][1] + z + y);
    }
  }

  ll ans = min(dp[n][0],dp[n][1]);
  cout << ans << endl;
  return 0;
}

E - A Gift From the Stars

次数が 1 の頂点と隣接している頂点は必ず星の中心となる。その星の中心と隣接している頂点を調べ、次数が 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; cin >> n;
  vector g(n,vector<int>());
  vector<int> deg(n);
  REP(i,n-1) {
    int u,v; cin >> u >> v;
    u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
    deg[u]++; deg[v]++;
  }

  // 頂点 i から 次数が 1 より大きい頂点を探す
  auto f = [&](int i) {
    if (i >= 0) for(auto v: g[i]) if (deg[v] > 1) return v;
    return -1;
  };

  vector<int> ans;
  queue<int> q;
  REP(i,n) if (deg[i] == 1) q.push(i);
  while(q.size()) {
    int center = f(q.front()); q.pop();
    if (center == -1) continue;
    deg[center] = 0;
    for(auto v: g[center]) {
      deg[v]--;
      if (deg[v] == 1) q.push(f(v));
    }
    ans.push_back(g[center].size());
  }

  sort(ans.begin(),ans.end());
  for(int v: ans) cout << v << " ";
  return 0;
}