ARC075

C問題


C: Bugged - AtCoder Regular Contest 075 | AtCoder


10の倍数にならない状態での最大の値を求められているので、10の倍数で無い最小の値を確保しておいて全てを足した際に10の倍数であれば確保してある値を引くだけで答えが出る


#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, a, ans = 0, min = 101;
  cin >> n;

  for(int i = 0; i < n; i++) {
    cin >> a;
    ans += a;
    if(min > a && a % 10 != 0) min = a;
  }

  cout << (ans % 10 == 0 ? min > 100 ? 0 : ans - min : ans) << endl;
}

D問題


D: Widespread - AtCoder Regular Contest 075 | AtCoder


全探索だと枝刈りを頑張っても無理だったので爆発回数 A 回で全滅させられる場合、 A ≦ B の条件を満たした B は全滅させることが可能な爆発回数という性質を利用し、二分探索で計算量を削減する

#include <bits/stdc++.h>
using namespace std;

ll n, a, b, ans, h[100001];

bool taosu(ll k) {
  ll cost = 0;
  rep(i, 0, n) {
    ll z = h[i] - b * k;
    if(z > 0) {
      cost += ceil((double)z / (double)(a - b));
      if(cost > k) return false;
    }
  }
  return true;
}

int main() {
  cin >> n >> a >> b;
  rep(i, 0, n) cin >> h[i];
  ll left = 0, right = 1000000000, mid, ans;
  while(left <= right) {
    mid = (left + right) / 2;
    taosu(mid) ? ans = mid, right = --mid : left = ++mid;
  }
  cout << ans << endl;
}