AtCoder abc309 参加メモ

AtCoder

Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309) - AtCoder

B - Rotate

愚直に時計回りへずらしていった。もっと簡単な方法あるかな。

#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<string> a(n);
  REP(i,n) cin >> a[i];

  auto b = a;
  REP(j,n-1) b[0][j+1] = a[0][j];
  REP(i,n-1) b[i+1][n-1] = a[i][n-1];
  for(int j = n-1; j > 0; j--) b[n-1][j-1] = a[n-1][j];
  for(int i = n-1; i > 0; i--) b[i-1][0] = a[i][0];

  REP(i,n) {
    REP(j,n) cout << b[i][j];
    cout << endl;
  }
  return 0;
}

C - Medicine

累積和で何日目に何錠飲むかを求めて、k 以下になった日が答え。

$ a_i $ の制約が大きいため map で座標圧縮した。

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

int main() {
  int n,k; cin >> n >> k;
  map<int,ll> mp;
  REP(i,n) {
    int a,b; cin >> a >> b;
    mp[1] += b; mp[1+a] -= b;
  }

  ll p = 0;
  for(auto [i,v]: mp) {
    mp[i] += p;
    if (mp[i] <= k) { cout << i << endl; return 0; }
    p = mp[i];
  }

  return 0;
}

D - Add One Edge

頂点1 と 頂点 N1+N2 からそれぞれ bfs で最短経路を求めて、それぞれの最大の距離の地点同士を連結させると d が最大値となる

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

int main() {
  int n1,n2,m; cin >> n1 >> n2 >> m;
  int n = n1+n2;
  vector g(n,vector<int>());
  REP(i,m) {
    int a,b; cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  auto bfs = [&](int i) {
    vector<int> dist(n,INF);
    queue<int> q;
    q.push(i);
    dist[i] = 0;
    while(q.size()) {
      int v = q.front(); q.pop();
      for(auto nv: g[v]) {
        if (dist[nv] != INF) continue;
        q.push(nv);
        dist[nv] = dist[v]+1;
      }
    }
    return dist;
  };

  auto d1 = bfs(0);
  auto d2 = bfs(n-1);
  int ans1 = *max_element(d1.begin(), d1.begin() + n1);
  int ans2 = *max_element(d2.begin() + n1, d2.end());
  int ans = ans1 + ans2 + 1;
  cout << ans << endl;
  return 0;
}
}

E - Family and Insurance

親から子へ dfs する。 引数に最大何世代先まで補償できるかを持っておき、今の人が保険に入っていたら親からの補償と自身の保険の補償との最大の世代数を次へ渡していけばいい。

#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 g(n,vector<int>());
  for(int i = 1; i < n; i++) {
    int p; cin >> p; p--;
    g[p].push_back(i);
  }

  vector<int> d(n);
  REP(i,m) {
    int x,y; cin >> x >> y; x--;
    d[x] = max(d[x],y);
  }

  auto bfs = [&](auto self, int i, int p) -> int {
    int res = 0;
    if (p > 0 || d[i] > 0) res++;
    int np = max(p-1,d[i]);
    for(auto v: g[i]) res += self(self,v,np);
    return res;
  };

  cout << bfs(bfs,0,0) << endl;
  return 0;
}

今回の成績

tic40さんのデンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）での成績：1541位
パフォーマンス：1285相当
レーティング：1161→1174 (+13) :)
Highestを更新しました！
#AtCoder #デンソークリエイトプログラミングコンテスト2023（ABC309） https://atcoder.jp/users/tic40/history/share/abc309?lang=ja