AtCoder Beginner Contest 328 振り返り

ABC328

概要

A - Not Too Hard

考えてたこと
全探索

提出したもの

a.cpp

int main() {
    int n, x;
    int points = 0;

    cin >> n >> x;

    for (int i = 0; i < n; i++) {
        int s;
        cin >> s;
        if (s <= x) {
            points += s;
        }
    }
    cout << points << endl;
    return 0;
}

振り返り
特になし。

B - 11/11

考えてたこと
全探索、月日を一文字ずつsetに入れてsetの中身が1の時、全ての値が同じ、つまりゾロ目。

提出したもの

b.cpp

int main() {
    int n;
    cin >> n;

    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        int d;
        cin >> d;
        for (int date = 1; date <= d; date++) {
            set<char> set;
            fore(j, to_string(i)) {
                set.insert(j);
            }

            fore(k, to_string(date)) {
                set.insert(k);
            }

            if (set.size() == 1) {
                cnt++;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

振り返り
特になし。

C - Consecutive

考えてたこと
累積和、毎回全探索していたら計算量が足りないけど先に保持しておけば十分足りる。

提出したもの

c.cpp

int main() {
    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    vector<int> vec(n + 1);
    vec[0] = 0;
    vec[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (s[i - 2] == s[i - 1]) {
            vec[i] = vec[i - 1] + 1;
        } else {
            vec[i] = vec[i - 1];
        }
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;

        cout << vec[r] - vec[l] << endl;
    }

    return 0;
}

振り返り
最近解いたから累積和ってすぐに気づいて解けたけど、実際に328が開催されていた頃だと解けなかった気がする、成長。

D - Take ABC

考えてたこと
ABCを都度消すと文字列の都合的に計算量が足りなそうだからそれを解決する問題なのかなぁと推測。文字列を一文字ずつ確認してABCの並びになる時だけ別の文字列に足していって最終的に完成するその文字列を出力。しかしWA。

提出したもの

d.cpp

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

    string ans;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'A') {
            if (i + 1 < s.size() && s[i + 1] == 'B') {
                if (i + 2 < s.size() && s[i + 2] == 'C') {
                    i += 2;
                } else {
                    ans += s[i];
                }
            } else {
                ans += s[i];
            }
        } else {
            ans += s[i];
        }
    }

    cout << ans << endl;
    return 0;
}

考えてたこと(2回目)
どうにもABCを消した後にABCが作成される際に問題になるらしい。(例えば、AABCBCのような場合、AABCBC -> ABCで処理が終了してしまう。)
何周か回せば解決する問題ではありそうだけど、その何周がどれくらいかかるかも分からず結局うまく実装できなかった。

振り返り
解答を見た上での振り返り。適合したものを別の変数に入れていくのではなく、とりあえず別の変数に入れて末尾をその都度確認するという方針だった。確かにこの方針なら削除する文字列以外の文字列の移動が発生しないから計算量も十分に足りそう。

感想

D問題がめちゃくちゃ悔しい、大体方針はあっていたけど後一捻り考えられなかった、精進。