SRM 578 div2
917->1014
DIV2で59位でした。
easy
#include <cstdio> #include <algorithm> #include <vector> #include <string> using namespace std; class DeerInZooDivTwo{ public: vector <int> getminmax(int N, int K){ vector<int> ans; ans.push_back(max(0, N - K)); ans.push_back(N - (K + 1) / 2); return ans; } };
med
マンハッタン距離D以内にあるvを辺で結んでグラフにし、グラフの連結成分の数mとすると
m != 0 のとき
2^m - 1 が答え
m == 0 のとき
0 が答え
#include <cstdio> #include <algorithm> #include <vector> #include <string> #include <cmath> using namespace std; typedef long long ll; typedef pair<int, int> P; const ll MOD = 1000000007; class GooseInZooDivTwo{ public: int sx, sy; vector<string> F; vector<P> vs; bool used[51 * 51]; void solve(const int i, const int d){ P p = vs[i]; int x = p.first; int y = p.second; for(int j = 0; j < vs.size(); j++){ if(!used[j]){ int x_ = vs[j].first; int y_ = vs[j].second; if(abs(x - x_) + abs(y - y_) <= d){ used[j] = true; solve(j, d); } } } } int count(vector <string> field, int dist){ ll ans; sx = field[0].size(); sy = field.size(); F = field; int g = 0; for(int i = 0; i < sx; i++){ for(int j = 0; j < sy; j++){ if(F[j][i] == 'v'){ vs.push_back(P(i, j)); } } } fill(used, used + vs.size(), false); for(int i = 0; i < vs.size(); i++){ if(!used[i]){ g++; used[i] = true; solve(i, dist); } } printf("%d\n", g); if(g == 0) return 0; ans = 1; for(int i = 0; i < g; i++){ ans *= 2; ans = ans % MOD; } return (int)ans - 1; } };