【AtCoder Beginner Contest 158】コンテストに初参加した話

以前競プロを勧める記事を書きました。

プログラミング初心者こそ競技プログラミングがおすすめ！

2020年3月15日

書いたんですがぼくも競技プログラミング初心者です。なので初心を忘れないうちにどんな感じで問題に挑んでいたのかを備忘録的にまとめたいと思います。

1 参加したコンテスト
2 提出結果と感想
3 問題について
4 終わりに

参加したコンテスト

AtCoderのABCと呼ばれるコンテストに参加しました。（以下のリンクは英語で書かれていますがサイトは全て日本語です）

先に問題が見たい方、この記事を見ながら問題を見たい人はリンクから見てください。

提出結果と感想

プログラミングもほぼ初心者なのでABまで解ければ及第点かな、と思いましたがCまで解くことができ、Dもあと一歩というとこまで迫れた気がします。(このDは実装より計算量の面で工夫が必要な問題だったので、途中まで手をつけられたのは偶々。)

コンテストなので順位表というものが更新されていくんですがトップ層が信じられない早さで解く様子が見られます。怖いです。

コンテスト後は他の参加者のコードを見ることができますが、簡単な問題だと言語によっては一行で終わりのものがあったりして見てて面白いです。どういうこと？？？

問題について

Aの提出コードと考えたこと

#include <bits/stdc++.h>
using namespace std;

int main(){
    string S;
    cin >> S;

    if(S == "AAA" || S == "BBB"){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}

考えること、言っても大したことはないですね。（なら6分もかけるな）

初コンテストで急がなきゃ、と焦っていましたが具体例を書けば全てAまたはBであるときで”No”になるとわかりました。文字列の長さも3文字で短いので実装も楽。

Bの提出コードと考えたこと

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long N,A,B,rep,ans,rem;
    cin >> N >> A >> B;
    rep = N / (A + B);
    rem = N - (A + B) * rep;
    if(rem >= A){
        cout << rep * A + A << endl;
    }else{
        cout << rep * A + rem << endl;
    }
    return 0;
}

できるボールの列が短ければ、ループを回して文字列としてその情報を持っておく。（青青赤→BBRのように）

そのあとで青玉の数（文字列内のRの登場回数）を数えればいいんですが、Nが大きいのでTLEになるだろうと分かります。

赤と青合わせてA + B個ずつボールを追加するんですから、この塊がいくつ続くのかを考えるとN / (A + B)回（= repとします）ですね。（小数点以下は切り捨てられるのでこれでよし）

ここまでで青玉の数はA * rep個です。

このあとも青玉→赤玉の順に追加して行きますが、途中でボールの列の長さがNになり操作が終わります。追加すべき玉の数はN % (A + B)（= rem）で表せるので（提出コードでは%の存在をすっかり忘れて違う書き方をしていますが）Aの値によって、ここで追加される青玉は、A個すべて(A <= remの時)またはrem個(A > rem)の時に分けられます。

あとはそれぞれA * repとの和をとって出力すればACです。そこそこ時間をかけて解いたので達成感がありましたね。

Cの提出コードと考えたこと

#include <bits/stdc++.h>
using namespace std;

int main(){
    int A,B;
    cin >> A >> B;

    double al,ar,bl,br;
    al = 12.5 * A;
    ar = al + 12.5;
    bl = 10 * B;
    br = bl + 10;
    
    int ans;
    if(ar <= bl || br <= al){
        cout << "-1" << endl;
    }else if(al <= bl){
        cout << ceil(bl) << endl;
    }else if(bl <= al){
        cout << ceil(al) << endl;
    }

    return 0;
}

もっと楽なやり方があるんですが、それはあとで載せます。

数式が混じるので画像にまとめました。（TeXで書けや）