AtCoder Beginner Contest 281

A - Count Down

Simple output problem

let N = Int(readLine()!)!
for i in 0...N { print(N-i) }

B - Sandwich Number

Print Yes if the following conditions hold, otherwise print No.

The first character is an uppercase English letter
The second to seventh characters are a number between 100000 and 999999
The eighth character is an uppercase English letter

let S: [Character] = Array(readLine()!)

if S.count != 8 {
    print("No")
} else if !S[0].isUppercase {
    print("No")
} else if !((100000...999999) ~= Int(String(S[1...6]))!) {
    print("No")
} else if !S[7].isUppercase {
    print("No")
} else {
    print("Yes")
}

C - Circular Playlist

T can be up to 10^18, so if you follow the music from the start, you'll definitely get a time limit exceeded.
N can be up to a hundred thousand, so it's a problem you have to solve in O(N) time.
In other words, you have to finish it with about one pass from 1 to N.

If you store the sum of all the music and keep the remainder of T divided by it, you can get rid of the full-playback cycles.
(When I saw that if the remainder of dividing by T is 0 you have to play the first song, I was really grateful to the problem setter.)

Anyway, now the song is guaranteed to end within one cycle,
so you just go through the music in order, find the song where playback gets cut off, and print it.

let ip = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (N, T) = (ip[0], ip[1])
let A = [0] + readLine()!.split{$0==" "}.map{Int(String($0))!}
let sum = A.reduce(0, +)
var remain = T % sum

for i in 1...N {
    if remain - A[i] >= 0 {
        remain -= A[i]
    } else {
        print(i, remain, separator: " ")
        break
    }
}

D - Max Multiple

Up to C it was obviously Silver level, so I got careless thinking Beginner must be easy^^ and couldn't solve it.
I didn't expect the difficulty to suddenly blow up. It was a DP problem that's at least Gold 4.

f(i, j, k): define it as the maximum sum, among the elements from 0 to a[i], of choosing j elements whose sum has remainder k.
Where I got stuck was that, to find the recurrence for index i,
I was going through DOG-level pain trying to find the x that makes (x + a[i]) % D = 0.
I was thinking, did I study too little math..., but then I realized that when defining the recurrence,

instead of defining it like previous + ☆ = current,
defining it like current + ♬ = future solves it easily.

So the recurrence can be defined as follows.

f\left(i+1,\ j+1,\ \left(k+a\left[i+1\right]\right)\%D\right)\ =\ \max _{ }^{ }\left(f\left(i,j,k\right)+a\left[i+1\right],\ 자신\right)

f\left(i+1,\ j,\ k\right)\ =\ \max _{ }^{ }\left(f\left(i,j,k\right),\ 자신\right)

('자신' means the left-hand side. I'm too lazy to write it again.)

Just solve that recurrence.

let ip = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (N, K, D) = (ip[0], ip[1], ip[2])
let a = [0]+readLine()!.split{$0==" "}.map{Int(String($0))!}
var dp = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: -1, count: D), count: K+1), count: N+1)

dp[0][0][0] = 0;

for i in 0..<N {
    for j in 0...K {
        for k in 0..<D {
            if dp[i][j][k] == -1 { continue }
            
            dp[i+1][j][k] = max(dp[i][j][k], dp[i+1][j][k])
            
            if j == K { continue }
            dp[i+1][j+1][(k+a[i+1])%D] = max(dp[i][j][k]+a[i+1], dp[i+1][j+1][(k+a[i+1])%D])
        }
    }
}

print(dp[N][K][0])

E - Least Elements

It was a problem you could solve by managing 2 multisets.
Make multisets L and R,
and initialize L with the first K of the M elements and R with the remaining M-K.

Now while sweeping, you remove the A[i-M]th element from L or R,
and you have to insert the A[i]th element.

The thing to watch out for is when K=1, M=1,
L will have 1 element and R will have 0 elements.
If you do the removal first,
it gets removed from L, and when you try to put R's first element in to keep L at 1, it's a runtime error.

So do the insertion before the removal.
Insert into L first, then put L's last element into R. Then
L has K elements, M has M-K+1, and the counts are always at least 1.

Now do the removal from L or R and make L have K elements and R have M-K elements.

( + In a multiset, set.erase(value) removes every value,
and set.erase(set.find(value)) removes only one, apparently... I went through hell because of this yesterday ㅠ
Lesson learned. )


#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

const int MAX = 200005;
int N, M, K, A[MAX];
multiset<int> L;
multiset<int> R;
ll ans;

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

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

    for (int i=1; i<=M; i++) {
        L.insert(A[i]), ans += A[i];
        if (L.size() > K) {
            R.insert(*L.rbegin());
            ans -= *L.rbegin();
            L.erase(--L.end());
        }
    }

    cout << ans << ' ';
    for (int i=M+1; i<=N; i++) {
        int w = A[i-M];
        L.insert(A[i]), ans += A[i];

        ans -= *L.rbegin();
        R.insert(*L.rbegin());
        L.erase(--L.end());

        if (w <= *L.rbegin()) {
            ans -= w;
            L.erase(L.find(w));
            ans += *R.begin();
            L.insert(*R.begin());
            R.erase(R.begin());
        } else {
            R.erase(R.find(w));
        }

        cout << ans << ' ';
    }

    return 0;
}

I tried to stick with swift if I could, but it just wasn't working so I used C++.

Comments