AtCoder Regular Contest 106（ARC106）

atcoder.jp

う笑
Bondo416さんのAtCoder Regular Contest 106での成績：1977位
パフォーマンス：962相当
レーティング：1507→1463 (-44) :(#AtCoder #ARC106 https://t.co/9f28Lt2oRY

— ボンド@競プロ (@bond_cmprog) October 24, 2020

A - 106

、の組み合わせを全探索しその和がと一致するか全探索すればいい
正の整数なので0は入らない（無限にWA吐いた）
提出コード

void solve(){
    ll N;
    cin >> N;
    for(int i=1;i<38;i++) for(int j=1;j<28;j++){
        ll t = 1;
        ll f = 1;
        {
            ll tmp = 0;
            while(t <= LINF / (ll)3 and tmp < i){
                t *= 3;
                tmp++;
            }
            if(tmp < i) break;
        }
        {
            ll tmp = 0;
            while(f <= LINF / (ll)5 and tmp < j){
                f *= 5;
                tmp++;
            }
            if(tmp < j) break;
        }
        if(t + f == N){
            cout << i << " " << j << endl;
            return;
        }
    }
    cout << -1 << endl;
}

B - Values

操作を考えると、操作を行った前後の総和は不変であることがわかる
そのため、各連結成分においてである必要がある
これを満たしている時、適切に操作を行うことで各頂点の値をに変更できる（解説参照）
よって、各連結成分ごとにを満たしているかチェックすればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> a(N), b(N);
    REP(i,N) cin >> a[i];
    REP(i,N) cin >> b[i];
    UnionFind uf(N);
    REP(i,M){
        int c, d;
        cin >> c >> d;
        --c, --d;
        uf.unite(c, d);
    }

    vector<ll> sum_a(N), sum_b(N);
    REP(i,N){
        sum_a[uf.root(i)] += a[i];
        sum_b[uf.root(i)] += b[i];
    }
    bool ok = true;
    REP(i,N){
        if(sum_a[i] != sum_b[i]){
            dumps(i);
            ok = false;
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Solutions

まず問題の操作を考えると、これは区間スケジューリングを求める操作と同一
よって高橋くんのプログラムは最適解を出力するため、必ず青木くん以上の個数を出力する
そのためのときは-1となる
の時、高橋くんがN個取って青木くんが0個の時のみ条件を満たすが青木くんは必ず1個以上取ることができるのでこの時も-1となる
の時、高橋くんがN個取って青木くんが1個のとき条件を満たすが、高橋くんがN個取れる時全ての区間は交わっていないので、青木くんもN個となり-1となる
ただし、の時はそれぞれ1個取れば条件を満たすことができる
それ以外の場合、高橋くんがM+1個取って、青木くんが1個だけ取れば条件を満たす
よって高橋くんがM+1取った後に青木くんが最初に一番大きい区間を取って、残りはその区間に入るような区間を作れば青木くんは1だけ取ることができるので条件を満たすことができる
の時、すべての区間が被らないようにすれば条件を満たすことができる
提出コード

const ll inf = (int)1e7;
void solve(){
    int N, M;
    cin >> N >> M;
    if(N == 1 and M == 0){
        cout << 1 << " " << 2 << endl;
        return;
    }
    if(M < 0 or N == abs(M) or (N >= 2 and N-1 == abs(M))){
        cout << -1 << endl;
        return;
    }
    vector<pair<ll, ll>> ans;
    if(M >= 0){
        ll cur = 2;
        REP(i,abs(M)){
            ans.emplace_back(cur, cur+1);
            cur += 2;
        }
        if(N > M){
            ans.emplace_back(1, inf+1);
            cur++;
            while(ans.size() < N){
                ans.emplace_back(cur, inf+cur);
                cur++;
            }
        }
    }
    for(auto [l, r] : ans) cout << l << " " << r << endl;
}