AtCoder Beginner Contest 277（ABC277）

atcoder.jp

A - ^{-1}

$ P_i = X $ となる $ i $ を答える

提出コード

void solve() {
    int N, X;
    cin >> N >> X;

    vector<int> P(N);
    REP(i, N) cin >> P[i];
    REP(i, N) if (P[i] == X) {
        cout << i + 1 << endl;
        return;
    }
}

B - Playing Cards Validation

すべての条件を満たすかどうかを丁寧にチェックする

提出コード

void solve() {
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i, N) cin >> S[i];
    set<char> cond1 = {'H', 'D', 'C', 'S'};
    set<char> cond2 = {'A', '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K'};
    set<string> st;
    bool ok = true;
    REP(i, N) {
        if (!cond1.count(S[i][0])) ok = false;
        if (!cond2.count(S[i][1])) ok = false;
        st.insert(S[i]);
    }
    if (st.size() != N) ok = false;
    cout << (ok ? "Yes" : "No") << endl;
}

C - Ladder Takahashi

BFSをして訪れた頂点の中で最大の頂点を出力
頂点の番号が大きいのでmapなどで管理する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    map<int, vector<int>> mp;
    REP(i, N) {
        cin >> A[i] >> B[i];
        mp[A[i]].emplace_back(B[i]);
        mp[B[i]].emplace_back(A[i]);
    }
    map<int, int> used;
    queue<int> q;
    q.emplace(1);
    used[1] = 1;
    while (!q.empty()) {
        auto x = q.front();
        q.pop();
        for (auto nx : mp[x]) {
            if (used.count(nx)) continue;
            q.emplace(nx);
            used[nx] = 1;
        }
    }
    cout << (used.rbegin()->first) << endl;
}

D - Takahashi's Solitaire

条件を満たす区間を考えると、区間の中のものはすべて取ってしまえばいいので各区間の中で総和が最大のものを求める
最終的な答えは手札の総和から区間の総和の最大を引いたものになる
あとは座圧などをしたあとに愚直に条件を満たす区間の総和を求めていけばいい

提出コード

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    Compress<ll> cmp;
    REP(i, N) {
        cin >> A[i];
        cmp.add(A[i] % M);
        cmp.add(A[i] % M + M);
    }
    cmp.add(LINF);
    cmp.build();
    int sz = cmp.size();
    vector<ll> sum(sz);
    REP(i, N) {
        sum[cmp.get(A[i] % M)] += A[i];
        sum[cmp.get(A[i] % M + M)] += A[i];
    }
    ll ans = LINF;
    ll all = accumulate(ALL(A), 0LL);
    ll cur_sum = 0;
    ll cur_num = -1;
    REP(i, sz) {
        if (cur_num == -1) {
            cur_num = cmp[i];
            cur_sum += sum[i];
        }
        else {
            if (cur_num + 1 == cmp[i]) {
                cur_sum += sum[i];
                cur_num++;
            }
            else {
                cur_sum = sum[i];
                cur_num = cmp[i];
            }
        }
        chmin(ans, max(0LL, all - cur_sum));
    }
    cout << ans << endl;
}

E - Crystal Switches

$ dist[i][j] := $ スイッチの状態が $ i $ のときに頂点 $ j $ にいるための最小移動回数とする
上記を拡張したグラフ上でダイクストラ（もしくは01-BFS）で求める

提出コード

void solve() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<P>> g(N);
    REP(i, M) {
        int u, v, a;
        cin >> u >> v >> a;
        --u, --v;
        g[u].emplace_back(v, a);
        g[v].emplace_back(u, a);
    }
    map<int, int> mp;
    REP(i, K) {
        int s;
        cin >> s;
        mp[--s] = 1;
    }
    using T = tuple<ll, int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    vector dp(2, vector<ll>(N, LINF));
    dp[0][0] = 0;
    pq.emplace(0, 0, 0);
    while (!pq.empty()) {
        auto [dist, v, sw] = pq.top();
        pq.pop();
        if (dist < dp[sw][v]) continue;
        for (auto [nv, a] : g[v]) {
            if (a ^ sw) {
                if (chmin(dp[sw][nv], dp[sw][v] + 1)) {
                    pq.emplace(dp[sw][nv], nv, sw);
                }
            }
        }
        if (mp.count(v)) {
            if (chmin(dp[sw ^ 1][v], dp[sw][v])) {
                pq.emplace(dp[sw ^ 1][v], v, sw ^ 1);
            }
        }
    }
    ll dist = min(dp[0][N - 1], dp[1][N - 1]);
    cout << (dist == LINF ? -1 : dist) << endl;
}