AtCoder Beginner Contest 432 【ABC 432】 A ~ C, E

AtCoder Beginner Contest 432 に参加しました。
A ~ C, E の4完で、
パフォーマンス 1355
レーティング 1094 → 1123 (+29)　となりました。

A - Permute to Maximize

$A, B, C$ を $A \geq B \geq C$ となるようにsortすればよいです。

cpp

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

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if (B < C) swap(B, C);
    if (A < B) swap(A, B);
    if (B < C) swap(B, C);
    cout << A << B << C;
    cout << endl;
}

B - Permute to Minimize

$X$ をsortします。$X_0 = 0$ のとき、 $X_i \neq 0$ である最小の $i$ について、
$X_0, X_i$ を交換すればよいです。

cpp

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

int main() {
    string X;
    cin >> X;
    sort(X.begin(), X.end());
    if (X[0] == '0') {
        for (int i = 1; i < X.size(); i++) {
            if (X[i] != '0') {
                swap(X[0], X[i]);
                break;
            }
        }
    }

    cout << X << endl;
}

C - Candy Tribulation

$N$ 人の子供それぞれに配る飴の総重量 を $G$ とします。
また、子供 $i$ が持つ小さな飴、大きな飴の個数をそれぞれ $s_i, t_i$ とします。
このとき、

\left\{
\begin{aligned}
&s_i + t_i = a_i \\
&s_iX + t_iY = G
\end{aligned}
\right.

$$ \therefore t_i = \frac{G - a_iX}{Y - X} \tag{1}$$
となります。$t_i$ は $G$ が最大の時、最大値をとります。
よって、$G$ を最大化させればよいです。
(1) より、 $G \equiv a_iX \, \bmod (Y - X)$ が必要です。
$1 \leq i \leq N$ について、 $a_iX \, \bmod (Y - X)$ が等しいとき、それを $P$ とします。
よって、 $G$ は整数 $k$ を用いて、 $G = k(Y - X) + P$ と表すことができます。
$$\displaystyle \max_{1 \leq i \leq N} A_i X\leq G
\leq \displaystyle\min_{1 \leq i \leq N} A_iY$$
これを考慮すれば、 $G$ の最大値が求まるので、$O(N)$ でこの問題を解くことができます。

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(), (v).end()

int main() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    ll P = A[0] * X % (Y - X);
    for (int i = 1; i < N; i++) {
        if (A[i] * X % (Y - X) != P) {
            cout << -1 << endl;
            return 0;
        }
    }

    ll MIN = *max_element(all(A)) * X;
    ll MAX = *min_element(all(A)) * Y;
    ll k = (MAX - P) / (Y - X);
    ll G = k * (Y - X) + P;
    if (MIN > G) {
        cout << -1 << endl;
        return 0;
    }
    
    ll ans = 0;
    for (int i = 0; i < N; i++) ans += (G - A[i] * X) / (Y - X);
    cout << ans << endl;
}

E - Clamp

クエリ2について考えます。

• $l > r$ のとき、
  $\max(l, \min(r, A_i)) = l$
• $l \leq r$ のとき、
  $A_i < l \Rightarrow \max(l, \min(r, A_i)) = \max(l, A_i) = l$
  $l \leq A_i \leq r \Rightarrow \max(l, \min(r, A_i)) = \max(l, A_i) = A_i$
  $r < A_i \Rightarrow \max(l, \min(r, A_i)) = \max(l, r) = r$

よって次のようなクエリに対応できれば良いです。
1 x y $A_x = y$ に変更する。
2 l r $l \leq A_i < r$ を満たす 整数 $i$ の個数を出力する
3 l r $l \leq A_i < r$ を満たす $A_i$ の総和を出力する
$A_i$ の最大値を $M$ とすると、
これらはFenwick Treeを用いると $O(logM)$ で処理できるので、
$O(N + QlogM)$ でこの問題を解くことができます。

cpp

#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
using ll = long long;

int main() {
    ll N, Q;
    cin >> N >> Q;
    const int M = 5e5 + 1;
    atcoder::fenwick_tree<ll> sum(M), cnt(M);
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum.add(A[i], A[i]);
        cnt.add(A[i], 1);
    }

    while (Q--) {
        int type;
        cin >> type;
        
        if (type == 1) {
            ll x, y;
            cin >> x >> y;
            x--;
            sum.add(A[x], -A[x]);
            cnt.add(A[x], -1);
            A[x] = y;
            sum.add(A[x], A[x]);
            cnt.add(A[x], 1);
        }

        if (type == 2) {
            ll l, r;
            cin >> l >> r;
            if (l > r) {
                cout << l * N << endl;
            }

            else {
                cout << l * cnt.sum(0, l) + sum.sum(l, r + 1) + r * cnt.sum(r + 1, M) << endl;
            }
        }
    }
}