LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Gettei(すぱ げってぃ)

競プロ日記#25/05/23

Posted at

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

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にしようかな。
鉄則本読んでて思うけど、各アルゴリズム技法の典型問題くらいであれば解けるのだが結局コンテストで求められるのはアルゴリズム技法をベースとした応用なわけで...
いつまでたっても高難易度問題は解けないのではないかと不安になる。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?