AtCoder Beginner Contest 246 - AtCoder の参加メモ
C - Coupon
greedy。
クーポンでX円値引きできる商品はクーポンを使えるだけ使って良い。 X円未満しか値引きできない商品だけ残ったときは、降順にソートして値段が高いものから順番にクーポンを使っていく。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) using ll = long long; int main() { int n,k,x; cin >> n >> k >> x; vector<int> a(n); REP(i,n) cin >> a[i]; REP(i,n) { int t = min(k, a[i]/x); a[i] -= t*x; k -= t; } sort(a.rbegin(),a.rend()); ll ans = 0; for (int i = k; i < n; i++) ans += a[i]; cout << ans << endl; return 0; }
D - 2-variable Function
尺取り。aを固定して二分探索しても間に合った。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) using ll = long long; ll f(ll a,ll b) { return a*a*a + a*a*b + a*b*b + b*b*b; } int main() { ll n; cin >> n; ll ans = 9e18; ll a = 0, b = 1e6; while(a <= b) { ll now = f(a,b); if (n <= now) { ans = min(ans, now); b--; } else { a++; } } cout << ans << endl; return 0; }
E - Bishop 2
拡張ダイクストラ
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) using P = pair<int, tuple<int,int,int>>; const int INF = 1e9+5; vector<pair<int,int>> moves = {{1,1},{1,-1},{-1,-1},{-1,1}}; int dist[1500][1500][5]; int main() { int n,ax,ay,bx,by; cin >> n >> ax >> ay >> bx >> by; ax--; ay--; bx--; by--; vector<string> s(n); REP(i,n) cin >> s[i]; REP(i,1500) REP(j,1500) REP(k,5) dist[i][j][k] = INF; priority_queue<P, vector<P>, greater<P>> q; q.push({0, {ax,ay,0}}); dist[ax][ay][0] = 0; while(q.size()) { auto [d,p] = q.top(); q.pop(); auto [x,y,dir] = p; REP(i,4) { int ndir = i+1; int ndist = d + (dir != ndir); int nx = x + moves[i].first; int ny = y + moves[i].second; if (nx < 0 || n <= nx || ny < 0 || n <= ny) continue; if (s[nx][ny] == '#') continue; if (dist[nx][ny][ndir] <= ndist) continue; dist[nx][ny][ndir] = ndist; q.push({ ndist, {nx,ny,ndir}}); } } int ans = INF; REP(i,5) ans = min(ans, dist[bx][by][i]); cout << (ans == INF ? -1 : ans) << endl; return 0; }