srm433 復習

参加記の方書くの忘れてた。
本番は250で8! * 160 * 160を書いてしまって撃墜され、500でad-hocをやって撃墜されてしまって0点。うぐぐ。難し目のセットだったようであまり下がらなかった。

div1:250 MagicWords

T(i) = T(0)となるiがK個存在する<=>T(0)はK個の等しい部分文字列に分割できる、という事を利用すると8! * 160になって通る。

class MagicWords {
public:
int count(vector <string> S, int K) {
  int ret = 0;
  vector<int> P(S.size());
  for (int i = 0; i < S.size(); ++i) P[i] = i;
  do {
    string con;
    for (int i = 0; i < P.size(); ++i) con += S[P[i]];
    int cnt = 0;
    for (int i = 1; i <= con.size(); ++i) {
      if (con.size() % i != 0) continue;
      bool ok = true;
      for (int j = 1; j < (con.size() / i); ++j) {
        for (int k = 0; k < i; ++k) {
          if (con[k] != con[j * i + k]) ok = false;
        }
      }
      if (ok) {
        cnt = con.size() / i;
        break;
      }
    }
    if (cnt == K) ++ret;
  } while (next_permutation(P.begin(), P.end()));
  return ret;
}

div1:500 SettingTents

最初に菱形の辺としてありうる直線を列挙して、長さ（だと整数にならないのでその二乗）で分類する。
等しい長さの直線を二つ選ぶと菱形が出来るので、bounding boxを計算して上下左右に動かす。

typedef complex<int> P;

class SettingTents {
public:
int countSites(int N, int M) {
  map<int, vector<P> > m;
  for (int i = 0; i <= N; ++i) {
    for (int j = -M; j <= M; ++j) {
      if (i == 0 && j <= 0) continue;
      m[i * i + j * j].push_back(P(i, j));
    }
  }
  int ret = 0;
  for (int d = 1; d <= N * N + M * M; ++d) {
    vector<P> &v = m[d];
    for (int i = 0; i < v.size(); ++i) {
      for (int j = i + 1; j < v.size(); ++j) {
        P p[3] = {v[i], v[j], v[i] + v[j]};
        int minx = 0, maxx = 0, miny = 0, maxy = 0;
        for (int k = 0; k < 3; ++k) {
          minx <?= real(p[k]);
          maxx >?= real(p[k]);
          miny <?= imag(p[k]);
          maxy >?= imag(p[k]);
        }
        int x = maxx - minx, y = maxy - miny;
        if (x <= N && y <= M) ret += (N - x + 1) * (M - y + 1);
      }
    }
  }
  return ret;
}

div1:1000 BarbarianInvasion

マップの外側と首都を分断するようなコスト最小のラインを求めれば良くて（正確にはラインじゃなくて-で途切れてる事もあるけども）、結局それはグラフの最小カット（＝最大流）になっているので、適切なグラフを作ってからフローを流すだけで求まってしまう、という。
単純にコスト最小なラインではなく出来るだけ潰すマス目の小さいラインを求めよ、という一見やっかいな条件があるが、適当にでかい数を足して最後に割ると上手く行く。

typedef long long ll;

const ll MOD = 10000000000LL;

template<typename T>
class Graph {
private:
  struct Edge {
    int to, back;
    T flow, cap;
    Edge(int to, T cap, int back) : to(to), back(back), flow(0), cap(cap) {}
    T residue() { return cap - flow; }
  };
  int n;
  vector<vector<Edge> > g;
public:
  Graph(int n) : n(n), g(n) {}
  void insert(int i, int j, T c) {
    g[i].push_back(Edge(j, c, g[j].size()));
    g[j].push_back(Edge(i, 0, g[i].size() - 1));
  }
  T dinic(int s, int t) {
    T flow = 0;
    int P[n], Q[n];
    for (;;) {
      memset(P, -1, sizeof(P));
      int QF = 0, QB = 0;
      P[Q[QB++] = s] = -2;
      while (QB > QF && P[t] == -1)
        for (int u = Q[QF++], v, i = 0; i < g[u].size(); ++i)
          if (P[v = g[u][i].to] == -1 && g[u][i].residue() > 0)
            P[Q[QB++] = v] = g[u][i].back;
      if (P[t] == -1) return flow;
      for (int i = 0, z; i < g[t].size(); ++i)
        if (g[z = g[t][i].to][g[t][i].back].residue() > 0 && P[z] != -1) {
          T inc = g[z][g[t][i].back].residue();
          for (int e = z; P[e] >= 0; e = g[e][P[e]].to)
            inc = min(inc, g[g[e][P[e]].to][g[e][P[e]].back].residue());
          if (!inc) continue;
          g[t][i].flow -= inc, g[z][g[t][i].back].flow += inc;
          for (int e = z; P[e] >= 0; e = g[e][P[e]].to)
            g[e][P[e]].flow -= inc, g[g[e][P[e]].to][g[e][P[e]].back].flow += inc;
          flow += inc;
        }
    }
  }
};

int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};

class BarbarianInvasion {
public:
int minimalDetachment(vector <string> countryMap, vector <int> detachmentSize) {
  int N = countryMap.size(), M = countryMap[0].size();
#define HI(i, j) ((i) * M + (j))
#define LO(i, j) (HI(N, 0) + (i) * M + (j))
#define D (LO(N, 0))
  int S;
  Graph<ll> g(D + 1);
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      for (int k = 0; k < 4; ++k) {
        int ni = i + dr[k], nj = j + dc[k];
        if (0 <= ni && ni < N && 0 <= nj && nj < M) {
          g.insert(HI(i, j), LO(ni, nj), MOD * 2);
        }
      }
      if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
        g.insert(HI(i, j), D, MOD * 2);
      }
      if (countryMap[i][j] == '*') {
        S = HI(i, j);
      } else if (countryMap[i][j] != '-') {
        g.insert(LO(i, j), HI(i, j), detachmentSize[countryMap[i][j] - 'A'] + MOD);
      }
    }
  }
  return g.dinic(S, D) % MOD;
}