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問題
お金の差を 以上にしないようにしながら友達を誘い友情度を最大化する問題。
この問題は最初にお金を基準にソートをしておく。
あとはしゃくとり法を使ってお金の差が 以上にならないようにしながらやっていけば良い
#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は連続して 回の猫のところに行くことは我慢できるが、連続して 回以上猫のいるところに行くとダメ。
連続して 回以上猫のいるところに行かないようにして行けるレストランは何件あるか。
私のコードでは幅優先探索で求めた。
#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; }