ei1333の日記

ぺこい

Facebook Hacker Cup 2016 Qualification Round

一応全部通ってた。

10. Boomerang Constellations

問題概要

二次元平面上に N 個の星がそれぞれ異なる位置に存在する。 それぞれの星は、座標(X_i, Y_i) で表される。 ブーメラン星座を以下のように定義する。

  • 星a-b間の距離 = 星b-c間の距離 (a ≠ b ≠ c) を満たす3つの星の組

このとき、ブーメラン星座の組み合わせの個数を答えよ。ただし他のブーメラン星座と星を共有してもよい。

解法

星 b を中心の星とすることを考え、星 b をすべての星に当てはめて総当りする。

星 b からの距離が等しい任意の 2 星間の組はブーメラン星座を成す。
一般化すると, 距離が等しい星が N 個あったときは、1 から N - 1 までの総和の組の個数を作れる。

等しい距離の星の個数を数えるのは map(連想配列) で簡単にできるので、O(N^2 log N) で解くことができ, だいたい間に合う。(O(N^2 log N)は前の CF で落ちた気が)

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int64 Solve()
{
  int N, X[2000], Y[2000];
  int64 ret = 0;
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }
  for(int i = 0; i < N; i++) {
    map< int, int > C;
    for(int j = 0; j < N; j++) {
      C[(X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j])]++;
    }
    for(auto& v : C) {
      ret += (v.second - 1) * v.second / 2;
    }
  }
  return(ret);
}

int main()
{
  int T;
  cin >> T;
  for(int i = 0; i < T; i++) {
    cout << "Case #" << i + 1 << ": " << Solve() << endl;
  }
}

25. High Security

問題概要

格子状の高さ 2, 幅 N の地図 G が与えられる。
 {G_{i,j}} = '.' のとき (i,j) に何もないマスを示し,  {G_{i,j}} = '#' のとき (i, j) に建物があることを示す。

警備員は何もないマス('.') に駐在することができ, 自分のマスだけでなく, 上下左右の連続した何もないマスも見渡すことができる。
例えば, 警備員を 'G' で表すとき,以下のように 見渡せる範囲は 'G' と '*' の部分となる。

.*.X.X..
*G*****X

全ての何もないマスを警備員が見渡せるようにしたいとき, 配置する警備員の最小の人数を求めよ。

解法

こういう問題ちょっと反例がありそうで怖い。

何もないマス(x, y) において, 隣接する左右のマス (x - 1, j),(x + 1, j) に建物があるとき, 左右方向に警備できない (x, y) に置くよりは, 左右方向に警備できる可能性がある (x, y + 1) あるいは, (x, y - 1) に置いたほうが良いのは直感的に分かる。
なので, それに該当するマス全てに最初に警備員を配置する。

あとはGrundyに左方向から, まだ警備されていない何もないマスがあれば 警備員を配置していく。Grundy怖いけど。

ソース

#include<bits/stdc++.h>
using namespace std;

struct UnionFindTree
{
  vector< int > data;
  UnionFindTree(int sz)
  {
    data.assign(sz, -1);
  }
  inline void Unite(int x, int y)
  {
    x = Find(x), y = Find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }
  inline int Find(int k)
  {
    return(data[k] < 0 ? k : data[k] = Find(data[k]));
  }
  inline bool Same(int x, int y)
  {
    return(Find(x) == Find(y));
  }
};


int Solve()
{
  int N;
  string G[2];

  cin >> N;
  N += 2;
  cin >> G[0];
  cin >> G[1];

  G[0] = "X" + G[0] + "X";
  G[1] = "X" + G[1] + "X";

  bool Root[10000] = {};
  UnionFindTree uf1(N), uf2(N);
  for(int i = 1; i < N; i++) {
    if(G[0][i - 1] == '.' && G[0][i] == '.') uf1.Unite(i - 1, i);
    if(G[1][i - 1] == '.' && G[1][i] == '.') uf2.Unite(i - 1, i);
  }

  int Count = 0;
  for(int i = 1; i < N - 1; i++) {
    if(G[0][i - 1] == 'X' && G[0][i] == '.' && G[0][i + 1] == 'X') {
      ++Count;
      Root[uf1.Find(i)] = true;
      if(G[1][i] == '.') Root[uf2.Find(i) + 5000] = true;
    }
  }
  for(int i = 1; i < N - 1; i++) {
    if(G[1][i - 1] == 'X' && G[1][i] == '.' && G[1][i + 1] == 'X') {
      if(Root[uf2.Find(i) + 5000]) continue;
      ++Count;
      Root[uf2.Find(i) + 5000] = true;
      if(G[0][i] == '.') Root[uf1.Find(i)] = true;
    }
  }
  for(int i = 1; i < N - 1; i++) {
    if(G[0][i] == '.' && !Root[uf1.Find(i)]) {
      ++Count;
      Root[uf1.Find(i)] = true;
    }
    if(G[1][i] == '.' && !Root[uf2.Find(i) + 5000]) {
      ++Count;
      Root[uf2.Find(i) + 5000] = true;
    }
  }
  return(Count);
}


int main()
{
  int T;
  cin >> T;
  for(int i = 0; i < T; i++) {
    cout << "Case #" << i + 1 << ": " << Solve() << endl;
  }
}

25. The Price is Correct

問題概要

N 個の数値からなる数列 B がある。
数列 B から連続する任意の要素を抜き出し, その要素の和を合計する。
合計した結果が T を上回ると ゲームに負けるので, それ以下に抑えたい。
抜き出し方は何通りあるか求めよ。

解法

圧倒的に尺取り法。 数列 B を左から右に走査することを考える。 B[i] を抜き出す数列の最後の要素とするとき, 和が T 以下を満たす先頭の要素番号 s の最小値を求める。
すると, B[i] ≥ 1 なので s, s+1, ..., i は全て和が T 以下になる。よって, (i - s) を抜き出し方の組み合わせとして足す。
このとき s は単調増加。尺取りすると O(N)。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int64 Solve()
{
  int64 N, P, B[100000];
  cin >> N >> P;
  for(int i = 0; i < N; i++) {
    cin >> B[i];
  }
  int64 ret = 0, head = 0, now = 0;
  for(int i = 0; i < N; i++) {
    now += B[i];
    while(head <= i && now > P) {
      now -= B[head];
      ++head;
    }
    ret += i - head + 1;
  }
  return(ret);
}
int main()
{
  int T;
  cin >> T;
  for(int i = 0; i < T; i++) {
    cout << "Case #" << i + 1 << ": " << Solve() << endl;
  }
}

40. Text Editor

問題概要

文字列の末端への 1 文字ずつの追加, 削除, プリントができるテキストエディタがある。
それぞれの操作にはコスト 1 がかかる。
最初, エディタの内容は空文字列である。
N 個の単語のうち任意の K 個を選んでプリントしたい。
また K 個の単語を表示した後, 空文字列にして終わる必要がある。
コストを最小化せよ。

解法

なるべく先頭からの文字列を重複させたいので, 辞書順でソートする。
あとは DP するだけ。次の文字列へ行くまでのコストの計算は, 共通している文字数貪欲に数えれば求まる。
O(N^3)になるがこれでも間に合う(N^3のテストケースが100個は死ぬ気がするけどテストケースが弱いのか1秒未満だった)

  • dp[i][j]: 最後に i 番目のワードをプリントし, 計 j 個プリントしたときのコストの最小値
  • dp[i][j]: dp[k][j - 1] + dist(S[k], S[i]) (k < i)

ソース

#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;

int Solve()
{
  int N, K;
  string S[302];
  int dp[302][302];
  fill_n(*dp, 302 * 302, INF);

  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    cin >> S[i];
  }
  sort(S, S + N);

  int ret = INF;
  for(int i = 0; i < N; i++) {
    dp[i][1] = S[i].size() + 1;
    for(int j = i - 1; j >= 0; j--) { // 前の要素
      int Match = 0;
      while(Match < S[j].size() && Match < S[i].size() && S[j][Match] == S[i][Match]) ++Match;
      for(int k = 1; k <= i; k++) {    // とった個数
        dp[i][k + 1] = min< int >(dp[i][k + 1], dp[j][k] + S[j].size() + S[i].size() - 2 * Match + 1);
      }
    }
  }
  for(int i = 0; i < N; i++) {
    ret = min< int >(ret, dp[i][K] + S[i].size());
  }
  return(ret);
}

int main()
{
  int T;
  cin >> T;
  for(int i = 0; i < T; i++) {
    cout << "Case #" << i + 1 << ": " << Solve() << endl;
  }
}