始めてAtCorderに参戦して、気づいたこと

目次

1.この記事の目的
2.はじめに
3.結果
4.参加して気づいたこと
5.コンテスト参加の流れ
6.問題A
7.問題B
8.解く時に参考にした記事
9.あとがき

この記事の目的

• モチベーションの維持
• 1,2年後の振り返り用
• アウトプットの練習
• 同じような境遇の人がいたら参考になりそう
• (有識者にアドバイスもらえたら嬉しい)

はじめに

これは、ABC392に参加した感想と振り返りについての記事です。
初めての記事投稿なので、不備があると思います。何かあれば、ご連絡お願いします。

結果

A問題（6分47秒）とB問題（72分22秒）が解けました。C問題は間に合いませんでした。
結果は、以下の通りです。

参加回数が5回に満たない場合は、推定より大幅に低いレーティングになるそうです。伸び代ってやつですね。
→参加し続けることのが大事。(改めて、色付きの人ってすごいことに気がつきました！)

参加して気づいたこと

色付きコーダーって本当にすごいんだ！

道のりは、長いなと思いました。
みんな最初は、灰色だった。
人と比べずに、気楽にやろうと思いました。

paizaの経験も活きた！

AtCorderを始める前までは、paizaのスキルチェックやってました。
paizaは、問題ごとにレートがあります。そのため、自分のレートに合わせて解くことができ、個人的には、取り組みやすかったです。また、解答時間中央値が問題と一緒に乗っているので、隙間時間に合わせて解くこともできます。（解答時間中央値を大幅に超えることもありましたが）
今回、paizaでのスキルチェックの経験がAtCorderでも活かせました。

for文とwhile文、使い分けるべきだった！

for文は、回数が決まった処理で使うと便利。
while文は、繰り返す回数が決まっていないが拘束条件がある場合に使うと便利。
（今まで、できること同じだから、使い分けても意味ないって思ってました。そんなことありませんでした）

大会に出るの大事

大会、特有のワクワク感があって楽しかったです。また、取り組もうという気持ちになりました。

計算量大事

計算量がわかると、解答の方針に自信が持てるし、考え直さないと行けない場合は早めに気付ける。大会出る前に、なんとなく計算量について知っていたのが生きました。（けれどまだまだ不十分です）

今後の課題

B問題を早く解く

著者の実力としては、簡単な問題ならC問題が解けるというレベルです。けれども、B問題に時間が掛かってしまったら、意味がないです。

この記事を参考にして、精進して行きたいと思っています。まだまだ、具体的な方針については考え中です。

計算量についての理解

計算量についての理解がまだまだ甘い。
また、計算量についてある程度わかっていても、計算量を減らす方法がわかってないのも問題。

環境構築が不十分

次は、#include < bits/stdc++.h >が使える形にする。

setやmapやorderedがわからない

B問題やC問題を見たときに、使えるのではと思いましたが、具体的にどうコードを書けば良いのかわかりませんでした。次回までには、使えるようにしたいです。

コンテスト参加の流れ

21:00から、コンテストに取り組み始めました。始まる前は、ドキドキでした。

問題A

https://atcoder.jp/contests/abc392/tasks/abc392_a
6分47秒で解けました。
↓実際に提出したコードです。

a.cpp

#include <iostream>
#define rep(i,cc,n) for(int i=cc;i<n;++i)
using namespace std;

int main(){
    int n=3;
    int a[3];
    rep(i,0,n){
        cin>>a[i];
    }
    bool flag=false;

    if(a[0]*a[1]==a[2]){
        flag=true;
    }else if(a[1]*a[2]==a[0]){
        flag=true;
    }else if(a[2]*a[0]==a[1]){
        flag=true;
    }
    if(flag==true){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

}

もっと、効率的な方法あるだろと思いながら解いてました。sortするのもありかなとか思ったり、でも、計算量的には問題ないから、いいやって感じでした。下は、ChatGPTに投げたやつです。
計算量って大事なんですね。問題解く前に、この方針で行けるか行けないかわかるし。（基本的には、A問題やB問題は計算量そこまで意識しなくてもいいらしいですが）

a.cpp

#include <iostream>
#define rep(i, cc, n) for (int i = cc; i < n; ++i)
using namespace std;

int main() {
    int a[3];
    cin >> a[0] >> a[1] >> a[2];

    if (a[0] * a[1] == a[2] || a[1] * a[2] == a[0] || a[2] * a[0] == a[1]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

なるほど、||でまとめれば、早いしboolとか使う必要なかったですね。

問題B

正直いって、ひどいです。またもや、bool使う必要なかったし。(最近bool使って二重ループ抜け出すの覚えて、使いたくなってしまいました。)72分22秒で提出してますね。大苦戦です。
↓わかりづらすぎたので、実際提出したコードにコメントを加えてます。

b.cpp

#include <iostream>
#include<algorithm>
#include<vector>
#include <set> 
#define rep(i,cc,n) for(int i=cc;i<n;++i)
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(m);
    rep(i,0,m){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    
    vector<int> x;
    x.reserve(n);//こうすると、処理時間が早くなるらしい。
    int j=1;
    //cout<<"-----"<<endl;//最初、処理が終わらなくって、どこまで処理ができたのか確認してます。
    bool flag=false;
    
    for(int i=0;i<m;){
        if(flag)break;//いりませんでした。
        for(;j<=n;){
            if(j<a[i]){
                x.push_back(j);
                //cout<<"push back :"<<j<<endl;//分岐、どっち進んでいるか気になりました。
                j++;
                break;
            }
            if(j==a[i]){
                //cout<<"hit : "<<j<<endl;//こっちの処理で詰まった記憶があります。
                j++;
                i++;
                break;
            }

        }
    }
    for(;j<=n;j++){
        x.push_back(j);//上のif文に組み込めるだろうと思ったけど、難しかった。精進します。
    }


    size_t leng=x.size();
    cout<<leng<<endl;
    if(leng==0){
    }else{
    rep(i,0,leng-1){
        cout<<x[i]<<" ";
    }
    cout<<x[leng-1]<<endl;
    }
    
}

#include < bits/stdc++.h >すれば、上の方省略できるらしいのですが、環境構築するのめんどくさくてサボりました。反省です。

正直、なかなかうまくいかなったです。無限ループしたり、処理が終わらなかったり。プログラムの大筋書くのはそこまで大変ではなかったですが、デバックが大変でした。あと、非効率なのはわかってたし、TLEもありえるとか思ってました。
理由としては、端の処理が上手に考えられなかったのが大きいです。ここで、Chat GPT先生に改良を頼んでみたので、取り上げたいと思います。

b.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

#define rep(i, cc, n) for (int i = cc; i < n; ++i)
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    
    for (int &val : a) cin >> val;
    sort(a.begin(), a.end());

    vector<int> x;
    x.reserve(n);

    int j = 1, i = 0;

    while (j <= n) {
        if (i < m && j == a[i]) {
            ++i; // `a[i]` に含まれる要素はスキップ
        } else {
            x.push_back(j);
        }
        ++j;
    }

    cout << x.size() << endl;
    
    if (!x.empty()) {
        copy(x.begin(), x.end() - 1, ostream_iterator<int>(cout, " "));
        cout << x.back() << endl;
    }

    return 0;
}

なるほどです。参りました。for文とwhile文を使い分けるって大事なんですね。正直、for文とwhile文書き換え可能だし、どっちも大差ないだろと思ってました。

vector<int> a(m);
    
for (int &val : a) cin >> val;

この書き方、かっこいいですね次からはこれにしたいと思います。

解説読んでみた

解法1は、全く思いつきませんでした。あるなしを0,1で表して、なかったら追加、あったらスキップって感じでしょうか。こういう解法できるようになりたいです。

解く時に参考にした記事

vectorの取り扱いがわからなくて、拝見させていただきました。

あとがき

記事書くの難しかった。けれど、きちんと振り返りができてよかったです。