SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)

A問題

　2倍していきながら範囲内に被る数を数えていけば十分間に合う。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll C, D;
    cin >> C >> D;

    ll ans = 0;
    for (ll i = 0;; i++) {
        ll low = 140 * pow(2, i);
        ll high = 170 * pow(2, i);
        if (low >= D) {
            break;
        }
        if (high <= C) {
            continue;
        }
        ans += min(D, high) - max(low, C);
    }

    cout << ans << endl;
}

B問題

問題

　個の要素を持つ配列が与えられる。連続して並ぶ個の薬品をとする操作を繰り返したとき、和を最大化せよ。

解法

　DPを考えて、番目を0にしないような最大値、左側に0が個続くような最大値の2つを保持しながら計算していくと上手く遷移が取れるので計算できる。コンテスト中の提出時はもっと無駄の多いコードを書いていたがもっと洗練させることができた。以下は修正後のもの。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> b(N);
    for (ll i = 0; i < N; i++) {
        cin >> b[i];
    }

    //1-originとして
    //dp[i][0] := b[i]を0としない[0, i]までの和の最大値
    //dp[i][1] := b[i]を0とする[0, i]までの和の最大値
    vector<vector<ll>> dp(N + 1, vector<ll>(2, INT_MIN));

    dp[0][0] = 0;
    dp[0][1] = 0;

    //(i - K, i]を0にするという操作を考える

    //i < Kでは0にする操作ができないので0としないものを求めるだけ
    for (ll i = 1; i < K; i++) {
        dp[i][0] = dp[i - 1][0] + b[i - 1];
    }

    for (ll i = K; i <= N; i++) {
        //0にしない場合直前までの大きい方にb[i - 1]を足すだけ
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + b[i - 1];

        //0にする場合
        //(1)直前を0としていたらここだけを0にできる
        //(2)直前を0にしていなかったらK個前まで戻る
        dp[i][1] = max(dp[i - 1][1], max(dp[i - K][0], dp[i - K][1]));
    }

    cout << max({ dp[N][0], dp[N][1] }) << endl;
}

反省

　こういうDPをなんとか書けたのは多少成長を感じる。計算過程で必要なものを考察して、それを上手く持ちながら計算していけたので良かった。