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

問題

atcoder.jp

感想

遅い4完で冷えた (1538 -> 1528 (-10))。Eが解ければなぁ。

研究を言い訳にして精進してないのが効いている。人々の成長スピードよ......。

A - Kyu in AtCoder

if文を8個書くとすごく時間がかかって大変なことになってしまうので、 を出力する。

提出コード

リンク： https://atcoder.jp/contests/m-solutions2020/submissions/15412198

void solve() {
    ll X;
    cin >> X;
    prints()(8 - (X / 200 - 2));
}

B - Magic 2

まず、 となるまで に対して操作を行い、次に、 となるまで に対して操作を行う。これが最適な手順なので、この方法での操作回数が K を超えるならアウト。

提出コード

リンク：https://atcoder.jp/contests/m-solutions2020/submissions/15417070

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

C - Marks

なら Yes、そうでなければ No。

提出コード

リンク：https://atcoder.jp/contests/m-solutions2020/submissions/15421458

void solve() {
    ll N, K;
    cin >> N >> K;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (ll i = K; i < N; i++) {
        if (A[i - K] < A[i]) {
            prints()("Yes");
        }
        else {
            prints()("No");
        }
    }
}

D - Road to Millionaire

株価が極小のとき有り金全部で株を買い、株価が極大となるときにすべての株売るとACを得た。

実装も汚いし時間もかけちゃったし、よくない動きをした。

提出コード

リンク：https://atcoder.jp/contests/m-solutions2020/submissions/15433173

void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    Vl vec(N);
    bool is_up;
    if (A[0] <= A[1]) {
        is_up = true;
        vec[0] = -1;
    }
    else {
        is_up = false;
        vec[0] = 1;
    }
    for (ll i = 1; i < N; i++) {
        if (is_up) {
            if (A[i - 1] > A[i]) {
                vec[i - 1] = 1;
                is_up = false;
            }
        }
        else {
            if (A[i - 1] < A[i]) {
                vec[i - 1] = -1;
                is_up = true;
            }
        }
    }
    if (is_up) {
        vec[N - 1] = 1;
    }
    else {
        vec[N - 1] = -1;
    }
 
    ll last;
    for (ll i = 0; i < N; i++) {
        if (vec[i] == 1) {
            last = i;
        }
    }
 
    ll kane = 1000, kabu = 0;
    for (ll i = 0; i < N; i++) {
        if (i == last) {
            kane += kabu * A[i];
            kabu = 0;
            break;
        }
        if (vec[i] == 1) {
            kane += kabu * A[i];
            kabu = 0;
        }
        else if (vec[i] == -1) {
            ll r = kane / A[i];
            kabu += r;
            kane -= r * A[i];
        }
    }
 
    prints()(kane);
}

E - M's Solution

『知っておこう』

きょうは C++ なら は間に合うことを知っておこう。

・

・

・

・

・

・

うーん。おそいね。

じゃ！

(set を使って にしてみたら、余計に遅くなった。setの定数倍さん......)

結局、 それぞれについて、線路の 通りの全配置における各集落のコストを で前計算すれば、解は で求められる。前計算の発想が出なかったのすごく反省だ。

コンテスト後提出コード

リンク：https://atcoder.jp/contests/m-solutions2020/submissions/15455281

ll memo_x[16][1 << 15], memo_y[16][1 << 15];
 
void solve() {
    ll N;
    cin >> N;
    Vl xs(N), ys(N), ps(N);
    for (ll i = 0; i < N; i++) {
        cin >> xs[i] >> ys[i] >> ps[i];
    }
 
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < (1ll << N); j++) {
            memo_x[i][j] = abs(xs[i]);
            memo_y[i][j] = abs(ys[i]);
            for (ll k = 0; k < N; k++) {
                if (j >> k & 1) {
                    memo_x[i][j] = min(memo_x[i][j], abs(xs[i] - xs[k]));
                    memo_y[i][j] = min(memo_y[i][j], abs(ys[i] - ys[k]));
                }
            }
        }
    }
 
    Vl ans(N + 1, L_INF);
 
    ll ub = 1;
    for (ll i = 0; i < N; i++) {
        ub *= 3;
    }
 
    for (ll mask = 0; mask < ub; mask++) {
        ll tmp = mask;
        ll cnt = 0;
        ll fgx = 0, fgy = 0;
        for (ll i = 0; i < N; i++) {
            ll r = tmp % 3;
            if (r == 1) {
                fgx |= 1ll << i;
                ++cnt;
            }
            else if (r == 2) {
                fgy |= 1ll << i;
                ++cnt;
            }
            tmp /= 3;
        }
        ll score = 0;
        for (ll i = 0; i < N; i++) {
            score += min(memo_x[i][fgx], memo_y[i][fgy]) * ps[i];
        }
        ans[cnt] = min(ans[cnt], score);
    }
 
    for (ll i = 0; i <= N; i++) {
        prints()(ans[i]);
    }
}

F - Air Safety

読めてない。けど、正答者数を見る限りEより簡単だったみたいだな。