ABC280に参加してきました！

今回もABCに参加してきました。

どうもこんにちは。大学の課題が結構やばいことになっているInです。今回もABCに参加してきましたので，その参加記事になっております。別に競技プログラミングのためだけにこのブログ(?)を開設したわけじゃないのに，現状では競技プログラミングの記事しかないことを憂いております。(やる気やらなんやらの問題で筆が進まないんですよね)

閑話休題。それでは今週の参加感想記事です。

結果発表のコーナー

今週の提出結果です。

なんと今回は運よくCまで解くことができました。(ドンドンパフパフ)

今回の成績は，4888/8672で，パフォーマンス375でした。そこそこよろしいんじゃないでしょうか？(そこ，灰パフォでイキるなとか言わない！)レーティング変動は今回プラス34で現在104です。入茶が楽しみです。

解法やらなんやらの振り返り

今週もいつものごとく問題をどのように解いたのかを忘備録として記録しておきます。まずはA問題です。

*Oh...*今週のA問題はなんだか見た目がいかついですね。正直A問題でつまずいて死ぬパターンかと思いました。

さて，見た目はいかついですが，この問題はよく見てみるとそんなに難しいことを言っていないことが分かります。

要するに#.##...#←こんな感じの文字列(文字列一つにつきW個の文字)がH回入力されるので，#の数を数えてくださいねということです。先週の文字列祭りに比べたらだいぶんましですね。方針としては，HもWも少ないのが制約からわかるので，シンプルに文字列として標準入力から読み取って，一文字づつ見ていく感じで処理しました。以下コードです。

#include <stdio.h>

int main(void) {
    int h, w;
    scanf("%i %i", &h, &w);
    char word[11];
    int count = 0;

    for(int i = 0; h > i; i++) {
        scanf("%s", word);
        for(int j = 0; w > j; j++) {
            if(word[j] == '#') {
                count++;
            } else if(word[j] == '0') {
                break;
            }
        }
    }

    printf("%i\n", count);
    return 0;
}

そこそこシンプルに書くことができました。ある程度標準入出力の使い方には慣れてきたんじゃないかなと思います。

さて，次はB問題です。以下問題文です。

記号と数字がわちゃわちゃしていて結構ウッってなる人多いかもしれません。僕もそうでした。 しかし，一回紙に書くとかなりシンプルに整理されることが分かります。 実際，S_k+1=S_k+A_k+1が成立しますから，逆に見るとA_k=S_k-S_k-1(ただしS₀=0) という関係式が成り立つことが分かります。したがって，二つのSから一つのAを錬成しながら出力していく方針で解けます。いやー数学って偉大ですね。以下通ったコードです。

#include <stdio.h>

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

    int s1, s2;
    s1 = 0;
    for(int i = 0; n > i; i++) {
        scanf("%i", &s2);
        printf("%i ", s2 - s1);
        s1 = s2;
    }

    return 0;
}

なんとA問題よりも短くなってしまいました。個人的には実装含めての難易度だと今回Bのほうが簡単だと思いました。

あと余談なんですが，誰が読んでも誤解を与えないという点では競プロのような問題文の書き方は適切だとは思いますが，記号を大量に使用するのは可読性っていう点だとどうなのかなってちょっと思ったりします。まあ例がついているので支障はそんなにないですが。

次はC問題です。以下問題文です。

英小文字のみからなる文字列を比較する問題のようです。文字列TはSにもう一つだけ文字を追加して作られているもののようですね。今回のC問題はなんかやたらとシンプルで助かりました。

方針としては，まず二つの配列を用意して文字列として読み取り，次にSとTを頭から見ていって，初めて一致しなくなった場所が答えという感じで行きました。配列としてみるときはインデックスが一つずれるので注意です。以下AC通ったコードです。

#include <stdio.h>

int main(void) {
    char s[500001];
    char t[500002];

    scanf("%s", s);
    scanf("%s", t);

    for(int i = 0; ; i++) {
        if(s[i] != t[i]) {
            printf("%i\n", i + 1);
            break;
        }
    }

    return 0;
}

こんな感じで実装しました。手元のマシンだとstaticではない配列の宣言で要素500000とかあまりやらないので結構ジャッジサーバーは融通効くなって印象です。

ちなみに余談ですが，この問題多くの人が引っ掛かったポイントがあったようで，(自分も1WA食らいました。)それは，「Sの最後に付け足すパターン」の見落としです。このミスは初心者から上位勢までみんな食らっててちょっと面白かったです。おそらく多くの人が引っ掛かった理由は，普通は\0(終端文字)が出現したら読み取りのループをブレークするのですが，この問題に関しては必ずTがSから構成される文字列であることが保証されているので，そんな気遣いをしなくてもOKだったっていう感じだと思われます。

D問題は，，解けなかったよ

今回Cの提出まで結構スムーズに行けたので，「お！ワンチャンあるか？」と思っていましたが，D問題結局解けませんでした。。。

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

この問題，見た目は結構シンプルなんですが，かなり厄介で手を動かすだけだと無理でした。

というのも，直接階乗を計算するのが無理なんですよね。 Cでの整数型の最大値unsigned long long intの最大が，18446744073709551615となっており，20桁まで入るんですが，実は20!の時点で18桁の整数になります。 階乗はおそロシア。なので，ほかの部分に注目して行かなくてはいけないんですけど，効率的な方法を見つけられなかったのと，実装力の低さのせいでスパゲッティコードを錬成してタイムアップしました。ただ，数学的に解を見つけられそうなので解けたら別記事として投稿したいなとは思っています。

終わりに

ABCを始めてから3週間ほどたちますが，少しは成長したのかなと思います。課題で忙しい時もありますが，ドンドンAtCoder Beginer's Selectionや競プロ典型90問などにも取り組んでいけたらいいなと思います。(アルゴ式も)目指せ茶コーダー！

余談ですが，このサイトに投稿されている記事は，markdownからの変換とかではなくすべてhtmlを手打ちしているので，手書きhtmlかなり慣れてきたような気もします。いいことなのかは知らん。

今回も読んでいただきありがとうございました。次の記事で会いましょう。

P.S. UEC Advent Calendar1とUEC Advent Calendar2が開催中ですので，興味があったら皆さんも読みましょう。(私も24日に寄稿(?)予定です。)