接着剤の精進日記

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

AtCoder Beginner Contest 291(ABC291)

atcoder.jp

A - camel Case

大文字の判定を行う

提出コード

void solve() {
    string S;
    cin >> S;
    REP(i, S.size()) {
        if ('A' <= S[i] and S[i] <= 'Z') {
            cout << i + 1 << endl;
            return;
        }
    }
}

B - Trimmed Mean

ソートをして $ N \leq x \lt 4N $ の平均値を求める

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> X(5 * N);
    REP(i, 5 * N) cin >> X[i];
    sort(ALL(X));
    int ans = 0;
    REP(i, N, 4 * N) ans += X[i];
    printf("%.12lf\n", ans / (double)(3 * N));
}

C - LRUD Instructions 2

訪れた頂点をmapなどで持ちながらシミュレートを行い、すでに訪れたかどうかをチェックする

提出コード

void solve() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    map<pair<int, int>, int> mp;
    int cur_x = 0, cur_y = 0;
    mp[{cur_x, cur_y}] = 1;
    for (char c : S) {
        if (c == 'U') {
            cur_y++;
        }
        else if (c == 'D') {
            cur_y--;
        }
        else if (c == 'R') cur_x++;
        else if (c == 'L') cur_x--;
        if (mp.count({cur_x, cur_y})) {
            cout << "Yes" << endl;
            return;
        }
        mp[{cur_x, cur_y}] = 1;
    }
    cout << "No" << endl;
}

D - Flip Cards

$ i $ 番目のものを決めるときには $ i - 1 $ 番目のものを表裏どちらの状態にしたかのみに依存するので以下のDPで求めればいい
$ dp[i][j] := i $ 番目のものまで見たとき、$ i - 1 $ 番目の状態が $ j $ のときの場合の数

提出コード

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> num(2, vector<int>(N));
    REP(i, N) cin >> num[0][i] >> num[1][i];
    vector dp(N + 1, vector<mint>(2, 0));
    dp[0][0] = 1;
    dp[0][1] = 1;
    REP(i, 1, N) {
        REP(j, 2) {
            REP(k, 2) {
                if (num[j][i - 1] != num[k][i]) dp[i][k] += dp[i - 1][j];
            }
        }
    }
    cout << dp[N - 1][0] + dp[N - 1][1] << endl;
}

E - Find Permutation

与えられた条件を有向グラフとして考える
このグラフ上で長さが $ N - 1 $ のパスが存在すれば条件を満たすのでこれを判定する

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> X(M), Y(M);
    vector<vector<int>> g(N);
    REP(i, M) {
        cin >> X[i] >> Y[i];
        --X[i], --Y[i];
        g[X[i]].emplace_back(Y[i]);
    }
    auto res = topologicalSort(g);
    vector<int> dist(N, -1);
    dist[res[0]] = 0;
    for (auto x : res) {
        for (auto nv : g[x])
            chmax(dist[nv], dist[x] + 1);
    }
    int ma = *max_element(ALL(dist));
    dump(dist);
    if (ma != N - 1) cout << "No" << endl;
    else {
        cout << "Yes" << endl;
        vector<int> ans(N);
        REP(i, N) ans[res[i]] = i + 1;
        for (auto x : ans)
            cout << x << " ";
        cout << endl;
    }
}

F - Teleporter and Closed off

頂点 $ i $ を使わずに移動可能かどうかは 頂点 $ i $ を飛び越すような辺が存在すればよい
そのような辺は制約より、 $ i $ の前後 $ M $ 個の頂点に絞られるのでこれをすべて調べれば良い
頂点 $ 1 $ からの最短距離を $ d_1 $ 、$ N $ からの最短経路を $ d_2 $ とし、頂点 $ j $ から $ k $ への辺が存在するとき、そのコストは $ d_{1,j} + d_{N, k} + 1 $ となるのでその最小を答えればいい

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    Dijkstra<int> d1(N, INF), d2(N, INF);
    REP(i, N) {
        cin >> S[i];
        REP(j, M) if (S[i][j] == '1') {
            d1.make_edge(i, i + j + 1, 1);
            d2.make_edge(i + j + 1, i, 1);
        }
    }
    d1.solve(0);
    d2.solve(N - 1);
    dump(d1.cost);
    dump(d2.cost);
    REP(i, 1, N - 1) {
        int ans = INF;
        REP(j, max(0, i - (M - 1)), i) {
            REP(k, i + 1, min(N, i + 1 + (M - 1))) {
                if (k - j - 1 < M and S[j][k - j - 1] == '1') chmin(ans, d1.cost[j] + d2.cost[k] + 1);
            }
        }
        cout << (ans == INF ? -1 : ans) << " ";
    }
    cout << endl;
}