ABC318 自分の解法（A〜C）

ABC318の自分の解法です。残念ながらAtCoderのコンテストには時間の都合上、参加できないのですが、後で解いたものを少しでも残せたらと思います。

A問題

まずはA問題から。
A問題ははじめに入力した$M$が$N$を超えないまで$P$を足せば答えが出てきます。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long

int main() {    
  int n, m, p;
  cin >> n >> m >> p;
  int ans = 0;
  while(m <= n) {
    ans++;
    m += p;
  }
  cout << ans << endl;
  return 0;
}

B問題

B問題です。
制約は$0\leq A_i < B_i \leq100$、$0\leq C_i < D_i \leq100$なので、$100 × 100$の$bool$型の配列で、$N$回の試行を実装すればいいです。
具体的には、$bool$型の配列を$vec$として$vec[A_i][B_i]$から$vec[C_i][D_i]$を$true$にして、最後に配列$vec$の中にある$true$の数を数えると、その数が答えになっています。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long

int main() {
  int n;
  cin >> n;
  vector<vector<bool>> vec(100, vector<bool> (100, false));
  rep(i, n) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    for (int x = a; x < b; x++) {
      for (int y = c; y < d; y++) {
        vec[x][y] = true;
      }
    }
  }
  int ans = 0;
  rep(i, 100) {
    rep(j, 100) {
      if(vec[i][j]) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

C問題

C問題です。
累積和を考えます。
まず、$1$日周遊パスのセットを購入する数を$k$セット($kD$枚)で固定した時に$N$日間の旅行の代金を最小化することを考えます。（ここの文章はAtCoderの公式解説からです。ごめんなさい。同じような解き方なので。）そして、配列$F$を昇順にソートします。$S_j=\sum_{i=1}^{j}F_i$とします。そして、$kP+\sum_{i=1}^{N-kD}F_i$、つまり$kP+S_{n-kD}$を求めれば良くなります。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long

int main() {
  int n, d, p;
  cin >> n >> d >> p;
  vector<int> f(n);
  rep(i, n) cin >> f[i];
  sort(f.begin(), f.end());
  vector<ll> s(n + 1);
  rep(i, n) s[i + 1] = s[i] + f[i];
  ll ans = 1LL << 60;
  rep(k, 1e9) {
    int r = max(0, n - k * d);
    ll now = s[r] + (ll)p * k;
    ans = min(ans, now);
    if (r == 0) break;
  }
  cout << ans << endl;
  return 0;
}