ABC290参加記録

Published on 2023-02-21
Last Modified 2023-09-22

Table Of Contents

ABC290参加した。

お久しぶりです。最近AtCoderコンテストの参加記録をサボりがちなので、流石にエントリを生成します。

今週行われたToyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）は、どうやらオンサイトのコンテストに向けての予選を兼ねているそうで、希望者は好成績を出すことができれば3/18日に行われる決勝イベントに招待されるそうです。なんかすごいですね。

まあ私はそんな実力には程遠いので、いつもどおり参加してきました。

成績とか

軽く今週の戦績を振り返っておきます。今回はA,B,Cの3完でパフォーマンス611, レート変動511→523でした。

成績表レート変動

微増ですがまあ勝ちは勝ちなので()

あと前回の参加記録からしばらく時間が立っているので、いつの間にか入茶しています。(多分色変記事は書きません)

問題と解法

サラッと流します。今までの記事では結構このパートに力を使っていたんですが、比較的難しい問題などは前回の記事のようなスタイルで記事を立てようかなと思っているので、あまり深入りはしないことにします。

A - Contest Result

問題文はこちら

A問題

すぬけくんの解いた問題番号は配点のあとに渡されるので、一旦配点はすべて記録しておく必要があります。*✙最強のデータ構造✙*である配列を用いれば一発です。ただしアクセスするインデックスは一つずれますから気をつけましょう。

C言語的なことを言うとしたら、制約からすぬけくんの総得点はintで大丈夫だし、何なら配点はcharで収まります。

以下ACコードです。

#include <stdio.h>

int main (void) {
    int n, m;
    scanf("%i %i", &n, &m);

    int a[n];
    for (int i = 0; n > i; i++) {
        scanf("%i", &a[i]);
    }

    int ans = 0;
    for (int i = 0; m > i; i++) {
        int tmp;
        scanf("%i", &tmp);
        ans += a[tmp - 1];
    }

    printf("%i", ans);
    return 0;
}

B - Qual B

問題文はこちら

B問題

予選コンテストにちなんだ問題でしょうか？意外とAtCoderの問題って遊び心のあるものが多いような気がします。

さて、予選を突破するための条件は、「決勝希望者であり、希望者のの中で上位K人である」ことなので、単に上からoのついている人をK人分だけoにして、あとはxにするとオーケーです。

以下ACコードです。

#include <stdio.h>

int main (void) {
    int n, k;
    scanf("%i %i", &n, &k);

    char s[n];
    scanf("%s", s);

    int sum = k;
    int count = 0;
    for (int i = 0; n > i; i++) {
        if (sum == 0) {
            break;
        }
        if (s[i] == 'o') {
            printf("o");
            sum--;
        } else {
            printf("x");
        }
        count++;
    }

    for (int i = count; n > count; count++) {
        printf("x");
    }
    return 0;
}

C - Max MEX

問題文はこちらです。

C問題

MEXってなんだよ(正論)

MEXというものをほとんど聞いたことがなかったので「MEX 数学」でgoogle検索してみましたが、あまりヒットしなかったのでそこまで有名なものでもないようです。

さて、このMEX演算は自明な性質として、「数Xを生成したければ、最低でもX個の元が必要である」というものがあります。本問題ではK要素を抜き出してくるという操作を行うため、どんなに頑張ってもMEX(B)の最大値はKになります。

最大値がそれより小さくなるケースは、「0~K-1に至る途中の数のどれかが一つでも欠けている」というものになります。

以上より、数列Aに0~K-1までの数字がすべて含まれているときに答えはKになり、それ以外のときは「欠けている」最小の数字が答えになります。

以下ACコードです。

#include <stdio.h>

int main (void) {
    int n, k;
    scanf("%i %i", &n, &k);

    char check[k + 1];
    for (int i = 0; k + 1 > i; check[i++] = 0) {}
    for (int i = 0; n > i; i++) {
        int tmp;
        scanf("%i", &tmp);
        if (k > tmp) {
            check[tmp] = 1;
        }
    }

    for (int i = 0; k + 1 > i; i++) {
        if (check[i] == 0) {
            printf("%i", i);
            break;
        }
    }

    return 0;
}