接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 209（ABC209）

AtCoder Beginner Contest 209（ABC209）

AtCoderBeginnerContest AtCoderBeginnerContest209 ABC ABC209

atcoder.jp

A - Counting

ミスが怖いのでfor文で数える
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    int ans = 0;
    for(int i=A;i<=B;i++) ans++;
    cout << ans << endl;
}

B - Can you buy them all?

問題文のとおりに値引きしたあとの総和が $ X $ 以下かどうか
提出コード

void solve(){
    int N, X;
    cin >> N >> X;
    vector<int> A(N);
    ll sum = 0;
    REP(i,N){
        cin >> A[i];
        if(i & 1) A[i]--;
        sum += A[i];
    }
    cout << (sum <= X ? "Yes" : "No") << endl;
}

C - Not Equal

難しくない？
小さい方が制約がきついので小さい順に決めていく
$ A_i $ の決め方は、$ C_i $ 通りからすでに決めた $ i - 1 $ 通り除いたもになるので、その総積が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> C(N);
    REP(i,N) cin >> C[i];
    sort(C.begin(), C.end());
    mint ans = 1;
    REP(i,N){
        ans *= max(0LL, C[i] - i);
    }
    cout << ans << endl;
}

D - Collision

頂点 $ (c_i, d_i) $ 間の距離の偶奇がわかればいい
これはLCAを利用することで木の二頂点間の距離を求めることができる
木は二部グラフなので、頂点同士が同じ色かどうかでも求めることができる
提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<vector<int>> g(N);
    REP(i,N-1){
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    LCA<vector<vector<int>>> lca(g);
    lca.build();
    while(Q--){
        int c, d;
        cin >> c >> d;
        --c, --d;
        int dist = lca.dist(c, d);
        if(dist & 1) cout << "Road" << endl;
        else cout << "Town" << endl;
    }
}

E - Shiritori

解説AC、後退解析っていうらしい
a ~ z、A ~ Zから3文字選んだものを頂点として、 $ 52^3 $ の頂点からなる有向グラフで考える
ある頂点からスタートした人が勝つか負けるか、もしくは引き分けかを求める
その頂点から辺が出ていないものは負け、その頂点から出ている辺がすべて勝ちへの頂点へ繋がっているなら負け、一つでも負ける頂点へ繋がっているなら勝ち、のようになる
また、上記のいずれでもないものは引き分けになる
これを勝ち負けが決まっているところから順に、その頂点へ向かう辺を持つ頂点の勝敗を調べていく
提出コード

const int NODE_NUM = 52 * 52 * 52;

void solve(){
    int N;
    cin >> N;
    vector<pair<int, int>> edge(N);
    vector<vector<int>> g(NODE_NUM);
    vector<int> deg(NODE_NUM);
    map<char, int> mp;
    int num = 0;
    for(char c='a';c<='z';c++) mp[c] = num++;
    for(char c='A';c<='Z';c++) mp[c] = num++;
    auto toNode = [&](char c1, char c2, char c3){
        return mp[c1] * 52 * 52 + mp[c2] * 52 + mp[c3];
    };
    REP(i,N){
        string S;
        cin >> S;
        int sz = S.size();
        int from = toNode(S[0], S[1], S[2]);
        int to = toNode(S[sz-3], S[sz-2], S[sz-1]);
        edge[i] = {from, to};
        g[to].emplace_back(from);
        deg[from]++;
    }
    vector<int> ans(NODE_NUM, -1);
    queue<int> q;
    REP(i,NODE_NUM) if(deg[i] == 0){
        ans[i] = 0;
        q.emplace(i);
    }
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(auto nv : g[cur]) if(ans[nv] == -1){
            deg[nv]--;
            if(ans[cur] == 0){
                ans[nv] = 1;
                q.emplace(nv);
            }
            else if(deg[nv] == 0){
                ans[nv] = 0;
                q.emplace(nv);
            }
        }
    }
    for(auto [from, to] : edge){
        if(ans[to] == -1) cout << "Draw" << endl;
        else if(ans[to] == 0) cout << "Takahashi" << endl;
        else cout << "Aoki" << endl;
    }
}