接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Beginner Contest 287(ABC287)

atcoder.jp

A - Majority

Forの個数が $ \lceil \frac{N}{2} \rceil $ 以上であればよい

提出コード

void solve() {
    int N;
    cin >> N;
    int f = 0;
    REP(i, N) {
        string s;
        cin >> s;
        if (s == "For") f++;
    }
    cout << (f >= ceil_div(N, 2) ? "Yes" : "No") << endl;
}

B - Postal Card

全探索で条件を満たすものを数える

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N), T(M);
    REP(i, N) cin >> S[i];
    REP(i, M) cin >> T[i];
    int ans = 0;
    REP(i, N) {
        int ok = 0;
        REP(j, M) {
            int sz = S[i].size();
            if (S[i][sz - 3] == T[j][0] and S[i][sz - 2] == T[j][1] and S[i][sz - 1] == T[j][2]) ok = 1;
        }
        ans += ok;
    }
    cout << ans << endl;
}

C - Path Graph?

パスグラフは木かつ木の直径が $ N - 1 $ であるので辺の数が $ M - 1 $ かつ直径が $ N - 1 $ であるかどうかを判定する

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    treeDiameter g(N);
    REP(i, M) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g.add_edge(u, v);
    }
    if (M != N - 1) {
        cout << "No" << endl;
        return;
    }
    g.build(0);
    if (g.diameter == N - 1) cout << "Yes" << endl;
    else cout << "No" << endl;
}

D - Match or Not

$ x $ を $ 1 $ 増やしたときに前の状態と異なる箇所は2箇所(消える箇所と増える箇所)なので差分更新ができる
よって予め今何文字マッチしているかを求めておき、それを差分更新して各 $ x $ について答えていく

提出コード

void solve() {
    string S, T;
    cin >> S >> T;
    int correct = 0;
    int sz = T.size();
    REP(i, sz) {
        if (S[(int)S.size() - 1 - i] == T[sz - 1 - i] or S[(int)S.size() - 1 - i] == '?' or T[sz - 1 - i] == '?')
            correct++;
        dump(S[(int)S.size() - 1 - i]);
        dump(T[i]);
    }
    int ans = 0;
    cout << (correct == sz ? "Yes" : "No") << endl;
    REP(i, sz) {
        if (S[(int)S.size() - sz + i] == T[i] or S[(int)S.size() - sz + i] == '?' or T[i] == '?') correct--;
        if (S[i] == T[i] or S[i] == '?' or T[i] == '?') correct++;
        // dumps(S[(int)S.size() - sz + i], T[i], S[i]);
        cout << (correct == sz ? "Yes" : "No") << endl;
    }
}

E - Karuta

文字列を辞書順でソートをすると、各 $ i $ についてのLCPはその前後を見るだけでよくなる
各文字列についてその前後のLCPを愚直に求めても文字列の長さの総和程度で収まるのでソートがボトルネックとなり、実行時間以内に求めることができる

提出コード

void solve() {
    int N;
    cin >> N;
    vector<string> S(N);
    vector<pair<string, int>> P(N);
    REP(i, N) {
        cin >> S[i];
        P[i] = {S[i], i};
    }
    sort(ALL(P));
    vector<int> idx(N);
    REP(i, N) idx[i] = P[i].second;
    vector<int> ans(N);
    REP(i, N) {
        int x = P[i].second;
        int ma = 0;
        if (i > 0) {
            int y = P[i - 1].second;
            int cnt = 0;
            REP(i, min(S[x].size(), S[y].size())) {
                if (S[x][i] != S[y][i]) break;
                cnt++;
            }
            chmax(ma, cnt);
        }
        if (i + 1 < N) {
            int y = P[i + 1].second;
            int cnt = 0;
            REP(i, min(S[x].size(), S[y].size())) {
                if (S[x][i] != S[y][i]) break;
                cnt++;
            }
            chmax(ma, cnt);
        }
        ans[x] = ma;
    }
    REP(i, N) cout << ans[i] << endl;
}