AtCoder Beginner Contest 246（ABC246）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 246での成績：1161位
パフォーマンス：1412相当
レーティング：1508→1498 (-10) :(#AtCoder #ABC246 https://t.co/DyNTjf3Vkz

— ボンド@競プロ (@bond_cmprog) April 2, 2022

A - Four Points

$ x $ は $ x1, x2, x3 $ のうち、一つしか使われていない値になる
$ y $ についても同様

提出コード

void solve(){
    int x1, x2, x3, y1, y2, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    cout << (x1^x2^x3) << " " << (y1^y2^y3) << endl;
}

B - Get Closer

$ ( \frac{A}{\sqrt{A^2 + B^2}}, \frac{B}{\sqrt{A^2 + B^2}} ) $ が答え

提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    printf("%.12lf %.12lf\n",  (double)A / hypot(A, B), (double)B / hypot(A, B));
}

C - Coupon

$ A_i \geq X $ の間はどれに使ってもいい
すべての $ i $ について $ A_i \lt X $ となった場合、降順ソートをして使えるだけ使う

提出コード

void solve(){
    ll N, K, X;
    cin >> N >> K >> X;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    ll ans = 0;
    REP(i,N){
        if(A[i] / X <= K){
            K -= A[i] / X;
            A[i] = A[i] % X;
        }
        else{
            A[i] -= K * X;
            K = 0;
        }
    }

    sort(ALL(A));
    reverse(ALL(A));
    REP(i,N){
        if(K > 0) K--;
        else ans += A[i];
    }
    cout << ans << endl;
}

D - 2-variable Function

$ 0 \leq a, b \leq 10^6 $ となるので片方は全探索できる
片方を固定した場合、二分探索で $ N $ 以上となる最小の $ X $ になる値を求めることができるのでその中で最小のものが答え

提出コード

void solve(){
    ll N;
    cin >> N;
    ll ans = 9LL * LINF;
    auto f = [](ll a, ll b) ->ll{
        return a*a*a + a*a*b + a*b*b + b*b*b;
    };

    REP(a,1e6+10){
        ll l = -1, r = 1e6+10;
        while(r - l > 1){
            ll m = (r + l) >> 1;
            if(f(a, m) >= N) r = m;
            else l = m;
        }
        chmin(ans, f(a, r));
    }
    cout << ans << endl;
}

E - Bishop 2

$ dist[dir][x][y] := $ マス $ (x, y) $ に方向 $ dir $ でたどり着いたときの最短距離としてダイクストラを行う
$ dir $ と同一の方向に進むならコストは $0$、それ以外ならコストは $1$ として最短経路を求めればいい（01BFS）

提出コード

void solve(){
    int N;
    cin >> N;
    int Ax, Ay, Bx, By;
    cin >> Ax >> Ay >> Bx >> By;
    --Ax, --Ay, --Bx, --By;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    vector dist(5, vector(N, vector(N, INF)));
    int dx[4] = {1, 1, -1, -1};
    int dy[4] = {1, -1, 1, -1};
    using T = tuple<int, int, int, int>;
    priority_queue<T, vector<T>, greater<T>> q;
    REP(d, 4){
        dist[d][Ax][Ay] = 0;
        q.emplace(0, 4, Ax, Ay);
    }
    dist[4][Ax][Ay] = 0;
    while(!q.empty()){
        auto [c, dir, x, y] = q.top(); q.pop();
        if(c < dist[dir][x][y]) continue;
        REP(d, 4){
            int nx = x + dx[d], ny = y + dy[d];
            if(nx < 0 or nx >= N or ny < 0 or ny >= N or S[nx][ny] == '#') continue;
            if(d == dir){
                if(chmin(dist[d][nx][ny], c)) q.emplace(dist[d][nx][ny], d, nx, ny);
            }
            else{
                if(chmin(dist[d][nx][ny], c + 1)) q.emplace(dist[d][nx][ny], d, nx, ny);
            }
        }
    }
    int ans = INF;
    REP(d, 4){
        chmin(ans, dist[d][Bx][By]);
    }
    cout << (ans == INF ? -1 : ans) << endl;
}