AtCoder abc376 参加メモ
AtCoder Beginner Contest 376 - AtCoder
A - Candy Button
最後に飴をもらった時刻を記憶しておく
#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,c; cin >> n >> c; int p = -1e4, ans = 0; REP(_,n) { int t; cin >> t; if (t-p >= c) { ans++; p = t; } } cout << ans << endl; return 0; }
B - Hands on Ring (Easy)
愚直にシミュレーションしたが、B にしては実装が重かった。 L or R、左 or 右回りで場合分けがあり、これをそのまま書くと煩雑になってしまう。
- R を動かす場合は swap(l,r) をし、コード上は常に L を動かすだけにする
- 左 or 右回りは dir で動く方向を +1 or -1 で持たせて置けば場合分けが不要になる
#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,q; cin >> n >> q; int l = 0, r = 1; auto f = [&](int dir, int pos, int t) { int cost = 0; while(pos != t) { if (pos == r) { cost = 1e9; break; } cost++; pos = ((pos+dir) % n + n) % n; } return cost; }; int ans = 0; REP(_,q) { char h; int t; cin >> h >> t; t--; if (h == 'R') swap(l,r); ans += min(f(1,l,t),f(-1,l,t)); l = t; if (h == 'R') swap(l,r); } cout << ans << endl; return 0; }
C - Prepare Another Box
追加する箱のサイズを二分探索で求めた。 おもちゃの入れ方は、一番小さいおもちゃから、一番小さい箱に貪欲に入れていくのが最適となる。
#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<int> a(n),b(n-1); REP(i,n) cin >> a[i]; REP(i,n-1) cin >> b[i]; sort(a.begin(),a.end()); auto f = [&](int x) -> bool { auto c = b; c.push_back(x); sort(c.begin(),c.end()); REP(i,n) if (a[i] > c[i]) return false; return true; }; int ok = 1e9+5, ng = 0; while(ok-ng>1) { int mid = (ok+ng)/2; if (f(mid)) ok = mid; else ng = mid; } cout << (ok > 1e9 ? -1 : ok) << endl; return 0; }
D - Cycle
頂点1 から BFS して頂点 1 に最短で戻る経路を探索する。 ED問題にしては?とくに捻りはなくBFSするだけだった。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' const int INF = numeric_limits<int>::max(); int main() { int n,m; cin >> n >> m; vector g(n,vector<int>()); REP(i,m) { int a,b; cin >> a >> b; a--; b--; g[a].push_back(b); } vector<int> dist(n,INF); queue<int> q; q.push(0); dist[0] = 0; while(q.size()) { auto now = q.front(); q.pop(); for(auto v: g[now]) { if (v == 0) { cout << dist[now]+1 << endl; return 0; } if (dist[v] <= dist[now]+1) continue; dist[v] = dist[now]+1; q.push(v); } } cout << -1 << endl; return 0; }
E - Max × Sum
{a,b} のペアを昇順ソートして a が小さい値から順番に見ていく。 a は昇順に見ていけば今の a が常に最大の値となる。 Σb は、k 個を越えたら以降は一番大きい値を捨てていけば良い。
#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>; const ll LINF = numeric_limits<ll>::max(); int main() { int t; cin >> t; REP(_,t) { int n,k; cin >> n >> k; vector<P> items(n); REP(i,n) cin >> items[i].first; REP(i,n) cin >> items[i].second; sort(items.begin(),items.end()); priority_queue<int> pq; ll sumb = 0, ans = LINF; for(auto [a,b]: items) { pq.push(b); sumb += b; if ((int)pq.size() == k) { ans = min(ans,(ll)a * sumb); sumb -= pq.top(); pq.pop(); } } cout << ans << endl; } return 0; }
雑感
B 問題でかなり時間かけてしまい大焦り。 D 問題もスタートが頂点1 というのを見落として、全体で最小サイクルを探索するコードを書いてしまった。 F問題は場合分けを考えていたら頭がおかしくなってきたので諦め。
D 問題解いた時点ではかなり遅かったが、E が解けたおかげで Highest 更新。まだいつ緑に落ちてもおかしく水準なのでヒヤヒヤする。
tic40さんのAtCoder Beginner Contest 376(Promotion of AtCoder Career Design DAY)での成績:1469位 パフォーマンス:1409相当 レーティング:1214→1235 (+21) :) Highestを更新しました! #AtCoder #ABC376(PromotionofAtCoderCareerDesignDAY) https://atcoder.jp/users/tic40/history/share/abc376?lang=ja