初冬

競技プログラミング・俳句・生成AI（Bard・Stable Diffusionなどなど）・AIアート・日記。それらを書いています。それらについてとりとめもなく書くブログです。行き当たりばったりで書いてます。

トップ > 競技プログラミング > AtCoder Beginner Contest 302 感想 A問題 B問題

AtCoder Beginner Contest 302 感想 A問題 B問題

競技プログラミング

総評

AtCoder Beginner Contest（ABC）に参加してきました！
結果はAとBとCとDとEの5つACして5完でした。
やった！
参加する前に4完か5完したいって言っていたので言った通り実現できてうれしいです！
パフォーマンスも1000を越えて満足いってます。
やった、やった！
昨日のことですけど、もうすごくうれしいです！
やった！

atcoder.jp

今回は配点がいつもと変わっていました。
B問題とC問題が250点でいつもはB問題が200点、C問題が300点で「どんな風になるんだろ……？」と思っていました。
蓋を開けてみればB問題がいつもに比べると本当に250点相当に難しい！ これで苦戦した人いるんじゃないかなと思います。
私もまあまあ解くのに時間かかりました。

問題 A B C D E F G Ex
配点 100 250 250 400 425 500 625 625

私の実力的にAからE問題を解いて5完というのは終わってみれば妥当だと思います。
F問題はちょっと難しかった……！
時間があっても解けなかったと思います。
なので、満足です。
欲張りすぎず、自分の実力に合った成績が出ているのでまあまあ、よし！ 良かった、良かった！
そんな感じで捉えてます。

この記事は感想なので、解説書いたり書かなかったりです。
解説書いているといつまでも時間がかかって書ききれないので、あまり書かないと思います。
そんなわけで一問一問振り返っていきます。
コードも載せたり載せなかったりです。
適当にやっていきましょう。

A - Attack

atcoder.jp

A問題は次のようなコードで解きました。
数学です。
数学の式です。
これは知っているか否かなので、知らなかった方は公式の解説を読むといいと思います。
切り上げのテクニックなので「割り算　切り上げ　プログラミング」くらいで検索したら出てこないかな？

#include <bits/stdc++.h>

using namespace std;


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

    long long A, B;
    cin >> A >> B;
    cout << (A + B - 1) / B << endl;
    return 0;
}

atcoder.jp

場合分けで解いても良かったですね！
むしろそっちの方が早く解けたかもしれない！
「えっと、切り上げのときの式ってどう書くんだっけ」と考えていたら遅れたので……。
A問題で出遅れるなんてなさけないです。
しかし、私は結構解くの遅い方で、いつもA問題解くのに時間がかかって……お気に入りに入れている人たちと比べて「遅い……なんて遅いんだ！」になってます。

場合分け無しだと、次のような感じですね。
今さっと書けたんで、そっちの方が良かったかなあ？　になってます。
A問題に2分くらいかかっていて、たぶんこっちの解法だともう少し早く解けた……！？
まあ、あまり変わらないので気にしてません。
どっちだって正解ですし、序盤の早さは気にしません。

#include <bits/stdc++.h>

using namespace std;


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

    long long A, B;
    cin >> A >> B;
    if (A % B == 0LL) {
        cout << A / B << endl;
    }
    else {
        cout << A / B + 1 << endl;
    }
    return 0;
}

atcoder.jp

B - Find snuke

atcoder.jp

この問題は難しかったですね……、B問題なのに！
ただ、やったことある解法だったのに、私はサクサク書いていけました。
それでも解くのに10分くらいかかってますが……！
たしか、解いたときはpredictorで1200のパフォーマンスを越えていたような気がします。 みんな苦戦していたようです。
確かに時間かかっても解けなかった人がいると思います。

今回A問題しか解けなかった人も心配することはないです。
私もABCで1完だったときにかなり苦しんで「才能ないのかな？」とかいろいろ頭によぎりました。
ABC、1完はしんどい、辛い気分になりますが、気にすることないです。
誰でも起こりうることだし、自分の能力を信じてあげた方が絶対にいいです。

#include <bits/stdc++.h>

using namespace std;


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

    long long H, W;
    cin >> H >> W;
    vector<string> S(H, "");
    for (long long i = 0LL; i < H; ++i) {
        cin >> S[i];
    }
    string snuke = "snuke";
    vector<pair<long long, long long>> dxdy {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0},
        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
    };
    for (long long i = 0LL; i < H; ++i) {
        for (long long j = 0LL; j < W; ++j) {
            for (auto &[dy, dx] : dxdy) {
                vector<pair<long long, long long>> ans;
                bool flag = true;
                for (long long k = 0LL; k < 5; ++k) {
                    long long ny = i + dy * k;
                    long long nx = j + dx * k;
                    if (ny >= 0LL && ny < H && nx >= 0LL && nx < W && S[ny][nx] == snuke[k]) {
                        ans.push_back(make_pair(ny, nx));
                    }
                    else {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    for (auto &[a, b] : ans) {
                        cout << a + 1 <<  " " << b + 1 << endl;
                    }
                    return 0;
                }
            }
        }
    }
    return 0;
}

atcoder.jp

この問題には定石があり、私の書いたコードの中ではdxdy（ディーエックスディーワイ）と書かれているところです。
これを用いて8方向に探索します。
for文で8方向に動かせるので、if文をいっぱい書くよりも楽です。
私はこの方法を競技プログラミングをするまで知りませんでした。
競技プログラミング以外で使ったことあるかと言われるとないですが……すごく便利です。
頭いいなと思います。

#include <bits/stdc++.h>

using namespace std;


int main() {
    vector<pair<long long, long long>> dxdy {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0},
        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
    };
    for (auto &[dy, dx] : dxdy) {
        cout << dy << " " << dx << endl;
    }
    return 0;
}

とりあえずこれで8方向にイチマスずつ探索出来ます。
今回は縦横斜めに5マス連続で見ないといけないので少し工夫が要ります。
ついでなので説明します。
私ので分からなかったら、他の人のコードを見るといいと思います……それくらい便利なので覚えておいた方がのちのちの競技プログラミングの問題でも楽をすることができると思うので、分かっておいた方がいいと思います。

次に書く2つのコードの内どちらでも8方向で5マス連続で走査していることが分かると思います。
少し工夫が要ります。
難しいですが、覚えておいて損はないです！
ABCでもときどきこういうことができると得をすることがあるので覚えておくといいでしょう……さっきも言ったかな？
まあ、いいや。
自分で書いていて勉強になりました。

#include <bits/stdc++.h>

using namespace std;


int main() {
    vector<pair<long long, long long>> dxdy {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0},
        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
    };
    long long i = 0LL;
    long long j = 0LL;
    for (auto &[dy, dx] : dxdy) {
        for (long long k = 0LL; k < 5; ++k) {
            long long ny = i + dy * k;
            long long nx = j + dx * k;
            cout << ny << " " << nx << endl;
        }
        cout << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;


int main() {
    vector<pair<long long, long long>> dxdy {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0},
        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
    };
    long long i = 0LL;
    long long j = 0LL;
    for (auto &[dy, dx] : dxdy) {
        long long ny = i;
        long long nx = j;
        for (long long k = 0LL; k < 5; ++k) {
            cout << ny << " " << nx << endl;
            ny += dy;
            nx += dx;
        }
        cout << endl;
    }
    return 0;
}

終わり

長くなったのと夜も遅くなったので今日は一旦ここで区切ります。
続きは書くかもしれないし、書かないかもしれません。
振り返りしながら他人のコードを見たり、考えたり、まとめたりすると頭が良くなる感じが……やっていて意味があります。
楽しいのでするかもしれません。

© 2023 ashitsunokara