ei1333の日記

ぺこい

NCR CodeSprint

www.hackerrank.com

二次元セグ木好き.

Counting Mistakes

問題概要

 {s_1 = 1} からはじめ,  {s_i = s_{i - 1} + 1} とする操作を  {n(1 \le n \le 10^3)} 回繰り返す.

この操作を何回か間違えるので, その回数を出力せよ.

解法

 {s_{i - 1} + 1 \ne s_{i}} の個数を数えれば良い. また  {s_1 \ne 1} の場合があるので, それも数える.

 {O(n)}.

ソース

#include<bits/stdc++.h>

using namespace std;


int main()
{
  int N, S[1000];

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

  int ret = S[0] != 1;
  for(int i = 1; i < N; i++) {
    if(S[i - 1] + 1 != S[i]) ++ret;
  }

  cout << ret << endl;
}

Spiral Message

問題概要

各セルに  {1} 文字のアルファベットか '#' がかかれている  {n \times m(1 \le n, m \le 20)} のグリッド上を, 左下のセルから螺旋状に回って文字列を作る.

'#' の塊は何個あるか.

解法

実際に文字列を作って数えればよい.

 {O(nm)}.

ソース

#include<bits/stdc++.h>

using namespace std;

const int vy[] = {-1, 0, 1, 0}, vx[] = {0, 1, 0, -1};

int main()
{
  int H, W;
  string S[20];
  bool used[20][20] = {{}};

  cin >> H >> W;
  for(int i = 0; i < H; i++) {
    cin >> S[i];
  }

  int ret = 0, rev = '#';
  int x = 0, y = H, v = 0;
  for(int i = 0; i < H * W; i++) {
    for(int k = 0; k < 4; k++) {
      int nx = x + vx[v], ny = y + vy[v];
      if(nx < 0 || nx >= W || ny < 0 || ny >= H || used[nx][ny]) {
        v = (v + 1) % 4;
        continue;
      }
      used[nx][ny] = true;
      x = nx, y = ny;
      if(rev == '#' && S[ny][nx] != '#') ++ret;
      rev = S[ny][nx];
      break;
    }
  }
  cout << ret << endl;
}

Mega Tic-Tac-Toe

問題概要

三目並べを拡張して以下のルールで考える.

  • 盤面の大きさ  {n \times m(1 \le n, m \le 1000)}.
  • 一方の文字は O, もう一方は X.
  • 対角線上に自分の文字を, 縦, 横あるいは斜めに  {k(1 \le k \le 1000)} 個連続して置いたら勝ち. 盤面が与えられるので, その状態でどちらが勝っているかを出力せよ.

解法

貪欲にやるなら, あるマスを始点として縦横斜めに連続して  {k} 個並んでいるかどうか調べる. しかしこれは始点  {O(nm)} それぞれで  {k} 回数える必要があって  {O(nmk)} で TLE.

そこで, それぞれのラインごとに累積和を求めておけば  {O(nm)}.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int g, w, h, k;
  string s[1000];

  cin >> g;
  while(g--) {
    cin >> h >> w >> k;
    for(int i = 0; i < h; i++) {
      cin >> s[i];
    }

    int a = 0, b = 0;
    for(int i = 0; i < h; i++) {
      int sum = 0;
      for(int j = 0; j < w; j++) {
        if(j == 0 || s[i][j - 1] == s[i][j]) {
          ++sum;
        } else {
          sum = 1;
        }
        if(s[i][j] == 'O') a = max(a, sum);
        else if(s[i][j] == 'X') b = max(b, sum);
      }
    }
    for(int j = 0; j < w; j++) {
      int sum = 0;
      for(int i = 0; i < h; i++) {
        if(i == 0 || s[i - 1][j] == s[i][j]) {
          ++sum;
        } else {
          sum = 1;
        }
        if(s[i][j] == 'O') a = max(a, sum);
        else if(s[i][j] == 'X') b = max(b, sum);
      }
    }
    for(int i = 0; i < w; i++) {
      int sum = 0;
      for(int j = 0; j < h && i + j < w; j++) {
        if(j == 0 || s[j - 1][i + j - 1] == s[j][i + j]) {
          ++sum;
        } else {
          sum = 1;
        }
        if(s[j][i + j] == 'O') a = max(a, sum);
        else if(s[j][i + j] == 'X') b = max(b, sum);
      }
    }
    for(int i = 0; i < w; i++) {
      int sum = 0;
      for(int j = 0; j < h && i - j >= 0; j++) {
        if(j == 0 || s[j - 1][i - j + 1] == s[j][i - j]) {
          ++sum;
        } else {
          sum = 1;
        }
        if(s[j][i - j] == 'O') a = max(a, sum);
        else if(s[j][i - j] == 'X') b = max(b, sum);
      }
    }
    for(int i = 1; i < h; i++) {
      int sum = 0;
      for(int j = 0; i + j < h && j < w; j++) {
        if(j == 0 || s[i + j - 1][j - 1] == s[i + j][j]) {
          ++sum;
        } else {
          sum = 1;
        }
        if(s[i + j][j] == 'O') a = max(a, sum);
        else if(s[i + j][j] == 'X') b = max(b, sum);
      }
    }
    for(int i = 1; i < h; i++) {
      int sum = 0;
      for(int j = 0; i + j < h && j < w; j++) {
        if(j == 0 || s[i + j - 1][w - j] == s[i + j][w - j - 1]) {
          ++sum;
        } else {
          sum = 1;
        }
        if(s[i + j][w - j - 1] == 'O') a = max(a, sum);
        else if(s[i + j][w - j - 1] == 'X') b = max(b, sum);
      }
    }

    if((a >= k && b >= k) || (a < k && b < k)) cout << "NONE" << endl;
    else if(a >= k) cout << "WIN" << endl;
    else cout << "LOSE" << endl;
  }
}

Flexible Tree Visitor Pattern (OOP)

問題概要

 {n(2 \le n \le 10^5)} 頂点の根付き木が与えられる. 各頂点は赤色か緑色で塗られていて値  {x_i(1 \le x_i \le 10^3)} をもつ.

Tree クラスを使って木を作り, Tree Vis クラスを継承して以下の  {3} つのクラスを作成せよ.

  • 葉に書かれた値の和を求める.
  • 赤い頂点に書かれた値の総乗を求める.
  • 緑色の葉に書かれた値の総和と, 葉ではない深さが偶数のノードの書かれた値の総和の絶対値を求める.

解法

クラスが書かれたソースをよく読んで実装する.

ソース

#include<bits/stdc++.h>

using namespace std;
class SumInLeavesVisitor : public TreeVis
{
  int sum = 0;

public:
  int getResult()
  {
    //implement this
    return (sum);
  }

  void visitNode(TreeNode *node)
  {
    //implement this
  }

  void visitLeaf(TreeLeaf *leaf)
  {
    //implement this
    sum += leaf->getValue();
  }
};


class ProductOfRedNodesVisitor : public TreeVis
{
  const int mod = 1e9 + 7;
  int sum = 1;

public:
  int getResult()
  {
    //implement this
    return (sum);
  }

  void visitNode(TreeNode *node)
  {
    //implement this
    if(node->getColor() == RED) {
      sum = 1LL * sum * node->getValue() % mod;
    }
  }

  void visitLeaf(TreeLeaf *leaf)
  {
    //implement this
    if(leaf->getColor() == RED) {
      sum = 1LL * sum * leaf->getValue() % mod;
    }
  }

};

class FancyVisitor : public TreeVis
{
  int sum = 0;

public:
  int getResult()
  {
    //implement this
    return (max(-sum, sum));
  }

  void visitNode(TreeNode *node)
  {
    //implement this
    if(node->getDepth() % 2 == 0) {
      sum += node->getValue();
    }
  }

  void visitLeaf(TreeLeaf *leaf)
  {
    //implement this
    if(leaf->getColor() == GREEN) {
      sum -= leaf->getValue();
    }
  }
};

int N, X[100000], C[100000];
vector< int > tree[100000];

Tree *makeTree(int idx, int depth = 0, int par = -1)
{
  if(tree[idx].size() == 1) {
    return (new TreeLeaf(X[idx], C[idx] == 0 ? RED : GREEN, depth));
  } else {
    TreeNode *node = new TreeNode(X[idx], C[idx] == 0 ? RED : GREEN, depth);
    for(int to : tree[idx]) {
      if(to != par) node->addChild(makeTree(to, depth + 1, idx));
    }
    return (node);
  }
}

Tree *solve()
{
  //read the tree from STDIN and return its root as a return value of this function

  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &X[i]);
  }
  for(int i = 0; i < N; i++) {
    scanf("%d", &C[i]);
  }
  for(int i = 0; i < N - 1; i++) {
    int V, U;
    scanf("%d %d", &V, &U);
    --V, --U;
    tree[V].push_back(U);
    tree[U].push_back(V);
  }
  return (makeTree(0));
}

Game Of Numbers

問題概要

Alice と Bob でゲームをする. Alice が先攻で  {l} 以上  {r(1 \le l \le r \le 10^6)} 以下の数を選んで現在の値に足す操作を交互に繰り返す. 最初に値を  {k(1 \le k \le 10^7)} 以上にできたらそのプレイヤーの勝ちである.

お互いに最適に行動する時どちらが勝つか求めよ.

解法

 {k \le r} のとき明らかに Alice が勝ち.

それ以外のケースについて考える. 小さいケースなら全探索で勝敗を求めることができるので, 実験をするといい感じのアレが出てくるのでそれを式にする.

 {O(1)}.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int G, L, R, K;
  cin >> G;
  while(G--) {
    cin >> L >> R >> K;
    if(K > R && (K - R - 1) % (L + R) < L) cout << "Bob" << endl;
    else cout << "Alice" << endl;
  }
}

Coconut Plantation

問題概要

 {r \times c(5 \le r \times c \le 10^5 + 50^2)} のグリッドがある. 各セルにはココナッツが  {1} 個植えられている.

 {n(1 \le n \le 10^5 + 50^2)} 回にわたって 長方形  {(x_{1_{i}}, y_{1_{i}}), (x_{2_{i}}, y_{2_{i}})} 内のセル一様に水を  {1} 与える.

最終的に与えられた水が  {m(\le n)} 未満のセルにあるココナッツは枯れる.

ココナッツを収穫するために労働者を雇う. 労働者はあるセルから東西南北いずれかの直線に沿ってココナッツを収穫する. 枯れたココナッツのセルに到達するか範囲外に出ると収穫を終える.

枯れていないすべてのココナッツを収穫するために必要な労働者の人数の最小値を求めよ.

解法

長方形内のそれぞれのセルに与えられた水の数を数える. これは二次元の imos 法を使えば各クエリ  {O(1)} でできて, 最後に  {1} 回で  {O(rc)} で求めれば良い.

必要な労働者の数を求める. 枯れていないセルは縦方向か横方向の枯れていないセルの連結成分どちらかに属す必要があることを考えると,これは二部グラフの最小点被覆なので最大マッチングを求めればよい.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

struct Bipartite_Matching
{
  vector< vector< int > > graph;
  vector< int > match;
  vector< bool > used;

  Bipartite_Matching(int n)
  {
    graph.resize(n);
  }

  void add_edge(int u, int v)
  {
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  bool dfs(int v)
  {
    used[v] = true;
    for(int i = 0; i < graph[v].size(); i++) {
      int u = graph[v][i], w = match[u];
      if(w == -1 || (!used[w] && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching()
  {
    int ret = 0;
    match.assign(graph.size(), -1);
    for(int i = 0; i < graph.size(); i++) {
      if(match[i] == -1) {
        used.assign(graph.size(), false);
        ret += dfs(i);
      }
    }
    return (ret);
  }
};

struct CumulativeSum2D
{
  vector< vector< int64 > > data;

  CumulativeSum2D(int H, int W) : data(H, vector< int64 >(W, 0))
  {
  };

  inline void add(int y, int x, int z)
  {
    if(y >= data.size() || x >= data[0].size()) return;
    data[y][x] += z;
  }

  void build()
  {
    for(int i = 1; i < data.size(); i++) {
      for(int j = 0; j < data[i].size(); j++) {
        data[i][j] += data[i - 1][j];
      }
    }
    for(int i = 0; i < data.size(); i++) {
      for(int j = 1; j < data[i].size(); j++) {
        data[i][j] += data[i][j - 1];
      }
    }
  }

  inline int64 query(int y, int x)
  {
    return (data[y][x]);
  }
};

int P, W, H, N, K;

int main()
{
  cin >> P;
  while(P--) {
    cin >> W >> H >> N >> K;
    CumulativeSum2D grid(H, W);
    for(int i = 0; i < N; i++) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      ++x2, ++y2;
      grid.add(y1, x1, +1);
      grid.add(y1, x2, -1);
      grid.add(y2, x1, -1);
      grid.add(y2, x2, +1);
    }
    grid.build();

    Bipartite_Matching graph(H * W * 2);
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        if(grid.query(i, j) >= K) {
          int p = i, q = j;
          while(p > 0 && grid.query(p - 1, j) >= K) p--;
          while(q > 0 && grid.query(i, q - 1) >= K) q--;
          graph.add_edge(p * W + j, i * W + q + H * W);
        }
      }
    }
    cout << graph.bipartite_matching() << endl;
  }
}

Area of Triangles

問題概要

 {n(2 \le n \le 100)} 個の三角形が与えられるので, 三角形で覆われた面積を求めよ. 重複しているところを重複して数えないように注意すること.

解法

ブーリアン演算なのでどこかのライブラリを拾ってきてそれを写経した.

Points and Fences

問題概要

二次元平面上に  {n(1 \le n \le 10^5)} 個の点がある. それぞれの点は  {p_i = (x_i, y_i) (-10^9 \le x_i, y_i \le 10^9)} にある.

 {q(1 \le n \le 10^5)} 個の  {3} 種類のクエリが時系列順に与えれれるので処理せよ.

  •  {1. add\ f_{x_1}\ f_{y_1}\ f_{x_2}\ f_{y_2}}: その  {4} 点を頂点としてフェンスを設置する.  {x} 軸と  {y} 軸に平行で, フェンスが他のフェンスに接触や交差することはない.
  •  {2. delete\ j}:  {j} 番目に設置したフェンスを撤去する.
  •  {3. query\ a\ b}: 点  {p_a} と点  {p_b} 間にパスが存在するか判定する. 経路上でフェンスで遮られている場合はパスが存在しない.

解法

おもしろかった.

 {p_a} と点  {p_b} 間にパスが存在するかどうかは, 点  {p_a} と点  {p_b} を内包するフェンスが同じかどうかである.

これを考えるとフェンスを追加する操作は長方形内の点をそのフェンスに属させる操作と考える事が出来る. それぞれのフェンスに乱数  {r_i} を割り当てておけば長方形内に一様に  {r_i} を xor 加算する操作に帰着でき, フェンスを除去する操作はもう一度同じ操作をすれば良い(一般にはゾブリストハッシュとよばれるテク).

ここで, 二次元だと大変なので列に対する xor 加算を考える. これは BIT ととても相性がよくて  {[x_1, x_2)} に加算するとき  {x_1} {r_i} を加え,  {x_2} {r_i} を加える操作をすれば良い( {2} 回 xor すればもとに戻るので).

二次元を考える.  {x} 軸方向を座標圧縮しておくとセグメント木に  {y} 方向を表す BIT を乗せれば解けそうなことがわかる.

 {O(q \log^2 n)}.

ソース

#include<bits/stdc++.h>

using namespace std;

struct BinaryIndexedTree
{
  vector< int > data;

  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }

  int sum(int k)
  {
    int ret = 0;
    for(++k; k > 0; k -= k & -k) ret ^= data[k];
    return (ret);
  }

  void add(int k, int x)
  {
    for(++k; k < data.size(); k += k & -k) data[k] ^= x;
  }
};

struct SegmentTree2D
{
  vector< BinaryIndexedTree > add;
  vector< vector< int > > vs;
  int sz;

  SegmentTree2D(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    vs.resize(2 * sz - 1);
  }

  void set(int k, int height)
  {
    vs[k + sz - 1].push_back(height);
  }

  void build()
  {
    for(int k = sz - 1; k < vs.size(); k++) {
      sort(begin(vs[k]), end(vs[k]));
    }
    for(int k = sz - 2; k >= 0; k--) {
      vs[k].resize(vs[2 * k + 1].size() + vs[2 * k + 2].size());
      merge(begin(vs[2 * k + 1]), end(vs[2 * k + 1]),
            begin(vs[2 * k + 2]), end(vs[2 * k + 2]),
            begin(vs[k]));
    }
    for(int k = 0; k < vs.size(); k++) {
      add.emplace_back(BinaryIndexedTree(vs[k].size() + 1));
    }
  }

  inline int lb(int k, int height)
  {
    return (lower_bound(begin(vs[k]), end(vs[k]), height) - begin(vs[k]));
  }

  void update(int a, int b, int Low, int High, int x, int k, int l, int r)
  {
    if(a >= r || b <= l) {
      return;
    } else if(a <= l && r <= b) {
      add[k].add(lb(k, Low), x);
      add[k].add(lb(k, High), x);
    } else {
      update(a, b, Low, High, x, 2 * k + 1, l, (l + r) >> 1);
      update(a, b, Low, High, x, 2 * k + 2, (l + r) >> 1, r);
    }
  }

  void update(int a, int b, int Low, int High, int x)
  {
    update(a, b, Low, High, x, 0, 0, sz);
  }

  int get(int k, int height)
  {
    k += sz - 1;
    int ret = add[k].sum(lb(k, height));
    while(k > 0) {
      k = (k - 1) >> 1;
      ret ^= add[k].sum(lb(k, height));
    }
    return (ret);
  }
};

int xor128(void)
{
  static int x = 123456789;
  static int y = 362436069;
  static int z = 521288629;
  static int w = 88675123;
  int t;

  t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

int main()
{
  int N, Q, X[100000], Y[100000];
  bool T[100000];
  int A[100000], B[100000], C[100000], D[100000], R[100000];
  vector< int > xs;

  cin >> N >> Q;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
    xs.push_back(X[i]);
  }
  for(int i = 0; i < Q; i++) {
    string t;
    cin >> t;
    if(t[0] == 'a') {
      T[i] = false;
      cin >> A[i] >> C[i] >> B[i] >> D[i];
      ++B[i], ++D[i];
      R[i] = xor128();
    } else if(t[0] == 'd') {
      T[i] = false;
      cin >> A[i];
      --A[i];
      R[i] = R[A[i]];
      D[i] = D[A[i]];
      C[i] = C[A[i]];
      B[i] = B[A[i]];
      A[i] = A[A[i]];
    } else {
      T[i] = true;
      cin >> A[i] >> B[i];
      --A[i], --B[i];
    }
  }
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));

  SegmentTree2D tree(xs.size());
  for(int i = 0; i < N; i++) {
    X[i] = lower_bound(begin(xs), end(xs), X[i]) - begin(xs);
    tree.set(X[i], Y[i]);
  }
  for(int i = 0; i < Q; i++) {
    if(!T[i]) {
      A[i] = lower_bound(begin(xs), end(xs), A[i]) - begin(xs);
      B[i] = lower_bound(begin(xs), end(xs), B[i]) - begin(xs);
    }
  }
  tree.build();

  for(int i = 0; i < Q; i++) {
    if(T[i]) {
      if(tree.get(X[A[i]], Y[A[i]]) == tree.get(X[B[i]], Y[B[i]])) {
        cout << "YES" << endl;
      } else {
        cout << "NO" << endl;
      }
    } else {
      tree.update(A[i], B[i], C[i], D[i], R[i]);
    }
  }
}