AtCoder Beginner Contest 364（ABC364）

atcoder.jp

A - Glutton Takahashi

sweet が今連続で何個食べたかを数えておく
2回の状態でまだ食べる必要がある場合はNo

提出コード

void solve() {
    int N;
    cin >> N;
    int sweet = 0;
    REP(i, N) {
        string S;
        cin >> S;
        if (sweet >= 2) {
            cout << "No" << endl;
            return;
        }
        if (S == "sweet") {
            sweet++;
        }
        else sweet = 0;
    }
    cout << "Yes" << endl;
}

B - Grid Walk

1手ずつシミュレートをし、最終的な座標を答える

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    int sh, sw;
    cin >> sh >> sw;
    vector<string> C(H);
    REP(i, H) cin >> C[i];
    string X;
    cin >> X;
    sh--, sw--;
    for (char c : X) {
        if (c == 'U') {
            if (sh > 0 && C[sh - 1][sw] == '.') sh--;
        }
        else if (c == 'D') {
            if (sh < H - 1 && C[sh + 1][sw] == '.') sh++;
        }
        else if (c == 'L') {
            if (sw > 0 && C[sh][sw - 1] == '.') sw--;
        }
        else if (c == 'R') {
            if (sw < W - 1 && C[sh][sw + 1] == '.') sw++;
        }
    }
    cout << sh + 1 << " " << sw + 1 << endl;
}

C - Minimum Glutton

$ A $ の降順、もしくは $ B $ の降順に食べるのが最適なのでそれぞれのパターンの最小値が答え

提出コード

void solve() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    vector<ll> A(N), B(N);
    REP(N) cin >> A[i];
    REP(N) cin >> B[i];
    vector<int> idx(N);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int i, int j) { return A[i] > A[j]; });
    int ans = N;
    {
        ll sum = 0;
        REP(i, N) {
            sum += A[idx[i]];
            if (sum > X) {
                chmin(ans, i + 1);
                break;
            }
        }
    }
    sort(ALL(idx), [&](int i, int j) { return B[i] > B[j]; });
    {
        ll sum = 0;
        REP(i, N) {
            sum += B[idx[i]];
            if (sum > Y) {
                chmin(ans, i + 1);
                break;
            }
        }
    }
    cout << ans << endl;
}

D - K-th Nearest

$ d' _{k_j} $ を求めるために二回二分探索を行う
$ d' _{k_\j} $ 自身を二分探索で求める
その判定条件として $ [b_j - x, b_j + x] $ に含まれる $ a $ の要素数が $ k $ 以上である最小の $ x $ を二分探索で求める
$ b_j - x $ 以上、$ b_j + x $ 以下の区間に含まれる $ a $ の要素数は $ a $ をソートしておくことでこちらも二分探索で求めることができる

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    REP(N) cin >> a[i];
    sort(ALL(a));
    while (Q--) {
        int b, k;
        cin >> b >> k;
        auto check = [&](int x) -> bool {
            int l = lower_bound(ALL(a), b - x) - a.begin();
            int r = upper_bound(ALL(a), b + x) - a.begin();
            return r - l >= k;
        };
        int l = -1, r = 2 * INF;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (check(m)) r = m;
            else l = m;
        }
        cout << r << endl;
    }
}

E - Maximum Glutton

DPをする
愚直にDPをすると $ dp[i][j][k] := i $ 番目まで見て、甘さの合計が $ j $、しょっぱさの合計が $ k $ のときに食べた個数の最大として $ O(NXY) $ となる
食べた個数をDPテーブルの変数としてもち、 $ X $ 、もしくは $ Y $ をDPの結果として持つことで $ dp[i][j][k] := i $ 番目まで見て、$ j $ 個すでに食べていて、甘さの合計が $ k $ のときの、しょっぱさの合計の最小値、として $ O(N^2X) $ で解くことができる

提出コード

void solve() {
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<int> A(N), B(N);
    REP(i, N) cin >> A[i] >> B[i];
    vector<int> idx(N);
    REP(i, N) idx[i] = i;
    int ans = 0;

    REP(_, 2) {
        sort(ALL(idx), [&](int i, int j) { return B[i] == B[j] ? A[i] < A[j] : B[i] < B[j]; });
        vector dp(N + 1, vector<int>(Y + 2, INF));
        dp[0][0] = 0;
        REP(i, N) {
            vector dp2(N + 1, vector<int>(Y + 2, INF));
            REP(j, N + 1) {  // j個食べた
                for (int k = Y + 1; k >= 0; k--) {
                    if (dp[j][k] == INF) continue;
                    chmin(dp2[j][k], dp[j][k]);
                    if (k <= Y and dp[j][k] <= X) {
                        chmin(dp2[j + 1][min(Y + 1, k + B[idx[i]])], dp[j][k] + A[idx[i]]);
                    }
                }
            }
            swap(dp2, dp);
        }
        REP(i, N + 1) REP(j, Y + 2) if (dp[i][j] != INF and dp[i][j] > 0) chmax(ans, i);
        swap(X, Y);
        swap(A, B);
    }

    cout << ans << endl;
}