SNCTプロコン春合宿コン'20 解説

Twitterでtesterの方による解説ツイートがある1のですが、もしかしたらTwitterをやっていない人がいるかもしれないので2、一応ここに解説を書いておきます。
コンテストへのリンク
https://www.hackerrank.com/contests/snct-spring20/challenges
提出したコードは下のほうにまとめてあります。
目次

1. εrr-r

A 円で A円より高い物を買うことはできません。
したがって、 A \lt Bなら"Error"を、そうでないなら A-Bを出力すればいいです。

2. αειου

母音は a, i, u, e, oの5つです3 前から文字列を見ていって、今見ている文字が母音ならカウンターに+1するなどして数え上げればいいです。
C++ならrange-based forを使うと楽に書けると思います。

3. ασδα

同じ品種のりんごは食べられないので、幸福度の最大値は各品種のりんごの美味しさの最大値の総和です。
したがって、品種 A_iのりんごの美味しさの最大値を配列かmapかなにかで持っておけばいいです。
美味しさが負のときは食べないほうがいいので握りつぶしてかまいません。

4. Ϟϟ

九九の票を睨むと Xは2つの整数 p,qを用いて X = pqと表せることが分かります。
これを変形すると p = \frac{X}{q}となるので pが整数となるような qを探せばいいです。 このような qは Xの約数に限られるので、 qを 1から \sqrt{X}まで動かして Xを割り切れるか試していけば,すべての (p, q)の組を列挙することができます。

5. Ξητ

まず、明らかに小さい数から取っていったほうがいいので Xの列をソートします。 また、 Aより大きい数しか選べないため、 Aが2つ以上あっても Aが2回以上選ばれることはありません。
したがって、重複を取り除いても答えは変わらないので重複を取り除いておきます。
ここで、 1に続く数が 13と 1333しか無い場合、大きい方である 1333を取ったほうが答えは大きくなります。したがって、
dp[i][b] := i番目の数までみて、最後に取った数の末尾の数字が bであったときの得点の最大値
とおけば、dpで答えが求められます。

6. ΣΜμ

いくつか例をつくってみると、一番右側の部分列をどれだけ伸ばしても最小値の最大値は大きくならず、反対に真ん中の部分列を短くすると最大値は小さくなる場合があることが分かります。 したがって、一番右側の部分列は区間[N, N]で固定するのが最適です。あとは最適な aの位置を探索すればよく、これは A_1から A_Nへの累積和と A_{N-1}から A_1への累積maxを持っておけば O(N)で求めることができます。

Submissions

1. εrr-r

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

int main(){
    int A, B;
    cin >> A >> B;
    if(A < B) cout << "Error" << endl;
    else cout << A - B  << endl;
}

2. αειου

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

int main(){
    int N;
    string S;
    cin >> N >> S;

    const string vowels = "aiueo";
    int counter = 0;
    for(auto& c : S){
        for(auto& vowel : vowels){
            if(c == vowel)  counter++;
        }
    }

    cout << counter << endl;
}

3. ασδα

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

int main(){
    int N;
    cin >> N;

    valarray<i64> max_delicious(0l, 100010);
    for(int i = 0; i < N; i++){
        i64 A, B; 
        cin >> A >> B;
        max_delicious[A] = max(max_delicious[A], B);
    }

    cout << max_delicious.sum() << endl;
}

4. Ϟϟ

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

int main(){
    i64 Q, X;
    cin >> Q >> X;

    int counter = 0;
    for(i64 q = 1; q*q <= X; q++){
        if((X % q) != 0) continue;
        i64 p = X / q;
        if(p <= Q && q <= Q) {
            if(q*q == X) counter += 1;
            else counter += 2;
        }
    }

    cout << counter << endl;
}

5. Ξητ

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

int front(i64& x){
    i64 d = 1;
    while(d * 10 <= x) d *= 10;
    return x / d;
}

int back(i64& x){
    return x % 10;
}

int main(){
    i64 N;
    cin >> N;
    vector<i64> X(N);
    for(int i = 0; i < N; i++) cin >> X[i];

    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());

    valarray<i64> dp(0l, 10);
    for(int i = 0; i < X.size(); i++){
        int b = back(X[i]);
        int f = front(X[i]);
        dp[b] = max(dp[b], dp[f] + X[i]);
    }

    cout << dp.max() << endl;
}

6. ΣΜμ

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

int main(){
    int N;
    cin >> N;
    vector<i64> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    vector<i64> sum(A), MAX(A);
    for(int i = 0; i < N-1; i++) sum[i+1] += sum[i];
    for(int i = N-3; i >= 0; i--) MAX[i] = max(MAX[i], MAX[i+1]);

    i64 ans = 0;
    for(int i = 0; i < N-2; i++){
        ans = max(ans, sum[i] + MAX[i+1] + A[N-1]);
    }

    cout << ans << endl;
}

途中で下書きが吹き飛んでしまってキレながら書いたので雑なところがあるかもしれませんが、ゆるしてください。

  1. https://twitter.com/ecto0310/status/1237007779597938689?s=20↩

  2. いないだろ↩

  3. yは母音！(素振り) ちゃんと問題文で定義してくれ↩