AtCoder Beginner Contest 122

結果

　38分51秒(1WA)で全完、103位だった。やはりWAを出してしまうと100位以内は難しい。

A問題

　条件分けを書くので微妙に時間を取られた。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    char b;
    cin >> b;
    cout << (b == 'A' ? 'T' :
        b == 'T' ? 'A' :
        b == 'C' ? 'G' :
        'C') << endl;;
}

B問題

　部分文字列というのを最初勘違いしていてATCGの数を数えればいいだけかと思ったら違っていた。スマートなやり方が思いつかず切る位置を全探索しようとしたら、終了位置を間違えて一番最後の文字をカウントできず1WA。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

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

    ll ans = 0;
    for (ll i = 0; i < S.size(); i++) {
        for (ll j = i; j < S.size() + 1; j++) {
            auto sub = S.substr(i, j - i);
            bool all = true;
            for (char c : sub) {
                if (!(c == 'A' || c == 'T' || c == 'C' || c == 'G')) {
                    all = false;
                }
            }

            if (all) {
                ans = max(ans, j - i);
            }
        }
    }
    cout << ans << endl;
}

C問題

　前回のAGCの反省から今日は丁寧にメモを取ろうということでこのあたりかたできるだけ奇麗に書くことを心がけてやっていく。パッと見累積和でやれそうだと思って、添え字の部分をきちんと処理するためにサンプルを使って考えて上手く1回目の実装で解けた。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, Q;
    string S;
    cin >> N >> Q >> S;
    vector<ll> l(Q), r(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> l[i] >> r[i];
    }

    vector<ll> sum(N, 0);
    for (ll i = 1; i < N; i++) {
        if (S[i] == 'C' && S[i - 1] == 'A') {
            sum[i]++;
        }
    }

    for (ll i = 1; i < N; i++) {
        sum[i] += sum[i - 1];
    }

    for (ll i = 0; i < Q; i++) {
        cout << sum[r[i] - 1] - sum[l[i] - 1] << endl;
    }
}

D問題

　考察はメモの通り。

　メモ中では配列っぽいDPで考えたけど、4次元配列はvectorで取ると面倒なのでmapとtupleを使ったメモ化再帰で実装した。計算量に余裕があったので配列じゃなくても間に合うという判断。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N;
constexpr ll MOD = 1e9 + 7;
map<tuple<ll, char, char, char>, pair<bool, ll>> memo;

ll solve(ll i, char j, char k, char l) {
    if (i == N) {
        return 1;
    }

    auto curr = make_tuple(i, j, k, l);
    if (memo[curr].first) {
        return memo[curr].second;
    }
    memo[curr].first = true;

    ll ans = 0;
    if ((j == 'A' && l == 'G') || (j == 'A' && k == 'G') || (k == 'G' && l == 'A') || (k == 'A' && l == 'G')) {
        (ans += solve(i + 1, k, l, 'A')) %= MOD;
        (ans += solve(i + 1, k, l, 'T')) %= MOD;
        (ans += solve(i + 1, k, l, 'G')) %= MOD;
    } else if (k == 'A' && l == 'C') {
        (ans += solve(i + 1, k, l, 'A')) %= MOD;
        (ans += solve(i + 1, k, l, 'T')) %= MOD;
        (ans += solve(i + 1, k, l, 'C')) %= MOD;
    } else {
        (ans += solve(i + 1, k, l, 'A')) %= MOD;
        (ans += solve(i + 1, k, l, 'T')) %= MOD;
        (ans += solve(i + 1, k, l, 'C')) %= MOD;
        (ans += solve(i + 1, k, l, 'G')) %= MOD;
    }

    return memo[curr].second = ans;
}

int main() {
    cin >> N;
    cout << solve(0, 'X', 'X', 'X') << endl;
}