灰コーダーのABC256

2022/06/18に開催された、AtCoder Beginner Contest 256へ参加しましたOsumi Akariです。最大レート340の永遠の灰コーダー（ ~~弱いだけでは？~~ ）ですが、取り敢えずどんなことをしたのかを書いていきます。どんな考えをしてどんなコーディングをしたのかを記録してきたいと思います。

こういう記事、実はコンテスト終了後すぐに出す必要性がある気がしてならない。

A - 2^N (00:03:08)

Nが入力されるので、2のN乗を出力するという問題です。C++（gcc 9.2.1）にはデフォルトの関数としてpow関数が存在するので、それで書けばいいように思えます。

しかしながらpow関数は対数を使用してN乗を求めているので、int型で返ってこないという特徴があります。この仕様を私は知っていたので、Nの制約が非常に大きいことから浮動小数点の誤差が出るのではないかと思いました。そのためこのような簡単な問題にも関わらず、ちょっと時間がかかってしまっています。

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

int main(){
    int N;
    cin >> N;
    int long long ans = 1;
    for(int i = 0; i < N; i++){
        ans = ans * 2;
    }
    cout << ans << endl;
    return 0;
}

B - Batters (00:18:15)

野球をモチーフにしているらしいですが、私は野球に詳しくないので条件の把握に時間がかかってしまいました。要するにカウントのiとN個の数列（Vとします）を用意した上で、以下の順番で進むゲームです。

数直線を用意します。
iが1つ進むごとに、0の場所に駒を追加します。
V.at(i)に書かれている数だけ全ての駒を動かします。
数直線で5を超えた場所に来た駒の数を数えて捨てる。

制限が緩いのでそのままシミュレートしました。移動の跡地をならすことを忘れていて、最初は焦りましたが…。

int main(){
    int N;
    cin >> N;
    vector<int> V(N);
    for(int i = 0; i < N; i++){
        cin >> V.at(i);
    }
    int P = 0;
    vector<int> diamond(9); //9じゃなくて8で良かった気がする
    for(int i = 0; i < N; i++){
        diamond.at(0) = diamond.at(0)+1;
        vector<int> diamond_orig(9); //9じゃなくて8で良かった気がする2
        for(int j = 0; j < 9; j++){
            diamond_orig.at(j) = diamond.at(j);
        }
        for(int j = 0; j < 4; j++){
            diamond.at(j+V.at(i)) = diamond_orig.at(j);
        }
        for(int j = 0; j < V.at(i); j++){
            diamond.at(j) = 0; //移動の跡地を均す
        }
        for(int j = 4; j < 9; j++){
            P = diamond.at(j) + P;
            diamond.at(j) = 0;
        }
    }
    cout << P << endl;
    return 0;
}

C - Filling 3x3 array (NoSub)

問題: C - Filling 3x3 array
提出: 無し
公式解説

nCrでおなじみの組み合わせで2*2の全探索をしたかった。

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

int main(){
    vector<int> A(3),B(3);
    for(int i = 0; i < 3; i++){
        cin >> A.at(i);
    }
    for(int i = 0; i < 3; i++){
        cin >> B.at(i);
    }
    int maxhw = max(max(A.at(0),max(A.at(1),A.at(2))),  max(B.at(0),max(B.at(1),B.at(2))));
    vector<vector<int>> kugiri(3, vector<int>(3)); //kurigi内部の数はmaxhw+1まで。kurigi.at(n).at(1)はkurigi.at(n).at(0)以上。
    kugiri.at(0).at(3) = maxhw+1;
    kugiri.at(1).at(3) = maxhw+1;
    kugiri.at(2).at(3) = maxhw+1;
    vector<vector<int>> nine(3, vector<int>(3));
    for(int i = 0; i < maxhw, i++){
        for(int j = 0; j < maxhw; j++){
            
        }

    }
    return 0;
}

D - Union of Interval (2 TLE)

脳筋プレイ、失敗…

…の一言に尽きます（そんなことはない）。みんな大好きお店に出入りする問題を、ちょっと数学チックに言い換えた感じの問題です。脳筋プレイをしたらTLEが出てしまいました。冷静に考えればimos法で解けばいい問題なので実装しようと思ったらコンテストが終わっていました。悲しいです。

#include <bits/stdc++.h>
using namespace std;
//useful 
#define rep(i,n) for(int i = 0; i < (n); i++)

int main(){
    int N;
    cin >> N;
    vector<vector<int>> LR(N, vector<int>(2));
    vector<int> linear(N*2);
    for(int i = 0; i < N; i++){
        cin >> LR.at(i).at(0) >> LR.at(i).at(1);
        linear.at(i*2) = LR.at(i).at(0);
        linear.at(i*2 + 1) = LR.at(i).at(1);
    }
    sort(linear.begin(),linear.end(),greater<int>());
    int linearmax = linear.at(0)+1;
    vector<int> V(linearmax);
    for(int i = 0; i < N; i++){
        for(int j = LR.at(i).at(0); j < LR.at(i).at(1); j++){
            V.at(j) = V.at(j) + 1;
        }
    }
    if(V.at(0) != 0){
            cout << 0 << " ";
    }
    for(int i = 1; i < linearmax; i++){
        if(V.at(i-1) == 0 && V.at(i) != 0){
            cout << i << " ";
        }
        else if (V.at(i-1) != 0 && V.at(i) == 0){
            cout << i << endl;
        }
    }
    cout << endl;
    return 0;
}

次回に向けて

次回のAtCoder関連記事: 灰コーダーのABC279

取り敢えず日本語を読む能力を鍛えましょう。

バッチを叩くだけで、USBメモリをバックアップしたい

地球を輪切りにして考える

Writer

Osumi Akari