TopCoder SRM 588 Div2
Easy: KeyDungeonDiv2
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; class KeyDungeonDiv2 { public: int countDoors(vector<int> r, vector<int> g, vector<int> k) { int N = r.size(); int ans = 0; for (int i = 0; i < N; ++i) { if (k[0] + k[1] + k[2] < r[i] + g[i]) continue; if (k[0] + k[2] < r[i]) continue; if (k[1] + k[2] < g[i]) continue; ans++; } return ans; } };
Medium: GUMIAndSongsDiv2
ダイクストラの要領で、{最後に歌った曲, 歌い終わった曲} の最小の時間を求める。
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; typedef tuple<int, int, int> P; template <class T, class U> void chmax(T &t, U f) { if (t < f) t = f; } class GUMIAndSongsDiv2 { int bitCount(long x) { x = (x & 0x55555555) + (x >> 1 & 0x55555555); x = (x & 0x33333333) + (x >> 2 & 0x33333333); x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f); x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff); return (x & 0x0000ffff) + (x >> 16 & 0x0000ffff); } public: int maxSongs(vector<int> duration, vector<int> tone, int T) { int N = duration.size(); map<pair<int, int>, int> dp; priority_queue<P, vector<P>, greater<P>> Q; for (int i = 0; i < N; ++i) { if (duration[i] <= T) { Q.push(make_tuple(duration[i], i, 1 << i)); dp[{i, 1 << i}] = duration[i]; } } int ans = 0; while (!Q.empty()) { int d, v, mask; tie(d, v, mask) = Q.top(); Q.pop(); chmax(ans, bitCount(mask)); for (int i = 0; i < N; ++i) { if (mask & (1 << i)) continue; int next_d = d + abs(tone[v] - tone[i]) + duration[i]; if (next_d > T) continue; int next_mask = mask | (1 << i); if (dp.count({i, next_mask}) && dp[{i, next_mask}] <= next_d) continue; dp[{i, next_mask}] = next_d; Q.push(make_tuple(next_d, i, next_mask)); } } return ans; } };
Hard: GameInDarknessDiv2
aliceとbobを同時に動かしながらbobのいる位置を幅優先で求めていく。
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; class GameInDarknessDiv2 { public: string check(vector<string> f, vector<string> m) { int H = f.size(); int W = f[0].size(); string moves = ""; for (string &s : m) moves += s; pair<int, int> alice, bob; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (f[i][j] == 'A') { alice = {i, j}; f[i][j] = '.'; } else if (f[i][j] == 'B') { bob = {i, j}; f[i][j] = '.'; } } } vector<pair<int, int>> bob_Q; bob_Q.push_back(bob); for (auto &a : moves) { if (a == 'U') alice.first--; if (a == 'R') alice.second++; if (a == 'L') alice.second--; if (a == 'D') alice.first++; set<pair<int, int>> next_bobs; for (auto &b : bob_Q) { if (b == alice) continue; int h = b.first; int w = b.second; if (h > 0 && f[h - 1][w] == '.') next_bobs.insert({h - 1, w}); if (w > 0 && f[h][w - 1] == '.') next_bobs.insert({h, w - 1}); if (h < H - 1 && f[h + 1][w] == '.') next_bobs.insert({h + 1, w}); if (w < W - 1 && f[h][w + 1] == '.') next_bobs.insert({h, w + 1}); } bob_Q.clear(); for (auto &b : next_bobs) { if (b != alice) { bob_Q.push_back(b); } } } if (bob_Q.empty()) return "Alice wins"; return "Bob wins"; } };