AtCoder Beginner Contest 225（ABC225）

atcoder.jp

Bondo416さんのUNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)での成績：1047位
パフォーマンス：1402相当
レーティング：1550→1536 (-14) :(#AtCoder #UNICORNプログラミングコンテスト2021(ABC225) https://t.co/my16148TUx

— ボンド@競プロ (@bond_cmprog) October 30, 2021

A - Distinct Strings

next_permutationで数える

提出コード

void solve(){
    string S;
    cin >> S;
    set<string> st;
    sort(ALL(S));
    do{
        st.insert(S);
    }while(next_permutation(ALL(S)));
    cout << (int)st.size() << endl;
}

B - Star or Not

次数が $ N - 1 $ の頂点が存在するかどうか

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> deg(N);
    REP(i,N-1){
        int a, b;
        cin >> a >> b;
        --a, --b;
        deg[a]++, deg[b]++;
    }
    bool ok = false;
    REP(i,N) if(deg[i] == N - 1) ok = true;
    cout << (ok ? "Yes" : "No") << endl;
}

C - Calendar Validator

$ B[i][j] + 1 = B[i][j+1] $ かつ $ B[i][j] + 7 = B[i+1][j] $ を満たせばいい
ただし、7 8 のようなものは存在しないのでこの場合はNoとなる

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<vector<ll>> A(N, vector<ll>(M));
    REP(i,N) REP(j,M) cin >> A[i][j];
    bool ok = true;
    REP(i,N-1) REP(j,M) if(A[i][j] + 7 != A[i+1][j]) ok = false;
    REP(i,N) REP(j,M-1){
        if(A[i][j] + 1 != A[i][j+1]) ok = false;
        if(A[i][j] % 7 == 0 and  A[i][j+1] % 7 == 1) ok = false;
    }
    cout << (ok ? "Yes" : "No") << endl;
}

D - Play Train

ある電車 $ i $ の前に連結している電車と後ろに連結している電車を管理すればいい
クエリ1、クエリ2は $ O(1) $ で更新でき、クエリ3は制約から 電車$ x $ から先頭までたどり、その後先頭から最後尾の電車まで順に出力すればいい

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<pair<int, int>> node(N, {-1, -1});

    while(Q--){
        int q, x, y;
        cin >> q >> x;
        if(q == 1 or q == 2){
            cin >> y;
            --y;
        }
        --x;
        if(q == 1){
            node[x].second = y;
            node[y].first = x;
        }
        else if(q == 2){
            node[x].second = -1;
            node[y].first = -1;
        }
        else{
            deque<int> dq;
            dq.push_back(x);
            {
                int cur = node[x].first;
                while(cur != -1){
                    dq.push_front(cur);
                    cur = node[cur].first;
                }
            }
            {
                int cur = node[x].second;
                while(cur != -1){
                    dq.push_back(cur);
                    cur = node[cur].second;
                }
            }
            cout << dq.size();
            while(!dq.empty()){
                cout << " " << dq.front() + 1;
                dq.pop_front();
            }
            cout << endl;
        }
    }
}

E - フ

$ i $ 個目のフの字を選ぶと直線 $ (x_i - 1, y_i) $ と $ (x_i, y_i - 1) $ の間に含まれる頂点は選ぶことができない（端点は除く）
この直線を偏角で置き換えると、左端と右端の区間に置き換えることができ、この区間上で区間スケジューリングとして解くことで最大値を求めることができる

提出コード

void solve(){
    int N;
    cin >> N;
    vector<long double> X(N), Y(N);
    REP(i,N) cin >> X[i] >> Y[i];
    vector<pair<long double, long double>> arg(N);
    REP(i,N){
        arg[i] = {atan2(Y[i], X[i] - 1), atan2(Y[i] - 1, X[i])};
    }
    sort(ALL(arg));
    int ans = 0;
    long double pre = -1;
    for(auto [r, l] : arg){
        if(pre <= l){
            ans++;
            pre = r;
        }
    }
    cout << ans << endl;
}