AtCoder abc323 参加メモ

AtCoder ABC

UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323) - AtCoder

B - Round-Robin Tournament

それぞれ勝った回数をカウントして、回数の多い順に sort する。

勝ち数が同じ場合には番号の早い順となるため注意。

#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; cin >> n;
  vector<int> cnt(n);
  REP(i,n) {
    string s; cin >> s;
    REP(j,n) if (s[j] == 'o') cnt[i]++;
  }

  vector<P> p(n);
  REP(i,n) p[i] = { cnt[i], -(i+1) }; // 勝ち数が同じ場合は番号の早い順
  sort(p.rbegin(),p.rend());

  for(auto [_,v]: p) cout << -v << " ";
  return 0;
}

C - World Tour Finals

他のプレイヤーの総合得点を上回るまで、貪欲に得点の高い問題から解いていけば良い。

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

  vector<int> score(n);
  REP(i,n) {
    REP(j,m) if (s[i][j] == 'o') score[i] += a[j];
    score[i] += (i+1);
  }

  vector<P> p(m);
  REP(i,m) p[i] = {a[i],i};
  sort(p.rbegin(),p.rend());
  vector<int> order(m);
  REP(i,m) order[i] = p[i].second;

  int mx = *max_element(score.begin(),score.end());
  REP(i,n) {
    int ans = 0;
    for(auto j: order) {
      if (score[i] >= mx) break;
      if (s[i][j] == 'o') continue;
      score[i] += a[j];
      ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

D - Merge Slimes

貪欲にサイズの小さいスライムから合成していく

#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; cin >> n;
  map<ll,ll> mp;
  REP(i,n) {
    int s,c; cin >> s >> c;
    mp[s] += c;
  }

  int ans = 0;
  for(auto [size,cnt]: mp) {
    mp[size*2] += cnt/2;
    ans += cnt % 2;
  }
  cout << ans << endl;
  return 0;
}

E - Playlist

DP で解いた。

  • dp[i][j] = 時刻 i のときに j:0(1番目), j:1(1番目以外) の曲が流れているときの確率
#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 mint = modint998244353;

int main() {
  int n,x; cin >> n >> x;
  vector<int> t(n);
  REP(i,n) cin >> t[i];

  // dp[i][j] := 時刻 i のときに j:0(1番目), j:1(1番目以外) になる確率
  vector dp(x+2,vector<mint>(2));
  mint r = (mint)1/n;
  REP(i,n) dp[min(x+1,t[i])][i == 0 ? 0 : 1] += r;

  REP(i,x+1) REP(j,n) REP(k,2) {
    if (dp[i][k] == 0) continue;
    dp[min(x+1,i + t[j])][j == 0 ? 0 : 1] += dp[i][k]*r;
  }

  cout << dp[x+1][0].val() << endl;
  return 0;
}

雑感

C で凡ミスして2WA、E は方針はすぐたったが、確率計算がうまくあわなくてかなりロスした。 確率や期待値問題、どうしても苦手意識がある

tic40さんのユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)での成績：1824位
パフォーマンス：1266相当
レーティング：1133→1147 (+14) :)
#AtCoder #ユニークビジョンプログラミングコンテスト2023秋(ABC323) https://atcoder.jp/users/tic40/history/share/abc323?lang=ja