AtCoder Beginner Contest 331

Daiwa Securities Co. Ltd. Programming Contest 2023（AtCoder Beginner Contest 331） - AtCoder

A - Tomorrow : AC(2:27)
B - Buy One Carton of Milk : AC(9:26)
C - Sum of Numbers Greater Than Me : AC(17:40)(1ペナ)
D - Tile Pattern : 提出無し
E - Set Meal : 提出無し

A - Tomorrow

ある国の暦では$${1}$$年は$${M}$$ヶ月からなりどの月も$${D}$$日からなる
$${y}$$年$${m}$$月$${d}$$日の翌日は何年何月何日か求める問題

自分の回答

int main(){
  int M, D, y, m, d;
  cin >> M >> D >> y >> m >> d;

  d++;
  if(d > D){
    d = 1;
    m++;
  }
  if(m > M){
    m = 1;
    y++;
  }

  printf("%d %d %d\n", y, m, d);
}

そのまま

公式解説

省略

B - Buy One Carton of Milk

スーパーマーケットで卵のパックが売られている
$${6}$$個入りのパックは$${S}$$円、$${8}$$個入りのパックは$${M}$$円、$${12}$$個入りのパックは$${L}$$円である
どのパックも何個でも買える時卵を$${N}$$個以上買うために必要な最小金額を求める問題

自分の回答

int main(){
  int N, S, M, L;
  cin >> N >> S >> M >> L;

  vector<int> D(N + 13, 10000000);
  D[0] = 0;
  for(int i = 0; i < N; i++){
    D[i + 6] = min(D[i + 6], D[i] + S);
    D[i + 8] = min(D[i + 8], D[i] + M);
    D[i + 12] = min(D[i + 12], D[i] + L);
  }

  int ans = 10000000;
  for(int i = N; i < N + 13; i++){
    ans = min(ans, D[i]);
  }
  printf("%d\n", ans);
}

動的計画法

公式解説

省略

C - Sum of Numbers Greater Than Me

長さ$${N}$$の数列$${A}$$が与えられる
$${1}$$から$${N}$$までの全ての$${i}$$において$${A}$$の要素のうち$${A_{i}}$$より大きな要素の総和を求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int64_t> A(N), SA(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
    SA[i] = A[i];
  }

  sort(SA.begin(), SA.end(), greater<int64_t>());
  map<int, int64_t> ans;
  int64_t sum = 0;
  for(int i = 0; i < N; i++){
    if(!ans.count(SA[i])){
      ans[SA[i]] = sum;
    }
    sum += SA[i];
  }

  for(int i = 0; i < N; i++){
    printf("%ld ",ans[A[i]]);
  }
  printf("\n");
}

Aを降順にソートして新出の要素が来たらそれをキーとしてこれまでの総和をmapに入れる
そして元のAの順番にmapから呼び出して出力

intとint64_tの計算のシステムを勘違いして1ペナ

公式解説

省略

D - Tile Pattern

縦横$${10^9}$$マスのグリッドがある
各マスは白か黒であり、$${N×N}$$マスのパターンの繰り返しである
$${(A,B)}$$を左上隅、$${(C,D)}$$を右下隅とする長方形内に存在する黒マスの個数を求めるクエリが$${Q}$$個与えられるため、全て処理する問題

自分の回答

二次元累積和でごちゃごちゃするので書いてみたけど時間内に終わらなかったしその後に書き上げたのもサンプル2すら合わなかった

公式解説

int N, Q, precalc[1010][1010];

long long g(int H, int W) {
  if (H <= N and W <= N) return precalc[H][W];
  int Hq = H / N, Hr = H % N;
  int Wq = W / N, Wr = W % N;
  long long ret = 0;
  ret += g(N, N) * Hq * Wq;
  ret += g(Hr, N) * Wq;
  ret += g(N, Wr) * Hq;
  ret += g(Hr, Wr);
  return ret;
}

long long f(int A, int B, int C, int D) {
  return g(C, D) - g(A, D) - g(C, B) + g(A, B);
}

int main() {
  cin >> N >> Q;
  vector<string> S(N);
  for (auto& s : S) cin >> s;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      precalc[i][j] += S[i - 1][j - 1] == 'B';
      precalc[i][j] += precalc[i - 1][j];
      precalc[i][j] += precalc[i][j - 1];
      precalc[i][j] -= precalc[i - 1][j - 1];
    }
  }
  while (Q--) {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << f(A, B, C + 1, D + 1) << "\n";
  }
}

https://atcoder.jp/contests/abc331/editorial/7822より

そうか自分は長方形が含まれる部分をNの区切りで大きく取り出して余分な部分を削ってでやったけど長方形を右下として(0,0)からでやればだいぶ計算が簡略化されるか

なるほど

E - Set Meal

食堂で主菜と副菜からなる定食が販売されている
主菜は$${N}$$品あり、価格はそれぞれ$${a_{i}}$$円
副菜は$${M}$$品あり、価格はそれぞれ$${b_{i}}$$円である
定食は主菜と副菜をそれぞれ$${1}$$品づつ組み合わせたものであり、値段はその和である
ただし、$${L}$$個の相異なる組においてはその組み合わせの定食は提供されていない
提供されているもののうち最も値段の高い定食の値段を求める問題

自分の回答

制約的に高い方から見ていけばいいんだろうけどその方法をぱっと思いつかなかったからD問題に戻った

公式解説

    N, M, L = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    g = [set() for _ in range(N)]
    for _ in range(L):
        c, d = map(lambda x: int(x) - 1, input().split())
        g[c].add(d)
    s = sorted([(p, j) for j, p in enumerate(b)], reverse=True)
    ans = 0
    for i in range(N):
        for p, j in s:
            if j not in g[i]:
                ans = max(ans, a[i] + p)
                break
    print(ans)

https://atcoder.jp/contests/abc331/editorial/7853より
Pythonによるもの

そっか各主菜において可能な副菜の中で最も高いものとの組み合わせを比較すればいいのか

なるほど

公式解説その2

int main() {
  int N, M, L;
  cin >> N >> M >> L;
  vector<int> a(N), b(M);
  for (auto& x : a) cin >> x;
  for (auto& x : b) cin >> x;
  set<pair<int, int>> bad;
  for (int i = 0; i < L; i++) {
    int c, d;
    cin >> c >> d;
    bad.emplace(c - 1, d - 1);
  }
  vector<int> ord_b(M);
  for (int i = 0; i < M; i++) ord_b[i] = i;
  sort(begin(ord_b), end(ord_b), [&](int i, int j) { return b[i] > b[j]; });
  vector<int> cur(N);
  priority_queue<pair<int, int>> Q;
  for (int i = 0; i < N; i++) Q.emplace(a[i] + b[ord_b[cur[i]]], i);
  while (true) {
    auto [cost, i] = Q.top();
    int j = cur[i];
    Q.pop();
    if (bad.count({i, ord_b[j]}) == 0) {
      cout << cost << "\n";
      break;
    }
    cur[i]++;
    if (cur[i] != M) Q.emplace(a[i] + b[ord_b[cur[i]]], i);
  }
}

https://atcoder.jp/contests/abc331/editorial/7821より

priority_queueにまず各主菜の値段と副菜で最も高いものの値段を足したものを主菜のインデックスとのpairで入れる
一番価格の高いものを取り出してそれが提供されてるペアならそれを出力して終わり、そうでないなら1つ安い副菜との和をpriority_queueに入れる
これを繰り返せば価格の高い順に見ていける

なるほど