Do Something

AtCoder abc384 参加メモ

AtCoder

Toyota Programming Contest 2024#12（AtCoder Beginner Contest 384） - AtCoder

A - aaaadaa

#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; char c1,c2; string s;
  cin >> n >> c1 >> c2 >> s;
  for(auto c: s) cout << (c == c1 ? c : c2);
  return 0;
}

B - ARC Division

#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,r; cin >> n >> r;
  REP(i,n) {
    int d,a; cin >> d >> a;
    if (d==1 && r >= 1600 && r <= 2799) r+=a;
    if (d==2 && r >= 1200 && r <= 2399) r+=a;
  }
  cout << r << endl;
  return 0;
}

C - Perfect Standings

bit 演算ですべてのケースを列挙してソートする。スコアの降順、文字列の昇順だが、スコアを負に反転しておけば昇順ソートするだけ良くなる

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

int main() {
  const int n = 5;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  vector<pair<int,string>> ans;
  REP(bit,1<<n) {
    int score = 0;
    string s;
    REP(i,n) if (bit >> i & 1) {
      score += a[i];
      s += char('A'+i);
    }
    ans.emplace_back(-score,s);
  }
  sort(ans.begin(),ans.end());
  for(auto [_,s]: ans) if (s.size()) cout << s << endl;
  return 0;
}

D - Repeated Sequence

s は数列aの合計数の剰余にしていい
累積和を数列aの2倍の長さ分取っておく
a[i] からスタートしたときにちょうど s になる位置があるか累積和から二分探索で求める

#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; ll s; cin >> n >> s;
  vector<int> a(n);
  REP(i,n) cin >> a[i];
  vector<ll> sum(n*2+1);
  REP(i,n*2) sum[i+1] = sum[i] + a[i%n];

  s %= accumulate(a.begin(),a.end(),0LL);
  int ok = 0;
  REP(i,n) ok |= binary_search(sum.begin(),sum.end(),sum[i]+s);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

E - Takahashi is Slime 2

優先度付きキューで強さの小さい順に、隣接しているまだ取り込んでいないスライムを管理する。新しくスライムを吸収したときには、そのスライムのマスに隣接しているまだ取り込んでいないスライムをキューに追加していく。

#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;
using T = pair<ll,pair<int,int>>;
const vector<int> di = {-1,0,1,0};
const vector<int> dj = {0,1,0,-1};

int main() {
  int h,w,x; cin >> h >> w >> x;
  int p,q; cin >> p >> q; p--; q--;
  vector s(h,vector<ll>(w));
  REP(i,h) REP(j,w) cin >> s[i][j];

  priority_queue<T, vector<T>, greater<T>> pq;
  vector visited(h,vector<int>(w));

  ll power = 0;
  auto push = [&](int i, int j) -> void {
    visited[i][j] = 1;
    power += s[i][j];
    REP(k,4) {
      int ni = i+di[k], nj = j+dj[k];
      if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
      if (visited[ni][nj]) continue;
      pq.emplace(s[ni][nj], P{ni,nj});
    }
  };
  push(p,q);

  while(pq.size()) {
    auto [_, pos] = pq.top(); pq.pop();
    auto [i,j] = pos;
    if (visited[i][j]) continue;
    if ((double)s[i][j] >= (double)power/x) continue;
    push(i,j);
  }
  cout << power << endl;
  return 0;
}

雑感

E は最初 set で隣接の未吸収スライムマスだけを管理する方針で実装した。Nが小さいのでいけそうに思ったが3ケースTLEで通らず。優先度付きキューに実装し直しでタイムロス。 F は最近よく見る二重 Σ の計算量をなんとかする問題。相変わらずこういうのは苦手。