AtCoder abc246 参加メモ

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;
}