AtCoder abc321 参加メモ

AtCoder ABC

SuntoryProgrammingContest2023（AtCoder Beginner Contest 321） - AtCoder

B - Cutoff

N ラウンド目に取り得る値を全探索する

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

  int ans = -1;
  REP(i,101) {
    auto b = a;
    b.push_back(i);
    sort(b.begin(),b.end());
    int tot = accumulate(b.begin()+1,b.end()-1,0);
    if (tot >= x) { ans = i; break; }
  }

  cout << ans << endl;
  return 0;
}

C - 321-like Searcher

x は最大で 9,876,543,210 になる。 同じ数は現れないため、0〜10 の数それぞれ1度だけ使うか、一度も使わないかどちらか。これは 210 と小さいため DFS で全列挙できる。

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

  vector<ll> ans;
  auto dfs = [&](auto self, ll i) -> void {
    ans.push_back(i);
    REP(ni,i%10) self(self,i*10+ni);
  };

  for(ll i = 1; i <= 9; i++) dfs(dfs,i);
  sort(ans.begin(),ans.end());
  cout << ans[k] << endl;
  return 0;
}

D - Set Menu

まず a, b は sort して問題ない。 a を固定して考えたとき、a[i] + b[j] >= p となる j の位置は二分探索で求まる。 このときの

  • p 未満となる合計は a[i] * j + (b[0] + b[1] + ... b[j-1])
  • p 以上となる合計は p * (m-j)

b[0] + b[1] + ... + b[x] は累積和を求めておくと O(1) で求められる

#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() {
  ll n,m,p; cin >> n >> m >> p;
  vector<ll> a(n),b(m);
  REP(i,n) cin >> a[i];
  REP(i,m) cin >> b[i];

  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  vector<ll> bs(m+1); // b の累積和
  REP(i,m) bs[i+1] = bs[i] + b[i];

  ll ans = 0;
  // a を固定して考える
  REP(i,n) {
    // a+b >= p となる b の index
    int idx = lower_bound(b.begin(),b.end(),p-a[i]) - b.begin();
    // a+b < p となる組み合わせの合計
    ans += a[i] * idx + bs[idx];
    // a+b >= p となる組み合わせの合計
    ans += (m-idx) * p;
  }
  cout << ans << endl;
  return 0;
}

雑感

MacOS アップデートしたら C++ コンパイル通らなくなるという... 開始5分前に気づいて焦った。結局ローカルでコンパイルできないままコンテスト始まってしまったため、AtCoder のコードテストで動作確認することにしてしのいだ。https://atcoder.jp/contests/apg4b/custom_test

E - Complete Binary Tree は時間が十分にあったものの、解ききれず。典型ぽくない adhoc な問題がでるとなかなか解けないな。

tic40さんのサントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）での成績：1624位
パフォーマンス：1326相当
レーティング：1069→1097 (+28) :)
#AtCoder #サントリープログラミングコンテスト2023（ABC321） https://atcoder.jp/users/tic40/history/share/abc321?lang=ja