接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 212（ABC212）

AtCoder Beginner Contest 212（ABC212）

AtCoderBeginnerContest AtCoderBeginnerContest212 ABC ABC212

atcoder.jp

A - Alloy

問題文の条件を判定する
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    if(0 < A and B == 0) cout << "Gold" << endl;
    else if(A == 0 and 0 < B) cout << "Silver" << endl;
    else cout << "Alloy" << endl;
}

B - Weak Password

弱い条件を満たさなければ Strong そうでなければ Weak
提出コード

void solve(){
    string A;
    cin >> A;
    if(A[0] == A[1] and A[1] == A[2] and A[2] == A[3]){
        cout << "Weak" << endl;
        return;
    }
    bool weak = true;
    REP(i,3){
        if(A[i] == '9'){
            if(A[i+1] != '0'){
                weak = false;
            }
        }
        else if((A[i] - '0' + 1) != (A[i+1] - '0')) weak = false;
    }
    cout << (weak ? "Weak" : "Strong") << endl;
}

C - Min Difference

$ A_i $ を固定したとき、$ B $ の要素で $ A_i $ に近いものを調べればいい
$ B $ を予めソートしておきlower_boundで求めた値を $ B_j $ とすると、$ B _j $ を含めた前後の値を実際に計算しその最小値を求めればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(N), B(M);
    REP(i,N) cin >> A[i];
    REP(i,M) cin >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    ll ans = LINF;
    REP(i,N){
        int idx = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
        if(idx < M) chmin(ans, abs(A[i] - B[idx]));
        if(idx + 1 < M) chmin(ans, abs(A[i] - B[idx+1]));
        if(idx - 1 >= 0) chmin(ans, abs(A[i] - B[idx-1]));
    }
    cout << ans << endl;
}

D - Querying Multiset

$ i $ 番目のクエリまでに加算された $ X_i $ の総和を $ sum_i $ とする
$ i $ 番目のクエリのときに $ j $ 番目に追加された $ X_j $ を取り出したときの値は $ X_j + sum_i - sum_j $ となる
実際の実装では $ sum $ を 今までの累積和 $ sum_i $ として持っておき、追加するときにその時点での累積和（ $ sum_j $ ）を $ X_j $ から引いておき、出力する際に $ sum ( = sum_i ) $ を加算することで上記と同様のことができる
提出コード

void solve(){
    int Q;
    cin >> Q;
    ll sum = 0;
    map<ll, ll> mp;
    while(Q--){
        int q;
        ll X;
        cin >> q;
        if(q == 1){
            cin >> X;
            mp[X-sum]++;
        }
        else if(q == 2){
            cin >> X;
            sum += X;
        }
        else{
            ll num = mp.begin() -> first;
            cout << num + sum << endl;
            mp[num]--;
            if(mp[num] == 0) mp.erase(num);
        }
    }
}

E - Safety Journey

$ dp[i][j] := i $ 日目に都市 $ j $ にいる相違なる旅の数としてDPをする
$ sum_i = \sum_{j=0}^{j=N-1} dp[i][j] $ とすると $ M = 0 $ の場合、$ dp[i+1][j] = sum_i - dp[i][j] $ となる
$ M \gt 0 $ の場合もほぼ同様で、都市 $ i $ と結ばれていない頂点 $ j $ の集合を考えると $ dp[i+1][j] = sum_i - dp[i][j] - \sum_{j} dp[i][j] $ となり全体で $ O(K(N+M)) $ となる
提出コード

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> U(M), V(M);
    REP(i,M){
        cin >> U[i] >> V[i];
        --U[i], --V[i];
    }
    vector<mint> dp(N);
    dp[0] = 1;
    REP(_,K){
        auto nxt = vector<mint>(N);
        mint sum = 0;
        REP(i,N) sum += dp[i];
        REP(i,N) nxt[i] += sum - dp[i];
        REP(i,M){
            nxt[U[i]] -= dp[V[i]];
            nxt[V[i]] -= dp[U[i]];
        }
        swap(dp, nxt);
    }
    cout << dp[0] << endl;
}

G - Power Pair

法 $ P $ の原始根を $ r $ とし、 $ 1 \leq a, b \leq P - 1 $ に対して $ x \equiv r^{a} , y \equiv r^b \pmod{P} $ とする
$ x^n \equiv y \pmod{P} $
$ \Leftrightarrow r^{an} \equiv r^b \pmod{P-1} $
$ \Leftrightarrow an \equiv b \pmod{P-1} $
となり、$ an \equiv b \pmod{P-1} $ を満たす正整数$ n $ が存在するような $ (a, b) $ を数えればいい
これは $ \sum_{a=1}^{P-1} \frac{P-1}{gcd(P-1, a)} $ で求められるが、$ O(P) $ となる
そのため $ g = gcd(P-1, a) $ となるような $ g $ を満たす $ a ( 1 \leq a \leq P - 1) $ の個数を $ f(g) $ とすると $ \sum _{g} \frac{P-1}{g} f(g) $ となる
$ g $ は $ P - 1 $ の約数であり、$ f(g) $ は $ P - 1 $ の約数の数 $ d $ に対し、$ O(d^2) $ で求められるので全体で $ O( \sqrt{P} + d^2 ) $ で求めることができる
提出コード

void solve(){
    ll P;
    cin >> P;
    P--;
    vector<ll> div;
    for(ll i=1;i*i<=P;i++){
        if(P % i == 0){
            div.emplace_back(i);
            if(P != i * i) div.emplace_back(P / i);
        }
    }
    sort(div.rbegin(), div.rend());
    int sz = div.size();
    vector<ll> sum(sz);
    REP(i,sz){
        sum[i] = P / div[i];
        REP(j,i) if(div[j] % div[i] == 0) sum[i] -= sum[j];
    }
    mint ans = 1;
    REP(i,sz) ans += mint(P / div[i]) * sum[i];
    cout << ans << endl;
}