Hatena::Grouptopcoder

peryaudoのTopCoder日記

|

2016-04-14

RGBTree

| 22:30

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

class RGBTree {
 public:
  string exist(vector<string> G) {
    g = G;
    const int k3 = (g.size() - 1) / 3;
    return F((1 << g.size()) - 1, k3, k3, k3) ? "Exist" : "Does not exist";
  }

  bool F(int incl, int red, int green, int blue) {
    if (memo.count(make_tuple(incl, red, green, blue))) {
      return memo[make_tuple(incl, red, green, blue)];
    }
    bool& ans = memo[make_tuple(incl, red, green, blue)];
    ans = false;

    if (__builtin_popcount(incl) == 1 && red == 0 && green == 0 && blue == 0) {
      return ans = true;
    }
    for (int i = 0; i < g.size() && !ans; ++i) {
      if (!(incl & (1 << i))) continue;
      const int nincl = incl ^ (1 << i);
      for (int j = 0; j < g[i].size() && !ans; ++j) {
        if (i == j) continue;
        if (!(incl & (1 << j))) continue;
        if (g[i][j] == '.') continue;
        if (g[i][j] == 'R' && red   > 0 && F(nincl, red - 1, green, blue)) {
          ans = true; break;
        }
        if (g[i][j] == 'G' && green > 0 && F(nincl, red, green - 1, blue)) {
          ans = true; break;
        }
        if (g[i][j] == 'B' && blue  > 0 && F(nincl, red, green, blue - 1)) {
          ans = true; break;
        }
      }
    }

    return ans;
  }

  map<tuple<int, int, int, int>, bool> memo;
  vector<string> g;
};

すっっっっげー普通のBitDP。

むっちゃ久々にBitDP書いた。

2016-03-19

TaroFillingAStringDiv1

| 16:28

ほぼ解けてたハズ(小学生並も言い訳)

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

class TaroFillingAStringDiv1 {
 public:
  int getNumber(int N, vector<int> position, string value) {
    vector<pair<ll, char>> filled;
    for (int i = 0; i < position.size(); ++i) {
      filled.emplace_back(position[i], value[i]);
    }
    sort(filled.begin(), filled.end());
    const ll MOD = 1000000007;
    ll ans = 1;
    for (int i = 0; i < filled.size() - 1; ++i) {
      const ll diff = filled[i + 1].first - filled[i].first;
      const ll ab = abs(filled[i + 1].second - filled[i].second);
      if (diff % 2 == ab) continue;
      ans = ans * diff % MOD;
    }
    return ans;
  }
};

2016-03-16

ChocolateDividingEasy

| 20:12

#include <iostream>
#include <vector>
#include <string>
#include <cassert>

using namespace std;
using ll = long long;

class ChocolateDividingEasy {
 public:
  int findBest(vector<string> chocolate) {
    field = vector<vector<ll>>(chocolate.size() + 1, vector<ll>(chocolate[0].size() + 1, 0));
    for (int i = 0; i < chocolate.size(); ++i) {
      for (int j = 0; j < chocolate[0].size(); ++j) {
        field[i + 1][j + 1] = field[i + 1][j] + chocolate[i][j] - '0';
      }
    }

    for (int i = 0; i < chocolate.size(); ++i) {
      for (int j = 0; j < chocolate[0].size(); ++j) {
        field[i + 1][j + 1] += field[i][j + 1];
      }
    }


    ll ans = 0;
    // [0, ix) [ix, jx) [jx, chocolate.size())
    for (int ix = 1; ix < chocolate.size(); ++ix) {
      for (int jx = ix + 1; jx < chocolate.size(); ++jx) {
        for (int ky = 1; ky < chocolate[0].size(); ++ky) {
          for (int ly = ky + 1; ly < chocolate[0].size(); ++ly) {
            ll cur = 1LL << 60LL;
            cur = min(cur, Sum(0,  0, ix, ky));
            cur = min(cur, Sum(ix, 0, jx, ky));
            cur = min(cur, Sum(jx, 0, chocolate.size(), ky));

            cur = min(cur, Sum(0,  ky, ix, ly));
            cur = min(cur, Sum(ix, ky, jx, ly));
            cur = min(cur, Sum(jx, ky, chocolate.size(), ly));

            cur = min(cur, Sum(0,  ly, ix, chocolate[0].size()));
            cur = min(cur, Sum(ix, ly, jx, chocolate[0].size()));
            cur = min(cur, Sum(jx, ly, chocolate.size(), chocolate[0].size()));
            ans = max(ans, cur);
          }
        }
      }
    }

    return (int)ans;
  }

  // 0-indexed, [sx, ex) [sy, ey)
  ll Sum(int sx, int sy, int ex, int ey) {
    const ll res = field[ex][ey] - field[sx][ey] - field[ex][sy] + field[sx][sy];
    return res;
  }

  vector<vector<ll>> field;
};

貴重なやるだけ問題。

GreaterGame

| 16:35

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

using namespace std;

class GreaterGame {
 public:
  double calc(vector<int> hand, vector<int> sothe) {
    sort(hand.begin(), hand.end());

    set<int> hands;
    for (auto&& x : hand) {
      hands.insert(x);
    }

    set<int> fixed;
    for (auto&& x : sothe) {
      if (x > 0) {
        fixed.insert(x);
      }
    }

    set<int> unfixed;
    for (int i = 1; i <= 2 * hand.size(); ++i) {
      if (!fixed.count(i) && !hands.count(i))
        unfixed.insert(i);
    }

    double ans = 0.0;
    Determine(hands, fixed, ans);

    Rnd(hands, unfixed, ans);

    return ans;
  }

  void Determine(set<int>& hands, set<int>& fixed, double& ans) {
    for (auto&& fi : fixed) {
      if (fi < *hands.rbegin()) {
        int picked = -1;
        for (auto&& ha : hands) {
          if (ha > fi) {
            picked = ha;
            break;
          }
        }
        hands.erase(picked);
        ans += 1.0;
      } else {
        hands.erase(*hands.begin());
      }
    }
  }

  void Rnd(set<int>& hands, set<int>& unfixed, double& ans) {
    for (auto&& ha : hands) {
      double win = 0.0;
      double total = 0.0;
      for (auto&& unf : unfixed) {
        if (ha > unf) {
          win += 1.0;
        }
        total += 1.0;
      }
      ans += win / total;
    }
  }
};

PeriodicJumping

| 15:03

#include <vector>
#include <cstdlib>

using namespace std;
using ll = long long;

class PeriodicJumping {
 public:
  int minimalTime(int x, vector<int> jumpLengths) {
    x = abs(x);
    if (x == 0) return 0;

    ll total = 0;
    ll ma = x;
    for (int i = 0; i < 2 * jumpLengths.size(); ++i) {
      total += jumpLengths[i % jumpLengths.size()];
      ma = max<ll>(ma, jumpLengths[i % jumpLengths.size()]);
      if (ma * 2 <= total + x) return i + 1;
    }

    total /= 2;
    ll ans = x / total * jumpLengths.size();
    x %= total;

    for (int i = 0; i < jumpLengths.size(); ++j) {
      if (x <= 0) break;
      x -= jumpLengths[i];
      ++ans;
    }

    return ans;
  }
};


2016-03-12

Decipherability

| 14:40

#include <string>

using namespace std;

class Decipherability {
 public:
  string check(string s, int K) {
    if (s.size() != K) {
      for (int i = 0; i < s.size(); ++i) {
        for (int j = i + 1; j < s.size(); ++j) {
          if (s[i] == s[j] && j - i <= K) {
            return "Uncertain";
          }
        }
      }
    }
    return "Certain";
  }
};

2016-03-06

Mike and Feet

| 14:11

基本的に蟻本P.298、POJ No.2559の類問。

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
  int n;
  cin>>n;

  vector<int> as(n);
  for (auto&& a : as) {
    cin>>a;
  }

  vector<int> ls(n), rs(n);

  {
    stack<int> st;
    for (int i = 0; i < n; ++i) {
      while (!st.empty() && as[st.top()] >= as[i]) {
        st.pop();
      }
      if (st.empty()) {
        ls[i] = 0;
      } else {
        ls[i] = st.top() + 1;
      }
      st.push(i);
    }
  }
  {
    stack<int> st;
    for (int i = n - 1; i >= 0; --i) {
      while (!st.empty() && as[st.top()] >= as[i]) {
        st.pop();
      }
      if (st.empty()) {
        rs[i] = n - 1;
      } else {
        rs[i] = st.top() - 1;
      }
      st.push(i);
    }
  }

  vector<int> ans(n, 0);
  for (int i = 0; i < n; ++i) {
    ans[rs[i] - ls[i]] = max(ans[rs[i] - ls[i]], as[i]);
  }

  for (int i = n - 2; i >= 0; --i) {
    ans[i] = max(ans[i], ans[i + 1]);
  }

  for (int i = 0; i < ans.size(); ++i) {
    cout<<ans[i]<<(i == ans.size() - 1 ? "\n" : " ");
  }

  return 0;
}

|