AtCoder Beginner Contest 452

최근 ABC 452 버추얼을 돌았습니다.

업솔빙 겸 A번부터 F번까지의 문제 풀이를 적어 보았습니다.

A. Gothec

$M$이 $9$이하의 홀수이면서 $M = D$를 만족하면 Yes를 출력하면 됩니다.

단, 1월은 예외 처리해야 합니다.

코드 [C++]

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M, D;
    cin >> M >> D;

    if (M == 1) {
        if (D == 7)
            println("Yes");
        else
            println("No");
        return 0;
    }

    if (M % 2 == 1 and M <= 9 and M == D)
        println("Yes");
    else
        println("No");

    return 0;
}

B. Draw Frame

테두리는 #이고 안은 모두 .으로 차있는 $H \times W$짜리 격자를 출력하면 됩니다.

코드 [C++]

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;

    for (int i = 0; i < W; i++)
        cout << '#';
    cout << '\n';
    for (int i = 1; i < H - 1; i++) {
        cout << '#';

        for (int j = 1; j < W - 1; j++)
            cout << '.';

        cout << "#\n";
    }
    for (int i = 0; i < W; i++)
        cout << '#';
    cout << '\n';

    return 0;
}

C. Fishbones

지문이 매우 난해합니다.

$S_j$중 길이가 $N$인 것에 대해서 $i = 1$부터 $N$까지 다음을 모두 만족하는지 확인하는 문제입니다.

$\vert S_k \vert = A_i$를 만족하고 $S_k$의 $B_i$번째 글자가 $S_j$의 $i$번째 글자와 일치하는 $S_k$가 하나 이상 존재한다.

저는 $\vert S_k \vert = A_i$를 만족하는 모든 $S_k$의 $B_i$번째 글자를 std::set에 넣어두는 방식으로 구현했습니다.

코드 [C++]

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

int A[11];
int B[11];

set<char> candidates[11];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
        B[i]--;
    }

    int M;
    cin >> M;
    vector<string> s(M);
    for (int i = 0; i < M; i++)
        cin >> s[i];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (s[j].length() != A[i])
                continue;
            candidates[i].insert(s[j][B[i]]);
        }
    }

    for (int j = 0; j < M; j++) {
        const string& str = s[j];

        if (str.length() != N) {
            cout << "No\n";
            continue;
        }

        bool possible = true;
        for (int i = 0; i < str.length(); i++) {
            if (not candidates[i].contains(str[i])) {
                possible = false;
                break;
            }
        }

        cout << (possible ? "Yes" : "No") << '\n';
    }

    return 0;
}

D. No-Subsequence Substring

우리가 원하는 것은 $T$를 부분 수열로 갖지 않는 $S$의 부분 문자열의 개수입니다.

$T$가 부분 수열로 존재하지 않는 구간을 안다면 부분 문자열의 개수를 쉽게 셀 수 있습니다.

어떤 구간 $[i, j]$에서 $T$가 존재하지 않는 최대 구간은 해당 구간 내에 등장하는 부분 수열 $T$의 시작 인덱스의 최솟값 $s$에 대해 $[s + 1, j]$가 가장 큰 구간이 됩니다.

문자열 $s$의 인덱스 $i$부터 $j$까지의 부분 문자열을 $s[i\dots j]$라 합시다.

$S[0\dots i]$의 부분 수열 중 $T[0\dots j]$를 이루는 것이 있을 때, $S$에서 해당 $T[0\dots j]$의 시작 인덱스를 $dp[i][j]$로 정의합시다.

예를 들어 $S[0\dots i]$가 abcab이고 $T[0\dots j]$가 ba인 경우 $dp[i][j] = 1$입니다.

$S[i] = T[0]$라면 $dp[i][0] = i$입니다.

이외에 $S[i] = T[j]$라면 $dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - 1])$이고, 아니면 $dp[i - 1][j]$입니다.

$i = 0$부터 $i < \vert S \vert$까지 $i$를 1씩 증가시키면서 $T$가 부분 수열로 등장하지 않는 구간 $[l, i]$를 관리합시다. $l = \max(l, dp[i][\vert T \vert - 1])$로 갱신하면 $[l, i]$는 $[0, i]$에서 $T$가 존재하지 않는 최대 구간이 됩니다. $i$로 끝나는 부분 문자열은 이 구간 안에 속하는 것이 유일하므로 해당 개수를 모두 세주면 답이 됩니다.

코드 [C++]

DP 배열은 이전 값만 참조하므로 첫 번째 차원을 없애고 int dp[55]와 같이 선언해도 비슷한 방법으로 문제를 해결할 수 있습니다.

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

using ll = long long;

template <typename T>
bool minimize(T& target, T candidate) {
    return target > candidate ? (target = candidate, true) : false;
}
template <typename T>
bool maximize(T& target, T candidate) {
    return target < candidate ? (target = candidate, true) : false;
}

int dp[202020][55];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string S, T;
    cin >> S >> T;

    int N = S.size();
    int M = T.size();

    fill(&dp[0][0], &dp[N + 5][M], -1);

    if (S[0] == T[0])
        dp[0][0] = 0;

    ll answer = 0;
    int last = dp[0][M - 1] + 1;
    answer += -last + 1;

    for (int i = 1; i < N; i++) {
        dp[i][0] = dp[i - 1][0];
        if (S[i] == T[0])
            dp[i][0] = i;

        for (int j = 1; j < M; j++) {
            dp[i][j] = dp[i - 1][j];

            if (S[i] == T[j])
                maximize(dp[i][j], dp[i - 1][j - 1]);
        }

        maximize(last, dp[i][M - 1] + 1);
        answer += i - last + 1;
    }

    cout << answer;

    return 0;
}

E. You WILL Like Sigma Problem

조화수를 이용한 $O(N\log M)$ 풀이와 약수를 이용한 $O(N\sqrt N)$풀이가 있습니다.

조화수를 이용한 풀이

\[\begin{align} &\sum_{i = 1}^N\sum_{j = 1}^M A_i \cdot B_j \cdot (i \bmod j) \\ =& \sum_{j = 1}^M B_j \sum_{i = 1}^N A_i \cdot (i \bmod j) \\ =& \sum_{j = 1}^M B_j \sum_{i = 1}^N A_i \cdot \left(i - j\left\lfloor\frac{i}{j}\right\rfloor\right) \\ =& \sum_{j = 1}^M B_j \sum_{i = 1}^N \left(iA_i - j\left\lfloor\frac{i}{j}\right\rfloor A_i\right) \end{align}\]

이때 $\sum iA_i$는 $O(N)$에 계산해 둘 수 있습니다.

$\dfrac{i}{j}$값이 일치하는 $i$는 총 $\dfrac{N}{j}$개 입니다.

일치하는 것끼리 누적 합을 이용해서 한번에 처리해 줍시다.

조화수열의 합 $\displaystyle \sum_{j = 1}^M \frac{1}{j}$는 $\log M$에 점근하므로 $O(N\log M)$에 해결할 수 있습니다.

코드 [C++]

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

using ll = long long;

constexpr ll MOD = 998244353;

ll A[505050], B[505050];
ll Asum[505050];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    ll baseSum = 0;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        Asum[i] = (Asum[i - 1] + A[i]) % MOD;

        baseSum += A[i] * i % MOD;
        baseSum %= MOD;
    }

    for (int j = 1; j <= M; j++)
        cin >> B[j];

    ll answer = 0;
    for (int j = 1; j <= M; j++) {
        ll sum = baseSum;
        sum %= MOD;
        for (int i = j; i <= N; i += j) {
            sum -= (Asum[min(N, i + j - 1)] - Asum[i - 1]) % MOD * (i / j) %
                      MOD * j % MOD;
            sum %= MOD;
        }

        answer += sum * B[j] % MOD;
        answer %= MOD;
    }

    cout << (answer + MOD) % MOD;

    return 0;
}

약수를 이용한 풀이

$B_j \cdot (i \bmod j)$의 값을 구한 다음 $A_i$를 곱한 값을 모두 더하면 답이 됩니다.

$i = 1$인 경우 $j = 1$부터 $5$까지 $i \bmod j$를 쓰면 $0, 1, 1, 1, 1$ 입니다.

이제 $i = 2$인 경우를 작성해 봅시다. $\bmod j$를 바로 적용하지 않고 이전에 $i = 1$일때 구한 값에 $1$씩 전부 더해 준 다음 $\bmod j$를 적용해도 결과는 같습니다.

먼저 $1$씩 더해주면 $1, 2, 2, 2, 2$ 입니다.

여기에 $\text{mod}$를 적용하면 $0, 0, 2, 2, 2$ 입니다.

$i \bmod j$의 값이 $0$이 되는 경우는 오직 $j$가 $i$의 약수일 때만 해당합니다.

따라서 $i$를 $1$씩 증가시키면서 행의 합을 잘 관리하면 문제를 해결할 수 있습니다.

이전 행의 합 $S = \displaystyle \sum_{j = 1}^M B_j \cdot ((i - 1) \bmod j)$라 합시다.

먼저 $S$에 $\displaystyle \sum_{j = 1}^N B_j$를 더합니다. 그 다음 $i$의 약수 $j$에 대해 $jB_j$를 $S$에서 빼주면 $\displaystyle \sum_{j = 1}^M B_j \cdot (i \bmod j)$를 구할 수 있습니다.

$i$의 약수는 $\sqrt i$에 구할 수 있으므로 총 시간 복잡도 $O(N\sqrt N)$에 문제를 해결할 수 있습니다.

코드 [C++]

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

using ll = long long;

constexpr ll MOD = 998244353;

ll A[505050], B[505050];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; i++)
        cin >> A[i];

    ll Bsum = 0;
    for (int j = 1; j <= M; j++) {
        cin >> B[j];
        Bsum += B[j];
    }

    ll answer = 0;
    ll rowSum = 0;
    for (ll i = 1; i <= N; i++) {
        rowSum += Bsum;
        rowSum %= MOD;

        for (ll j = 1; j * j <= i; j++) {
            if (i % j != 0)
                continue;
            ll k = i / j;

            if (j <= M) {
                rowSum -= j * B[j] % MOD;
                rowSum %= MOD;
            }
            if (k != j and k <= M) {
                rowSum -= k * B[k] % MOD;
                rowSum %= MOD;
            }
        }

        answer += A[i] * rowSum % MOD;
        answer %= MOD;
    }

    cout << (answer + MOD) % MOD;

    return 0;
}

F. Interval Inversion Count

투 포인터를 이용해서 구간 $[l, h]$의 inversion의 개수가 $K$개 이하가 되도록 관리하면서 $h$를 1씩 증가시켜 줍시다. 이때 $l$은 가능한 작은 값을 유지해야 합니다.

그렇다면 $h$로 끝나는 구간 중 inversion의 개수가 $K$개 이하인 것은 정확히 $h - l + 1$개입니다.

이를 모든 $h$에 대해서 구해주면 전체 구간에서 inversion의 수가 $K$개 이하인 구간의 수를 $O(N\log N)$에 구할 수 있습니다.

같은 방법으로 inversion의 수가 $K - 1$개 이하인 구간의 수를 세어서 빼 주면 답이 됩니다.

코드 [C++]

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

using ll = long long;

struct SegmentTree {
    int n;
    vector<int> t;

    SegmentTree(int n) : n(n), t(n << 1) {}

    void change(int i, int v) {
        for (t[i += n] = v; i > 1; i >>= 1)
            t[i >> 1] = t[i] + t[i ^ 1];
    }

    int getRangeSum(int l, int r) {
        int sum = 0;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1)
                sum += t[l++];
            if (~r & 1)
                sum += t[r--];
        }

        return sum;
    }
};

int P[505050];

ll N, K;

ll getLessOrEqualCnt(ll k) {
    ll ret = 0;
    ll inv = 0;
    int lo = 1, hi = 1;
    SegmentTree seg(N + 1);

    while (hi <= N) {
        inv += seg.getRangeSum(P[hi], N);
        seg.change(P[hi], 1);

        while (lo < hi and inv > k) {
            seg.change(P[lo], 0);
            inv -= seg.getRangeSum(0, P[lo]);
            lo++;
        }

        if (inv <= k)
            ret += hi - lo + 1;

        hi++;
    }

    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        cin >> P[i];
    cout << getLessOrEqualCnt(K) - getLessOrEqualCnt(K - 1);

    return 0;
}