InTheDayDream

ABC283参加記録！

Published on 2022-12-26
Last Modified 2023-09-22

Table Of Contents

ABC283参加してきた！

こんにちは。最近近所のスーパーが扱っている冷凍パスタのメーカーが変わって一瞬焦ったInです。(でもちゃんとおいしかったのでセーフ)

冷凍パスタ

アドベントカレンダーを執筆していた影響で遅れてしまいましたが，今週もちゃんとABCに参加してきましたので，その参加記録を生やしておきます。

今週の成績発表のコーナー

まずは今週の成績です。前回爆死したのが記憶に新しいですが，今回はこんな感じでした。

提出結果

大体16分でCまで通して，そのあとD問題に敗北しました。全体で3完です。

コラ画像
このためだけに10分くらいで作った雑コラ。

なお，今回のコンテストによるレート変動は以下の通りでした。

レート変動

茶色まで折り返し地点といった感じでなかなかいいんじゃないでしょうか？今回は結構早解きに成功したので，3完ですがそこそこの順位になりました。ペナルティも食らってないし

各問題と解法

いつも通り自分が解いた問題の説明を載せていきたいと思います。まずはA問題です。

A - Power

問題文は以下の通りでした。

A問題

AのB乗を出力するだけのシンプルな問題です。 ご存じの方も多いかもしれませんが一応書いておきますと，ABというのはBが自然数の場合は素朴に定義されており， AB=A×A×…×A (AがB個掛け算されている) というものです。

この問題の制約下では，ABの最小値はA=B=1の時1で，最大値はA=B=9の時387420489となります。これはintの範囲内に収まります。また，計算回数も9回程度に収まることが分かるので，定義通り計算して出力したらOKであることが分かります。以下にAC通ったコードを載せます。

#include <stdio.h>

int main(void) {
    int a, b;
    scanf("%i %i", &a, &b);
    int ans = 1;

    for(int i = 0; b > i; i++) {
        ans *= a;
    }

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

このA問題はここ最近の中では簡単な問題だと思います。というかほとんどの言語が組み込みで冪乗計算の機能を備えているので，簡単に解けた人が多いんじゃないかと思います。

B - First Query Problem

問題文は以下の通りでした。

B問題

この問題はAtCoderによくあるタイプのクエリを処理する奴ですね。この手の問題は工夫したら真面目にクエリを処理しなくてもいい場合があります。したがって，まずは条件をよく見ることが大切です。

問題文を見ると，クエリの件数の制約や，行う必要のある操作の制約がかなり緩いことが分かります。まず第一引数が1であるようなクエリは，受け取った数列を配列などに保持するだけでO(1)で行うことができます。また，第一引数が2であるようなクエリに対しても同様です。一つしか値を操作しないので軽いですね。操作回数も105が上限となっており，愚直に処理しても十分間に合いそうです。

もしかしたら何らかの最適化があるのかもしれませんが，私は書いてある通りに実装して通りました。以下コードです。

#include <stdio.h>

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

    int a[n];

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

    int temp; //クエリ種類
    int k; // インデックス
    int num; // すり替え数字
    for(int i = 0; q > i; i++) {
        scanf("%i", &temp);
        scanf("%i", &k);

        if(temp == 1) {
            scanf("%i", &num);
            a[k - 1] = num;
        } else {
            printf("%i\n", a[k - 1]);
        }
    }

    return 0;
}

クエリの種類によって与えられる引数の数が変わるのに注意です。私の実装ではシンプルにif文で分岐してあります。あと完全に余談なのですが，うえのコードでは実行時で確定していない変数を用いて配列を宣言するというC言語(C99以降?)の機能を使っているのですが，便利だけど罪悪感があります(笑)

C - Cash Register

問題文は以下の通りでした。

C問題

与えられた数字をレジの機械で打ち込むときに必要なストローク数を調べるという問題でした。ほとんどの人がまずは制約に目が行くのではないでしょうか？制約は整数が10100000らしいです。デカ過ぎんだろ...

テニスの王子様コラ画像
デカさのイメージ図

ということで、明らかに「非常に簡単な処理」でどうにかなる、もしくは規則性などに注目して簡略化する必要があることが推察できます。そこで、問題文から具体的に考えてみます。

詳細は省きますが、具体例をいくつか考えることで「数字のキーを押す」ということと「現在表示されている数字の末尾に押した数字を追加する」ということが(一回目の入力を除いて)完全に一対一に対応していることに気づきます。すなわち、「0が二つ並んでいる」という状態を除くと、追加される数字に関係なく「キーを押す回数」=「数字の桁数」ということがわかります。

したがって、入力を文字列として受け取り、前述した「0が二つ並んでいる」状況のときのみを別処理になるようにして、あとは桁数をカウントするだけで良いです。

文字列として扱う理由は値が大きすぎてC言語組み込みのあらゆる整数型に収まらないからというのと、単純に各桁の数値を確認するだけなら配列としてアクセスしたほうが有利だからです。例えば整数型として格納できたとすると、各桁を取り出すためには割り算や剰余演算くらいしか手がないです。剰余を取る操作などは明らかに配列へのアクセスより遅く、今回の条件ではあまり意味がありません。以下はACコードです。

#include <stdio.h>

int main(void) {
    char s[100002] = {0};
    scanf("%s", s);
    int ans = 0;

    for(int i = 0; s[i] != '\0'; i++) {
        if(s[i] == '0' && s[i + 1] == '0') {
            ans++;
            i++;
        } else {
            ans++;
        }
    }

    printf("%i", ans);

    return 0;
}

まず配列を100002以上で宣言します。これは、10100000=10...0(0が100000個並んでいる)で100001ブロック消費して、さらに文字列として処理しているので終端文字\0の分が必要だからです。

前述の連続した0の処理は、二つ並んだものを見つけたら配列の参照カウントをインクリメントする処理に分岐させるようにしています。これで一回で二文字打ったということと等価になります。

見ての通り計算量的には各桁を見て回るだけなのでO(1)の処理を桁数だけ行うことになります。与えられた数字の桁数は最大で100001なので、余裕で間に合います。

D - Scope

問題文は以下の通りでした。

D問題

問題文が長くて問われていることを理解するだけでも結構大変な問題ですね。最終的にコンテスト後にACすることができたので，思考の過程を載せておきたいと思います。

問題文が複雑なので，まず問われていることを整理しました。この問題で問われていることは，細部を無視するとざっとこんな感じです。

(以下の議論では上の条件でぼかした「ある条件」と「ある操作」については説明しません。ご了承ください。)具体例を見ながらどういう判定法をするといいのかを考えました。例えば，具体例としてコンテストのページに乗っている入力例を以下に提示します。

入力例

この例などを見ながら考えると，良い文字列を)から遡って構成するには，(と)の数を釣り合わせればいいことに気が付くと思います。

例えば上記の入力例をとって説明しましょう。まず最初に出会う)は4文字目です。そこから遡って見返していくと，ほかの)に出会う前に(と出会うことが分かります。この場合，(と)の数が等しい最小の範囲を見つけることができました。

次に出会う)は最後の文字です。ここからさかのぼってみていくと，(に出会う前に)と出会ってしまうことが分かります。したがって，その他の)に出会わなければ2つの(が見つかった場所までが条件を満たす範囲になるはずです。もしこれが本当に正しいのか気になる人は，ほかの良い文字列のパターンなどに適用して確認してみてください。

このような操作を思いつくのは結構大変かもしれません。(実際，私はコンテスト中は間違った方針で進めてしまっていました。)個人的には，まずは「良い数列」の様々なパターンなどを書き出してみて，実際に自分がこの判定をするときにどのような部分に着目するかなどを考えるといいかもしれません。厳密に正しいという証明を出すのは難しくても，発見的手法が威力を発揮する場面は多いと思います。

それでは見つけ出した方法を愚直に実装してみましょう。私は()の数をカウントするのではなく，一番深いネストの()を終えたら()を違う文字で置き換えてしまうという方法をとりました。この操作によって，常に最初に見つかった(で止めればよくなります。

#include <stdio.h>

int main(void) {
    char s[300001] = {0};
    scanf("%s", s);

    char ascii[123] = {0}; // アルファベット小文字はa->97からz->122だからそれぞれのインデックスに対応させる。1がたってたら使用済み

    for(int i = 0; s[i] != '\0'; i++) {
        if(s[i] == '(') {
            continue;
        } else if(s[i] == ')') {
            s[i] = 0;
            for(int j = 0; ; j++) {
                if(s[i - j] == '(') {
                    s[i - j] = 0;
                    break;
                } else if(s[i - j] == 0){
                    continue;
                } else {
                    ascii[s[i - j]] = 0;
                }
            }
        } else {
            if(ascii[s[i]] == 1) {
                printf("No\n");
                return 0;
            } else {
                ascii[s[i]] = 1;
            }
        }
    }

    printf("Yes\n");
    return 0;
}

こんな感じの実装になりました。英小文字カウンターは，asciiコード表でa~zが97~122に割り当てられているのを利用して，そのまま配列にアクセスするキーとして利用しています。途中でブレークすることなく最後までループを回せたらそれはYesの文字列だったという風に判定しています。

TLEくらった提出

...はい，このコード実はTLEを食らいました。 あれだけ自信満々に解説しておいてなんですが，これでは通らないようです。今の方針を維持したままもう少し工夫できるところがないか考えてみましょう。

具体例を見ながら条件をよく考察すると，上記のコードでは必要ない処理をかなり含んでいることが分かります。まずは以下の例を見てください。

文字列(((a(bcd)cde))ef)を考える。

  1. まずabcdと書かれたボールが箱に入れられる。(箱の中: abcd)

  2. )に出会って，bcdが取り出される。(箱の中: a)

  3. cdeと書かれたボールが箱に入れられる。(箱の中: acde)

  4. abcdeが取り出される。(箱の中: なし)

  5. abcdeが取り出される。(二回目)(箱の中: なし)

  6. ボールefが箱に入れられる。(箱の中: ef)

  7. abcdefが取り出される。(箱の中: なし)

  8. 高橋君が操作を終えることができると分かる

注目していただきたいのは，ボールを取り出すフェーズです。よく見ると一度取り出した部分は，その後考える必要がないことが分かります。直観に反すると思うので，もう少し定性的に考えてみます。現在考えている階層より深いネストの()の中にある小文字は，以下の2パターンに分岐します。((abc)abe)を見ながら考えてみるといいと思います。

  1. 現在の階層にあるものとと同じ小文字 -> 「現在の階層」の)に出会えば，より深い部分に行く前にボールは取り出される。(上の例のabが該当する)

  2. 現在の階層に無い小文字 -> 「現在の階層」に至る前に取り出され，それ以降箱に入れられること自体がない。(上の例でcが該当する)

以上から，例えば((abc)abe)は，一回目のボール取り出しをした後は( abe)として扱っても良いということになります。

これを繰り返すことで，一回見た部分を今後見ないという改善策が見つかります。これを実装しましょう。

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    char *s = (char *)calloc(300001, sizeof(char));
    scanf("%s", s);
    int len = 0;
    for(; s[len] != '\0'; len++) {}

    char ascii[123] = {0}; // アルファベット小文字はa->97からz->122だからそれぞれのインデックスに対応させる。1がたってたら使用済み
    char *s1 = NULL;

    for(int i = 0; s[i] != '\0'; i++) {
        if(s[i] == '(') {
            continue;
        } else if(s[i] == ')') {
            int j;
            for(j = 1; ; j++) {
                if(s[i - j] == '(') {
                    break;
                } else {
                    ascii[s[i - j]] = 0;
                }
            }

            s1 = (char *)calloc(len - j, sizeof(char)); // 新しい配列の宣言+代入
            for(int k = 0; i - j > k; k++) {
                s1[k] = s[k];
            }
            for(int k = i + 1, k1 = i - j; len > k; k++, k1++) {
                s1[k1] = s[k];
            }
            len = len - j - 1;
            i = i - j - 1;
            free(s);
            s = s1;
            s1 = NULL;
        } else {
            if(ascii[s[i]] == 1) {
                printf("No\n");
                return 0;
            } else {
                ascii[s[i]] = 1;
            }
        }
    }

    printf("Yes\n");
    return 0;
}

これでAC通りました。うれしい。

かなりごちゃごちゃしてしまいましたが，このコードの要点は，

  1. 最もネストの深い()を見つけて，ボール解放を行う。

  2. 新しく配列を宣言して，その部分のみを除いた文字列を作る。

これを繰り返しているだけです。C言語以外なら多分もっと簡潔に書けると思います。

ちなみにこれは全然最適な方法ではないらしく，今回のコンテストでC言語を用いてD問題を通した中で最も実行時間がかかっていました。余裕があればほかの人のコードも解析しようかな。

終わりに

今回の記事は書くのに過去一番時間がかかりました。ひとえにD問題が強敵だったからです。とんでもねえな

実はいまだにコンテスト中にD問題を通したことがありません。そろそろ通させてくださいマジで。ちなみにレーティングが今回で199まで上がったので，茶色までの折り返しに到達しました。何とか茶色に到達できるように今後も頑張っていけたらなと思います。

完全に私事ですが，このくらいの規模の記事になると流石にタグ含めすべてを手打ちするの結構大変になってきました。もうちょっと何とかしたいです。

それではここまで読んでいただきありがとうございました。よいお年を。

Tags for this post: 競技プログラミング コンテスト参加記録

Other posts tagged by "競技プログラミング"

more ...

Other posts tagged by "コンテスト参加記録"

more ...
Power by Hugo / Theme simplog by michimani