接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 217（ABC217）

AtCoder Beginner Contest 217（ABC217）

AtCoderBeginnerContest AtCoderBeginnerContest217 ABC ABC217

atcoder.jp

A - Lexicographic Order

文字列の比較をする
提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    if(S < T) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - AtCoder Quiz

予めsetに入れておいて、3つ消して最後に残ったものを出力
提出コード

void solve(){
    set<string> st;
    st.insert("ABC");
    st.insert("ARC");
    st.insert("AGC");
    st.insert("AHC");
    REP(i,3){
        string s;
        cin >> s;
        st.erase(s);
    }
    cout << *st.begin() << endl;
}

C - Inverse of Permutation

$ q_{p_i} = i $ となるので、これを出力
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> q(n);
    REP(i,n){
        cin >> p[i];
        q[p[i]-1] = i+1;
    }
    REP(i,n) cout << q[i] << " ";
    cout << endl;
}

D - Cutting Woods

すでに切られている位置をsetで管理する
番兵として $ 0, L $ を入れておく
$ x_i $ に一番近い前後の値を $ l, r $ とすると $ x_ i $ を含む長さは $ r - l $ となる
提出コード

void solve(){
    ll L, Q;
    cin >> L >> Q;
    set<int> st;
    st.insert(0);
    st.insert(L);
    REP(i,Q){
        int c, x;
        cin >> c >> x;
        if(c == 2){
            auto itr = st.lower_bound(x);
            auto itr2 = itr;
            itr2--;
            cout << (*itr - *itr2) << endl;
        }
        else{
            st.insert(x);
        }
    }
}

E - Sorting Queries

すでにソートされた要素の集合をpriority_queue、まだソートされていない集合をqueueで管理をする
クエリ2に答えるとき、ソートされた集合があればpriority_queueで一番小さい値を、そうでなければqueueの先頭の値を出力する
クエリ3でソートするときには、queueの値を全てpriority_queueに追加し、queueを空にすればいい
提出コード

void solve(){
    int Q;
    cin >> Q;
    priority_queue<int, vector<int>, greater<int>> pq;
    queue<int> que;
    REP(i,Q){
        int q;
        cin >> q;
        if(q == 1){
            int x;
            cin >> x;
            que.emplace(x);
        }
        else if(q == 2){
            if(!pq.empty()){
                cout << pq.top()<< endl;
                pq.pop();
            }
            else{
                cout << que.front() << endl;
                que.pop();
            }
        }
        else{
            while(!que.empty()){
                pq.emplace(que.front());
                que.pop();
            }
        }
    }
}

F - Make Pair

$ dp[l][r] := $ 区間 $ [l, r) $ の生徒だけを考えたときに条件を満たす答えの数として区間DPをする
$ l \lt i \lt r $ を満たす $ (l , i) $ペアにすることを考えると $ [l+1, i-1] $ と $ [i+1, r-1] $ の組合せはそれぞれ $ dp[l+1][i], \; dp[i+1][r] $ となり、この中のペアをどの順で選ぶかが $ _{\frac{r-l}{2}} C _{\frac{r - (i+1)}{2}} $ 通りあるので $ dp[l+1][i] \times dp[i+1][r] \times _{\frac{r-l}{2}} C _{\frac{r - (i+1)}{2}} $ となる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    N *= 2;
    bc.init(N+10);
    vector<vector<int>> relation(N, vector<int>(N));
    REP(i,M){
        int a, b;
        cin >> a >> b;
        relation[--a][--b] = 1;
        relation[b][a] = 1;
    }
    vector dp(N+1, vector<mint>(N+1, 0));
    vector used(N+1, vector(N+1, 0));
    auto memo = [&](auto && self, int l, int r) -> mint{
        if(l == r) return 1;
        if(l > r) return 0;
        if((r - l) & 1) return 0;
        if(used[l][r]) return dp[l][r];
        used[l][r] = 1;
        auto &res = dp[l][r];
        for(int i=l+1;i<r;i+=2){
            if(!relation[l][i]) continue;
            res += self(self, l+1, i) * self(self, i+1, r) * bc.nCr((r-l)/2, (r-(i+1))/2);
        }
        return res;
    };
    cout << memo(memo, 0, N) << endl;
}

G - Groups

$ dp[i][j] := i $ 人を条件を満たすように $ j $ 個のグループに分ける方法の数としてDPをする
$ i $ 番目の人を追加するとき、新しくグループを作ってその中に入れるか、すでにある $ j $ 個のグループの中のどれかに入れる方法がある
前者の場合、$ i -1 $ 人が $ j - 1 $ 個のグループを作っているので$ dp[i][j] = dp[i-1][j-1] $ となる
後者の場合、入ることのできるグループの個数を $ k $ とすると$ i - 1 $ 人が $ j $ 個のグループを作っているので $ dp[i][j] = dp[i-1][j] \times k $ となる
$ i $ が入ることのできないグループは $ 1 \leq x \leq i - 1 $ のうち、$ M $ で割った余りが $ i $ と一致するような $ x $ がいるグループとなる
そのような $ x $ は全て別のグループに存在し、そのグループの数は $ j - \lfloor \frac{i - 1}{M} \rfloor $ となるので $ dp[i][j] = dp[i-1][j-1] + ( j - \lfloor \frac{i - 1}{M} \rfloor) dp[i-1][j] $ となる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector dp(5050, vector<mint>(5050, 0));
    dp[0][0] = 1;
    for(int i=1;i<5050;i++){
        for(int j=1;j<=i;j++){
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * (j - (i - 1) / M) ;
        }
    }
    REP(i,N) cout << dp[N][i+1] << endl;
}