読者です 読者をやめる 読者になる 読者になる

Codeforces Round #321 (Div. 2) A~C

A問題

連続した非減少数列の長さを求めれば良いので、前日の稼ぎ以上を今日稼いでいればカウント+1そうでなければカウント=1とする。

前日と今日の稼ぎしかみないので配列は使わず変数2つを使いコードを書いた。

#include <iostream>
#include <algorithm>

int main() {
    int n, pre_money, now_money, count = 0, max = 0;

    std::cin >> n;
    
    // 初日は前日の稼ぎがないので-1としておく
    pre_money = -1;
    for (int i = 0; i < n; i++) {
        std::cin >> now_money;
        if (pre_money > now_money) {
            max = std::max(max, count);
            count = 0;
        }
        count++;
        pre_money = now_money;
    }

    max = std::max(max, count);

    std::cout << max << std::endl;
    return 0;
}

B問題

お金の差を  d 以上にしないようにしながら友達を誘い友情度を最大化する問題。

この問題は最初にお金を基準にソートをしておく。

あとはしゃくとり法を使ってお金の差が  d 以上にならないようにしながらやっていけば良い

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int friends, d;

    std::cin >> friends >> d;

    // money, friendship factor
    std::vector<std::pair<int, int> > v(friends);
    for (int i = 0; i < friends; i++) {
        int m, s;
        std::cin >> m >> s;
        v[i] = std::make_pair(m, s);
    }

    // お金を基準にソート
    std::sort(v.begin(), v.end());

    // 尺取法でとく
    long long start = 0, end = 0, max = 0, total_friendship = v[0].second;
    while(true){
        while (end + 1 < friends && v[end + 1].first - v[start].first < d) {
            end++;
            total_friendship += v[end].second;
        }
        max = std::max(max, total_friendship);
        if (end + 1 == friends) break;
        end++;
        total_friendship += v[end].second;
        while (v[end].first - v[start].first >= d) {
            total_friendship -= v[start].second;
            start++;
        }
    }

    std::cout << max << std::endl;

    return 0;
}

C問題

猫が怖いkefaさんがレストランに行く問題。

kefaは連続して  m 回の猫のところに行くことは我慢できるが、連続して  m 回以上猫のいるところに行くとダメ。

連続して  m 回以上猫のいるところに行かないようにして行けるレストランは何件あるか。

この問題は幅優先探索、もしくは深さ優先探索を使えばよい。

私のコードでは幅優先探索で求めた。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

int main() {
    int n_node, m, count = 0;

    std::cin >> n_node >> m;

    std::vector<int> is_in_cat(n_node);
    std::vector<std::vector<int> > node(n_node);
    for (int i = 0; i < n_node; i++) {
        std::cin >> is_in_cat[i];
    }

    for (int i = 0; i < n_node - 1; i++) {
        int from, to;
        std::cin >> from >> to;
        from--;
        to--;
        node[from].push_back(to);
        node[to].push_back(from);
    }

    // pos, cat;
    std::queue<std::pair<int, int> > pos;
    std::vector<bool> visited(n_node);
    pos.push({ 0, (is_in_cat[0] == 1 ? 1 : 0) });

    while (!pos.empty()) {
        int p = pos.front().first;
        int cat = pos.front().second;
        pos.pop();

        if (visited[p] || cat > m) continue;
        visited[p] = true;

        int push_count = 0;
        for (int i = 0; i < node[p].size(); i++) {
            if (!visited[node[p][i]]) {
                pos.push({ node[p][i], (is_in_cat[node[p][i]] == 1 ? cat + 1 : 0) });
                push_count++;
            }
        }
        // leaf
        if (push_count == 0) {
            count++;
        }
    }

    std::cout << count << std::endl;
    return 0;
}