接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 181（ABC181）

AtCoder Beginner Contest 181（ABC181）

AtCoderBeginnerContest AtCoderBeginnerContest181 ABC ABC181

atcoder.jp

A - Heavy Rotation

$ n $ の偶奇で場合分け
提出コード

void solve(){
    int n;
    cin >> n;
    if(n & 1) cout << "Black" << endl;
    else cout << "White" << endl;
}

B - Trapezoid Sum

$ A_i , B_i $の和は等差数列の和で$ \frac{(B_i - A_i + 1) \times (A_i + B_i)}{2} $で求められる
よって各$ A_i, B_i $の和の総和を求めればいい
提出コード

void solve(){
    int N;
    cin >> N;
    ll sum = 0;
    REP(i,N){
        ll a, b;
        cin >> a >> b;
        sum += (b - a + 1) * (a + b) / 2;
    }
    cout << sum << endl;
}

C - Collinearity

3点が一直線上にあるかどうかは直線$ (i, j) $と直線$ (i, k) $が同じ傾きかどうかで判定できる
よって3点$(i, j, k) $を全探索して傾きが一致するものがあるかどうかを判定すればいい
直線$ (i, j) $の傾きを$ \frac{y_1}{x_1} $、直線$ (i, k) $の傾きを$ \frac{y_2}{x_2} $とする
そうすると、分母を払うと$ x_1 y_2 = x_2 y_1 $で判定ができて実装が楽になる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    bool ok = false;
    REP(i,N) for(int j=i+1;j<N;j++) for(int k=j+1;k<N;k++){
        int x1 = x[i] - x[j], y1 = y[i] - y[j];
        int x2 = x[i] - x[k], y2 = y[i] - y[k];
        int g1 = gcd(abs(x1), abs(y1));
        int g2 = gcd(abs(x2), abs(y2));
        x1 /= g1, y1 /= g1, x2 /= g2, y2 /= g2;
        if(x1 == 0) y1 = 1;
        if(y1 == 0) x1 = 1;
        if(x1 < 0) x1 *= -1, y1 *= -1;
        if(x2 == 0) y2 = 1;
        if(y2 == 0) x2 = 1;
        if(x2 < 0) x2 *= -1, y2 *= -1;
        if(x1 == x2 and y1 == y2) ok = true;
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

D - Hachi

$ |S| \geq 3 $のとき、下3桁で8の倍数が作れれば良い
そのため、$ S $の1~9の個数をカウントしておき、3桁の8の倍数を全探索し、これが作れれば良い
$ |S| = 1 $と$ |S| = 2 $のときは場合分けする必要がある
提出コード

void solve(){
    string s;
    cin >> s;
    vector<int> cnt(10);
    REP(i,s.size()){
        cnt[s[i]-'0']++;
    }
    if(s.size() == 1){
        if(s == "8") cout << "Yes" << endl;
        else cout << "No" << endl;
        return;
    }
    if(s.size() <= 2){
        for(int i=16;i<100;i+=8){
            int t = i % 10;
            int u = i / 10;
            if((s[0] - '0' == t and s[1] - '0' == u) or(s[0] - '0' == u and s[1] - '0' == t)){
                cout << "Yes" << endl;
                return;
            }
        }
        cout << "No" << endl;
        return;
    }
    for(int i=104;i<=1000;i+=8){
        bool ok = true;
        int cur = i;
        vector<int> tmp(10);
        while(cur > 0){
            tmp[cur%10]++;
            cur /= 10;
        }
        REP(i,10) if(cnt[i] < tmp[i]) ok = false;
        if(ok){
            cout << "Yes" << endl;
            // dump(i);
            return;
        }
    }
    cout << "No" << endl;
}

E - Transformable Teacher

添字で頭が壊れた
$ W_i $を$ H $に追加したものをソートして考えると昇順にペアを作っていけばいい
そのため、$ W_i $をどこに追加するかは二分探索で求めることができる
隣り合う要素の和の累積和を取って上げると、$ W_i $を追加してできるペアとその前後の総和の最小値を求めればいい
$ W_i $を追加した時にその前後で累積和の偶奇が変わるので注意
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> H(N), W(M);
    REP(i,N) cin >> H[i];
    REP(i,M) cin >> W[i];
    sort(H.begin(), H.end());
    vector<ll> cum_odd(N+1);
    vector<ll> cum_even(N+1);
    REP(i,N-1){
        if(i & 1){
            cum_even[i+1] = cum_even[i] + H[i+1] - H[i];
            cum_odd[i+1] = cum_odd[i];
        }
        else{
            cum_even[i+1] = cum_even[i];
            cum_odd[i+1] = cum_odd[i] + H[i+1] - H[i];
        }
    }
    ll ans = LINF;
    REP(i,M){
        {
            int idx = upper_bound(H.begin(), H.end(), W[i]) - H.begin();
            if(idx & 1){
                if(idx == N) chmin(ans, abs(W[i] - H[idx-1]) + cum_odd[idx-1]);
                else chmin(ans, abs(W[i] - H[idx-1]) + cum_odd[idx-1] + cum_even[N-1] - cum_even[idx]);
            }
            else{
                if(idx == 0) chmin(ans, H[idx] - W[i] + cum_even[N-1] - cum_even[idx]);
                else chmin(ans, H[idx] - W[i] + cum_odd[idx-1] + cum_even[N-1] - cum_even[idx]);
            }
        }
    }
    cout << ans << endl;
}

F - Silver Woods

これすき、解説ACした
$ y = 100, y = -100 $の二直線と各頂点を結んで二直線の間に線（直線じゃなくても良い）が結ばれたとき、各頂点間の距離で最大のところを円の直径とすれば円はゴールまで通る事ができる
よって二直線も頂点とみなし、各頂点間の距離が小さい順にUnionFindなどで頂点集合をmergeし、$y = 100 $と$ y = -100 $が同じ連結成分となった時、最大の距離の半分が求めたい$ r $となる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    vector<tuple<double, int, int>> vt;
    int y1 = N, y2 = N+1;
    REP(i,N){
        vt.emplace_back(y[i] + 100, i, y1);
        vt.emplace_back(100 - y[i], i, y2);
        for(int j=i+1;j<N;j++){
            vt.emplace_back(hypot(x[i]-x[j], y[i]-y[j]), i, j);
        }
    }
    sort(vt.begin(), vt.end());
    UnionFind uf(N+2);
    for(auto [d, i, j] : vt){
        uf.unite(i, j);
        if(uf.issame(y1, y2)){
            printf("%.12lf\n", d / 2.0);
            return;
        }
    }
}