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

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";
  }
};