AtCoder Beginner Contest 321

SuntoryProgrammingContest2023（AtCoder Beginner Contest 321） - AtCoder

A - 321-like Checker : AC(2:32)
B - Cutoff : AC(8:16)
C - 321-like Searcher : AC(93:04)
D - Set Menu : AC(74:04)

A - 321-like Checker

正整数$${x}$$の各桁が上から狭義単調減少であるとき、その整数を「321-like Number」とする
正整数$${N}$$が与えられ、それが321-like Numberであるか判定する問題

自分の回答

int main(){
  string N;
  cin >> N;

  for(int i = 1; i < N.size(); i++){
    if(N[i - 1] <= N[i]){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}

そのまま
ただ数字で受け取ると桁で見るのがめんどくさいから文字列で受け取ってcharで比較

公式解説

省略

B - Cutoff

$${N}$$ラウンドからなる試験があり、各ラウンドにおけるスコアは$${0}$$から$${100}$$の整数である。最終スコアは全ラウンドのスコアから最低スコアと最高スコアを除いた総和である
現在$${N-1}$$ラウンドが終了し、それまでの各ラウンドのスコアは$${A_{i}}$$である
最終スコアを$${X}$$以上にするために$${N}$$ラウンド目に取るべき最少スコアを求める問題
ただし、最終スコアを$${X}$$以上にすることができない場合「-1」と出力する

自分の回答

int main(){
  int N, X;
  cin >> N >> X;
  int sum = 0, mi = 200, ma = 0;
  for(int i = 0;i < N - 1; i++){
    int a;
    cin >> a;
    sum += a;
    mi = min(mi, a);
    ma = max(ma, a);
  }

  for(int i = 0; i <= 100; i++){
    int nsum = sum + i, nmi = min(mi, i), nma = max(ma, i);
    if(nsum - nmi - nma >= X){
      printf("%d\n", i);
      return 0;
    }
  }
  printf("-1\n");
}

0点からXになるか見て行って終わり
もっと計算量少ない方法はあるけどこれが書くのが早い

公式解説

省略

C - 321-like Searcher

A問題と同じで321-like Numberを定義する
$${K}$$番目に小さい321-like Numberを求める問題

自分の回答

int main(){
  int K;
  cin >> K;
  vector<int> N(10, 0);

  int k = 0, dg = 0;
  while(k != K){
    N[0]++;
    int j = 0;
    while(N[j] == 10){
      N[j] = 0;
      N[j + 1]++;
      j++;
      dg = max(dg, j);
    }
    for(int i = 1; i <= dg; i++){
      if(N[i - 1] >= N[i]){
        N[i] = N[i - 1] + 1;
        N[i - 1] = i - 1;
      }
      if(N[i] >= 10){
        N[i + 1]++;
        N[i] = N[i - 1] + 1;
        dg = max(i + 1, dg);
      }
    }
    k++;
  }

  for(int i = dg; i >= 0; i--){
    printf("%d", N[i]);
  }
  printf("\n");
}

321-like Numberの最大は9876543210で1から順番に見ていったらダメだけど321-like Numberだけなら総当たりできるからそれを作るものを作る
ただその部分もっときれいにできるよなぁ…

公式解説

import java.util.*
fun main() {
  Scanner(System.`in`).use { sc ->
    val K = sc.nextInt() - 1
    val ans = MutableList(9) { ('1' + it).toString()} // 最初は"1", "2", ..., "9"
    repeat(K) {for (v in '0' until ans[it].last()) ans.add(ans[it] + v)} // 与えられた数の末尾に、条件を満たす数を結合する
    println(ans[K]) // ansは昇順に値が入っている
  }
}

https://atcoder.jp/contests/abc321/editorial/7275より
(これ言語なんだろ…Kotlinってやつっぽいけど合ってるかな…)

1,2,3,4,5,6,7,8,9からスタートしてその後ろに1の位の数-1から0までをくっつけていくってのを繰り返せば昇順に321-like Numberができるって感じか

なるほど

D - Set Menu

食堂で$${N}$$種類の主菜と$${M}$$種類の副菜が提供されていて、主菜はそれぞれ$${A_{i}}$$円、副菜はそれぞれ$${B_{i}}$$円である
主菜$${1}$$品と副菜$${1}$$品からなる定食を作るとき、その値段は主菜の値段と副菜の値段の和か$${P}$$のうち小さい方とする
主菜と副菜の組み合わせは$${NM}$$通りあるが、それらすべてに対する定食の値段の和を求める問題

自分の回答

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

  sort(B.begin(), B.end());
  vector<int64_t> c_sumB(M, 0);
  c_sumB[0] = B[0];
  for(int i = 1; i < M; i++){
    c_sumB[i] = c_sumB[i - 1] + B[i];
  }

  int64_t ans = 0;
  for(int i = 0; i < N; i++){
    auto l = lower_bound(B.begin(), B.end(), P - A[i]);
    int li = l - B.begin();
    if(li != 0){
      ans += A[i] * li + c_sumB[li - 1];
    }
    ans += P * (M - li);
  }

  printf("%ld\n", ans);
}

副菜を昇順にソートして、主菜を一つ選んだ時に組み合わせでP以上となる副菜の位置liをlower_boundで探し、それより下の値段の和は主菜の値段×li+そこまでの副菜の和となるから副菜の和を累積和で取得、それ以上はP*(M-li)でそれぞれansに足すことを主菜全てでしたのが答え

公式解説

省略