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
