接着剤の精進日記

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

トップ > AtCoder > M-SOLUTIONS プロコンオープン 2020

M-SOLUTIONS プロコンオープン 2020

AtCoder ABC 企業コン m-solutions2020

atcoder.jp

A - Kyu in AtCoder

if文全部書く
楽できそうな気もしたけどこっちのほうが早そうだった
提出コード

void solve(){
    int X;
    cin >> X;
    int ans = 0;
    if(X <= 599) ans = 8;
    else if(X <= 799) ans = 7;
    else if(X <= 999) ans = 6;
    else if(X <= 1199) ans = 5;
    else if(X <= 1399) ans = 4;
    else if(X <= 1599) ans = 3;
    else if(X <= 1799) ans = 2;
    else if(X <= 1999) ans = 1;
    cout << ans << endl;
}

B - Magic 2

ちょっとこどふぉっぽい気がした
A \lt B \lt Cとなるまでに必要な操作回数をシミュレートしてそれがK回以内でできるか判定すればいい
提出コード

void solve(){
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    int cnt = 0;
    while(A >= B){
        B *= 2;
        cnt++;
    }
    while(B >= C){
        C *= 2;
        cnt++;
    }
    if(cnt <= K) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Marks

これ累積和でもいいの面白いね
i学期とi-1学期との差異はA_iとA_{i-K}なのでこの大小比較を行えばいい
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    for(int i=K;i<N;i++){
        if(A[i-K] >= A[i]) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}

D - Road to Millionaire

未来がわかっても最大化出来ないので株やりません（？）
まず、各日で株を持っていたら同額で買い直せるのでそれを全て売ってしまっていい
今がi日目だとすると、A_i \lt A_{i+1}ならば株を買えばその分必ず得をする
逆にA_i \geq A_{i+1}のときは買っても損をするだけになる
そのため、各日の最初に持っている株を全部売り、A_i \lt A_{i+1}の時買えるだけ買えばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];

    ll cur = 1000;
    ll kabu = 0;
    REP(i,N){
        cur += kabu * A[i];
        kabu = 0;
        if(i == N-1) break;
        if(A[i] < A[i+1]){
            kabu += cur / A[i];
            cur -= cur / A[i] * A[i];
        }
    }

    cout << cur << endl;
}

E - M's Solution

ぱっと見全探索できそうな制約なのでまず全探索を考えてみる
サンプルを睨むと各集落のx座標もしくはy座標を通るような辺のみを考えれば良さそう
これはある鉄道Lを考えると、Lを選ぶ集落だけを抜き出すと中央値と同じ議論ができるため、集落のうちどこかを通る（これ頭いい）
これは\mathcal{O}(3^N)で出来そう
実際には毎回コスト計算をすると\mathcal{O}(3^N \times N ^ 2)かかりTLEになる
コンテスト中はここから計算量削れなくて終わったけど、前計算することで計算量を落とせる
x軸方向とy軸方向に分けてコストを前計算する
それぞれについて、2 ^ N通り前計算をすると
前計算に\mathcal{O}(2 ^ N \times N ^ 2)、全探索部分に\mathcal{O}(3 ^ N \times N)でこの問題を解くことができる
全探索部分は再帰が楽だと思う（ループで部分集合列挙のほうが良かったりするのかな）
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> X(N), Y(N), P(N);
    REP(i,N) cin >> X[i] >> Y[i] >> P[i];
    vector<vector<ll>> costX(1<<N, vector<ll>(N, LINF));
    auto costY = costX;
    REP(i,1<<N){
        REP(j,N){
            costX[i][j] = abs(X[j]);
            costY[i][j] = abs(Y[j]);
            REP(k,N) if(i >> k & 1){
                chmin(costX[i][j], abs(X[j] - X[k]));
                chmin(costY[i][j], abs(Y[j] - Y[k]));
            }
        }
    }

    vector<ll> ans(N+1, LINF);
    auto dfs = [&](auto && self, vector<int> &state) -> void{
        if(size(state) == N){
            ll x = 0, y = 0;
            int cnt = 0;
            REP(i,N){
                if(state[i] == 0) continue;
                cnt++;
                if(state[i] == 1) x |= (1LL << i);
                else if(state[i] == 2) y |= (1LL << i);
            }

            ll sum = 0;
            REP(i,N){
                sum += P[i] * min(costX[x][i], costY[y][i]);
            }
            chmin(ans[cnt], sum);
        }
        else{
            REP(i,3){
                state.emplace_back(i);
                self(self, state);
                state.pop_back();
            }
        }
    };

    vector<int> state;
    dfs(dfs, state);
    REP(i,N+1) cout << ans[i] << endl;
}