AtCoder abc308 参加メモ

B - Default Price

D のいずれとも異なる色の皿の料理は一皿 $ P_0 $ 円ということに注意する

#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<string> c(n),d(m);
  vector<int> p(m+1);
  REP(i,n) cin >> c[i];
  REP(i,m) cin >> d[i];
  REP(i,m+1) cin >> p[i];

  map<string,int> mp;
  REP(i,m) mp[d[i]] = p[i+1];

  int ans = 0;
  REP(i,n) ans += mp.count(c[i]) ? mp[c[i]] : p[0];
  cout << ans << endl;
  return 0;
}

C - Standings

double でそのまま計算すると誤差で wa となる。long double を使えば通るが、解説のように分母を取って整数で比較したほうが安全かもしれない

#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<pair<long double,int>> vp;
  REP(i,n) {
    long double a,b; cin >> a >> b;
    long double r = a / (a+b);
    vp.emplace_back(r,-i);
  }
  sort(vp.rbegin(),vp.rend());
  for(auto [_,v]: vp) cout << (-v+1) << " ";
  return 0;
}

D - Snuke Maze

H,W <= 500 という制約のため DFS で間に合う

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

const vector<pair<int, int>> moves = { {1,0},{0,1},{-1,0},{0,-1} };
const string target = "snuke";
const int sz = 5;

int main() {
  int h,w; cin >> h >> w;
  vector<string> s(h);
  REP(i,h) cin >> s[i];

  vector visited(h,vector<bool>(w));
  auto dfs = [&](auto self, int x, int y, int i) -> void {
    if (s[x][y] != target[i % sz]) return;
    if (x == h-1 && y == w-1) { cout << "Yes" << endl; exit(0); }

    visited[x][y] = true;
    for(auto [dx,dy]: moves) {
      int nx = x + dx, ny = y + dy;
      if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
      if (visited[nx][ny]) continue;
      self(self,nx,ny,i+1);
    }
  };

  dfs(dfs,0,0,0);
  cout << "No" << endl;
  return 0;
}

E - MEX

数は3通りしかない。頭から見て言って M, ME について Mの数字 x Eの数字の組み合わせでそれぞれ何通りあるか記録していく。

X が来たときは上記で記録しておいた ME に対応する数字と X の数字で mex を取り、 mex * MEの合計数を答えに加算していく

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

  auto mex = [](int x, int y, int z) {
    vector<bool> mex(3);
    mex[x] = mex[y] = mex[z] = true;
    REP(i,3) if (!mex[i]) return i;
    return 3;
  };

  vector<int> m(3);
  vector e(3,vector<ll>(3));
  ll ans = 0;
  REP(i,n) {
    if (s[i] == 'M') m[a[i]]++;
    if (s[i] == 'E') REP(j,3) e[j][a[i]] += m[j];
    if (s[i] == 'X') {
      REP(j,3) REP(k,3) ans += mex(j,k,a[i]) * e[j][k];
    }
  }
  cout << ans << endl;
  return 0;
}

F - Vouchers

値引き金額が最も大きいクーポンから優先して使っていけば最も合計金額を小さくできる。

値引き金額が最も大きいクーポンから順に、二分探索でクーポンを使うことができる最も価格の低い商品を貪欲に選んでいけばよい。

#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 P = pair<int,int>;

int main() {
  int n,m; cin >> n >> m;
  vector<int> p(n),l(m),d(m);
  multiset<int> st;
  REP(i,n) { cin >> p[i]; st.insert(p[i]); }
  REP(i,m) cin >> l[i];
  REP(i,m) cin >> d[i];

  vector<P> pc(m);
  REP(i,m) pc[i] = {d[i],l[i]};
  sort(pc.rbegin(),pc.rend());

  ll ans = accumulate(p.begin(),p.end(),0LL);
  for(auto [nd,nl]: pc) {
    auto it = st.lower_bound(nl);
    if (it == st.end()) continue;
    ans -= nd;
    st.erase(it);
  }
  cout << ans << endl;
  return 0;
}

今回の成績

F 問題まで解けたけどもそれでも 3 桁位は厳しかった。今回は全体的に簡単だったかもしれない

tic40さんのCodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)での成績：1117位
パフォーマンス：1446相当
レーティング：1124→1161 (+37) :)
Highestを更新しました！
#AtCoder #CodeQUEEN2023予選(ABC308) https://atcoder.jp/users/tic40/history/share/abc308?lang=ja