競技プログラミングの鉄則

A51 - Stack

基本の例題なのでもちろんACはできたのだがstackではなくvectorで実装してしまったのでこの章の他の問題ではきちんと適切なデータ構造を利用するように意識したい

int main() {
    long long Q;
    cin >> Q;
    vector<string> A(Q);
    for (long long i = 0; i < Q; i++){
        int query;
        cin >> query;
        if (query == 1) {
            string x;
            cin >> x;
            A.push_back(x);
        }
        if (query == 2) {
            cout << A.back() << endl;
        }
        if (query == 3) {
            A.pop_back();
        }
    }
}

A61 - Adjacent Vertices

問題には出力の順番は不問とのことでソートせずに実装したがaccのテストではそこはWA判定になったので提出するときに少しだけドキドキした。
そんなところでドキドキするくらいならソートしておけよという話ではある


int main() {
    long long N,M;
    cin >> N >> M;
    vector<long long> G[100009];
    for (long long i = 0; i < M; i++){
        long long A,B;
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    for (long long i = 1; i <= N; i++){
        cout << i << ": {";
        for (long long j = 0; j < G[i].size(); j++){
            if (j == G[i].size() - 1) cout << G[i][j];
            else{
                cout << G[i][j] << "," << " ";
            }
        }
        cout << "}" << endl;
    }  
}

B11 - Binary Search 2

問題そのものというよりもlower_bound()の使い方をググってるのに微妙な記事ばっかりでメソッドの使い方に苦戦した。

B16 - Frog 1

アルゴ式のアルゴリズム中級や鉄則本を読んだりしたことによってこのレベルの動的計画法であれば流石に瞬殺できるレベルにはなった。

    long long N;
    cin >> N;
    long long dp[100009];
    long long h[100009];
    for (long long i = 1; i <= N; i++){
        cin >> h[i];
    }
    dp[1] = 0;
    dp[2] = abs(h[2] - h[1]);
    for (long long i = 3; i <= N; i++){
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));   
    }
    cout << dp[N] << endl;

B26 - Output Prime Numbers

何故か手元においてる競プロ用のマクロシートみたいなのにエラトステネスの篩のメソッド化したものを用意できていなかったのでこの問題を機にメソッド化した。
正直答えを出すだけならmain()の中でゴリゴリやればよかっただけなのにイキった。
とはいえ詰まったのはC++では配列を返却するメソッドを実装できないというところでvector型のメソッドにしたところくらいだった。そういう意味ではイキった割には勉強になった。

// エラトステネスの篩の関数
vector<bool> Eratosthenes(long long N){
    vector<bool> Deleted(N + 9);
    for (long long i = 2; i <= N;i++){
        Deleted[i] = false;
    }

    for (long long i = 2; i * i <= N;i++){
        if (Deleted[i] == true){
            continue;
        }
        for (long long j = i * 2;j <= N;j += i){
            Deleted[j] = true;
        }
    }
    return Deleted;
}

int main() {
    long long N;
    cin >> N;
    // bool Deleted[1000009];
    // for (long long i = 2; i <= N;i++){
    //     Deleted[i] = false;
    // }

    // for (long long i = 2; i * i <= N;i++){
    //     if (Deleted[i] == true){
    //         continue;
    //     }
    //     for (long long j = i * 2;j <= N;j += i){
    //         Deleted[j] = true;
    //     }
    // }

    vector<bool> Deleted = Eratosthenes(N);

    for (long long i = 2; i <= N;i++){
        if (Deleted[i] == false){
            cout << i << endl;
        }
    }        

}

B36 - Switching Lights

最初 if (one % 2 == K % 2){ cout << "Yes" << endl; }の部分で間違えてNとの偶奇も調べてしまったがNとの偶奇は重要じゃなかった

int countOnesInString(const std::string& bitStr) {
    int count = 0;
    for (char c : bitStr) {
        if (c == '1') {
            ++count;
        }
    }
    return count;
}
int main() {
    long long N,K;
    cin >> N >> K;
    string S;
    cin >> S;
    
    int one = countOnesInString(S);


    if (one % 2 == K % 2){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
        
}

B51 - Bracket

ちょっと普通によくわからなかった。解説読んでもよくわからないし、解説に「相当難しい問題です」という公表が書いてあって絶望した。こちとら初心者なのでお手柔らかにお願いします...。

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

    stack<int> Stack;
    for (int i = 0;i < S.size();i++){
        if (S[i] == '('){
            Stack.push(i+1);
        }
        if (S[i] == ')'){
            cout << Stack.top() << " " << i + 1 << endl;
            Stack.pop();
        }
    }
}

B61 - Influencer

無向グラフの典型問題って感じでさすがに余裕ではある


int main() {
    long long N,M;
    cin >> N >> M;
    vector<long long> G[100009];
    for (long long i = 0; i < M; i++){
        long long A,B;
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }

    long long max = 0;
    long long ans = 0; 
    for (long long i = 1;i <= N;i++){
        if ((long long)G[i].size() > max){
            max = (long long)G[i].size();
            ans = i;
        }
    }

    cout << ans << endl;
}

B12 - Equation

そんなに難しい問題設定じゃなかったので単純に二分探索しようとしたがどうも答えが合わなかったりTLEしたり...
まず、Whileにこだわるのをやめる。計算量を考えればfor文を20回回すだけでよい
小数になる系の誤差とかはもう少し理解を深めないといけない。
流れで解説ACしてしまった。
とはいえ単調増加する3次関数でrightの候補を絞れたりしたのは良かった


long double func(long double x){
    return (x * x * x) + x;
}


int main() {
    long long N;
    cin >> N;
    
    long double left = 1;
    long double right = 100;
    for (int i = 0;i < 20;i++){
        long double mid = (left + right) / 2.0;
        long double f = func(mid);
        if (f > 1.0 * N){
            right = mid;
        }
        else{
            left = mid;
        }
      
    }
    cout << setprecision(10) << fixed << left << endl;
}

AtCoder Boot camp for Beginners

AtCoder Beginner Contest 108

B - Ruined Square
- ユーザー解説の方をみたところ何やら回転行列というのを知らないと実装は難しいらしい。線形代数はサボっててよくわからなかったので調べました。再度日を改めて挑戦します

余談だん

最近はアルゴ式や鉄則本読むのにハマっていて久々にBoot campやったらB問題でボコられて萎えた
しかも明日のABCの配点がA:150,B:250となっていた。こりゃまたまた、かましてくるに違いない。Unratedにしようかな。
鉄則本読んでて思うけど、各アルゴリズム技法の典型問題くらいであれば解けるのだが結局コンテストで求められるのはアルゴリズム技法をベースとした応用なわけで...
いつまでたっても高難易度問題は解けないのではないかと不安になる。