AtCoder Beginner Contest 334

UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334) - AtCoder

結果

A - Christmas Present : AC(1:56)
B - Christmas Trees : WA
C - Socks 2 : 提出無し
D - Reindeer and Sleigh : AC(63:38)

A - Christmas Present

高橋君にバットかグローブの値段が高い方をプレゼントする
バットが$${B}$$円、グローブが$${G}$$円であるときどちらをプレゼントするか判定する問題

自分の回答

int main(){
  int B, G;
  cin >> B >> G;

  printf(B > G ? "Bat\n" : "Glove\n");
}

そのまま

公式解説

省略

B - Christmas Trees

東西に無限に伸びる道路があり、座標$${A}$$を基点として$${M}$$mおきにクリスマスツリーを立てる
高橋君と青木君がそれぞれ座標$${L,R}$$に立っている、高橋君と青木君の間(立っている位置も含める)にツリーが何本あるか求める問題

自分の回答

(R-L)/Mで間にある本数を求めていろいろ補正を試してみたけどどうにも全部合うことがなかった

公式解説

using ll = long long;

ll floor(ll x, ll m) {
    ll r = (x % m + m) % m;
    return (x - r) / m;
}

int main() {
    ll a, m, l, r;
    cin >> a >> m >> l >> r;
    l -= a, r -= a;
    cout << floor(r, m) - floor(l - 1, m) << endl;
}

https://atcoder.jp/contests/abc334/editorial/8984より

L以上とR以下の最も近いツリーが何番目かを求めてそれを引けばいいのか

なるほど

C - Socks 2

$${N}$$組の靴下があり、$${i}$$番目の靴下の色は$${i}$$である
それぞれ色$${A_{1},A_{2},…,A_{K}}$$の靴下の片方を無くしてしまったため残っている靴下で可能な限りペアを作るが、色$${i}$$と$${j}$$のペアであるときその奇妙さを$${|i-j|}$$とする
奇妙さの総和を最小でいくつにできるか求める問題

自分の回答

靴下が2足残っているものはそのまま組んで問題なく、そうなると1足のペアで最小を求める問題になって、基本的には隣接するので組むべき
後は1足のが奇数個あった時どれを残すかになって、左から組んでいったのと右から組んでいったので累積和してなんやかんやすれば良さそうだなとは思ったけどうまく書けなかった

公式解説

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(k);
    for (int &i: a) cin >> i;
    vector<int> pre(k + 1), suf(k + 1);
    for (int i = 1; i <= k; i++) {
        pre[i] = pre[i - 1];
        if (i % 2 == 0) pre[i] += a[i - 1] - a[i - 2];
    }
    for (int i = k - 1; i >= 0; i--) {
        suf[i] = suf[i + 1];
        if ((k - i) % 2 == 0) suf[i] += a[i + 1] - a[i];
    }
    int ans = 1e9;
    for (int i = 0; i <= k; i += 2) {
        ans = min(ans, pre[i] + suf[i]);
    }
    cout << ans << endl;
}

https://atcoder.jp/contests/abc334/editorial/8983より

やっぱり考え方は合ってたか

これ書けなかったのは悔しいな

D - Reindeer and Sleigh

$${N}$$台のソリがあり、それぞれ引くには$${R_{i}}$$匹のトナカイは必要である
$${X}$$匹のトナカイがいる時最大で何台のソリを引けるか求めるクエリが$${Q}$$個与えられるため全て処理する問題

自分の回答

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

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

  for(int i = 0; i < Q; i++){
    int64_t x;
    cin >> x;
    auto ai = upper_bound(Rsum.begin(), Rsum.end(), x);
    printf("%d\n", ai - Rsum.begin() - 1);
  }
}

必要数が少ない方から埋めていけばいいため、ソートしてi番目まで引くためには何匹必要かを累積和
後はそれを二分探索してそのインデックスが答え

公式解説

省略