AtCoder Beginner Contest 180（ABC180）

atcoder.jp

初黄パフォわーい
Bondo416さんのAtCoder Beginner Contest 180での成績：169位
パフォーマンス：2135相当
レーティング：1411→1507 (+96) :)
Highestを更新しました！#AtCoder #ABC180 https://t.co/0ZUE7Jw7Gv

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

A - box

制約的に負にならないのでをそのまま出力
提出コード

void solve(){
    int N, A, B;
    cin >> N >> A >> B;
    cout << N - A + B << endl;
}

B - Various distances

チェビシェフ距離の絶対値取り忘れて1WA吐いた（反省）
定義どおりに求めたものを出力
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> x(N);
    REP(i,N) cin >> x[i];
    ll man = 0;
    ll eu = 0;
    ll ch = 0;
    REP(i,N){
        man += abs(x[i]);
        eu += abs(x[i]) * abs(x[i]);
        chmax(ch, abs(x[i]));
    }
    double e = sqrt(eu);
    printf("%lld\n", man);
    printf("%.12lf\n", e);
    printf("%lld\n", ch);
}

C - Cream puff

の約数を求めればいい
これはでできる
提出コード

vector<ll> divisor(ll n){
    vector<ll> res;
    for(ll i=1; i*i <= n; i++){
        if(n % i == 0){
            res.push_back(i);
            if(i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

void solve(){
    ll N;
    cin >> N;
    auto res = divisor(N);
    sort(res.begin(), res.end());
    for(auto x : res) cout << x << endl;
}

D - Takahashi Unevolved

倍する操作は最大でも60回程度までしか出来ない
また倍する操作は後になればなるほど損になるので最初に何回か行った後足す操作を行えばいい
そのため、最初の操作の回数を全探索し、後者の操作は割り算で求められる
提出コード

void solve(){
    ll X, Y, A, B;
    cin >> X >> Y >> A >> B;
    ll ans = 0;
    REP(i,61){
        ll cur = X;
        int cnt = 0;
        while(cur <= Y/A and cnt < i){
            cur *= A;
            cnt++;
        }
        if(cur >= Y or cnt < i) continue;
        ll tmp = cnt + (Y - cur - 1) / B;
        // dumps(i, cur, cnt, tmp, (Y-cur-1)/B);
        chmax(ans, tmp);
    }
    cout << ans << endl;
}

E - Traveling Salesman among Aerial Cities

Traveling Salesman ProblemをbitDPでやる方法がわかっていればコストの部分を問題に合わせれば答えが求められる
今いる街がで、過去に訪れた街の状態がの時の最小コストとしてbitDPをすればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> X(N), Y(N), Z(N);
    REP(i,N) cin >> X[i] >> Y[i] >> Z[i];
    vector<vector<ll>> dp(N, vector<ll>((1 << N)+10, LINF));
    dp[0][0] = 0;
    for(int i=1;i<(1<<N);i++){
        REP(j,N) if(i >> j & 1){
            REP(k,N){
                ll cost = dp[j][i-(1<<j)] + abs(X[k] - X[j]) + abs(Y[k] - Y[j]) + max(0, Z[k] - Z[j]);
                chmin(dp[k][i], cost);
            }
        }
    }
    cout << dp[0][(1<<N)-1] << endl;
}