AtCoder Beginner Contest 433 【ABC 433】 A ~ D

A - Happy Birthday! 4

$T$ 年後の高橋君、青木君の年齢はそれぞれ $X + T, Y + T$となるので、

\begin{aligned}
X + T &= Z(Y + T) \\
\therefore\quad
T &= \frac{X - ZY}{Z - 1}
\end{aligned}
\

となります。

cpp

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

int main() {
    int X, Y, Z;
    cin >> X >> Y >> Z;
    cout << (X >= Z * Y && (X - Z * Y) % (Z - 1) == 0 ? "Yes" : "No") << endl;
}

B - Nearest Taller

$0 \leq i < N$ について、$ 0 \leq j < i \, \land\, A_j > A_i $ を満たす $j$ を求めればよいです。

cpp

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        int ans = -2;
        for (int j = 0; j < i; j++) if (A[j] > A[i]) ans = j;
        cout << ans + 1 << endl;
    }
}

C - 1122 Substring 2

文字列 $S$ をランレングス圧縮したとき、
$n$ 個の組 $(L_1, R_1), (L_2, R_2), ... (L_n, R_n)$ に分けられたとします。
答えは $$\sum_{L_{i + 1} = L_i + 1} \min(R_i, R_{i + 1})$$
です。

cpp

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

vector<pair<char, int>> RLE(string &a) {
    vector<pair<char, int>> ret;
    int cnt = 1;

    for (int i = 0; i < a.size() - 1; i++) {
        if (a[i] != a[i + 1]) {
            ret.push_back(make_pair(a[i], cnt));
            cnt = 1;
        }

        else cnt++;
    }

    ret.push_back(make_pair(a.back(), cnt));

    return ret;
}

int main() {
    string S;
    cin >> S;
    auto R = RLE(S);
    long long ans = 0;
    for (int i = 0; i < R.size() - 1; i++) {
        auto [c1, d1] = R[i];
        auto [c2, d2] = R[i + 1];
        if (c2 == c1 + 1) ans += min(d1, d2);
    }

    cout << ans << endl;
}

D - 183183

正整数 $x$ の桁数を $L(x)$ とします。
正整数 $a, b$ について、$f(a, b) = a \cdot 10^{L(b)} + b$ となります。

\begin{aligned}
f(A_i, A_j) &\equiv 0 \, \pmod{M} \\
A_i \cdot 10^{L(A_j)} + A_j &\equiv 0 \, \pmod{M} \\
A_i \cdot 10^{L(A_j)} &\equiv -A_j \, \pmod{M}
\end{aligned}

となるので、各 $A_i$ について、 std::mapなどに $(A_i \cdot 10^d \bmod{M}, d)$ の組を追加すればよいです。

cpp

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

int main() {
    ll N, M;
    cin >> N >> M;
    modint::set_mod(M);
    using mint = modint;
    vector<ll> A(N);
    map<pair<ll, ll>, ll> mp;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        for (ll d = 1; d <= 10; d++) mp[{(mint(A[i]) * mint(10).pow(d)).val(), d}]++;
    }

    ll ans = 0;
    for (int j = 0; j < N; j++) {
        ll d = to_string(A[j]).size();
        ans += mp[{mint(M - A[j]).val(), d}];
    }

    cout << ans << endl;
}