University CodeSprint 3 - ei1333の日記

全完したぞい. パーカーを得た.

A Small Step Toward Calculators

www.hackerrank.com

問題概要

x+y または x-y の形式の文字列が与えられる. ここで ${x}$ と ${y}$ は一桁の非負整数である.

加減算した結果を出力せよ.

解法

忘れた.

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

int main()
{
  int64 A, B;
  char o;
  scanf("%lld%c%lld", &A, &o, &B);
  if(o == '-') printf("%lld\n", A - B);
  else printf("%lld\n", A + B);
}

Erupting Volcanoes

www.hackerrank.com

問題概要

えーん.

解法

問題文にかかれているため.

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

int N, M;
int mat[300][300], ret;

int main()
{
  scanf("%d", &N);
  scanf("%d", &M);

  for(int i = 0; i < M; i++) {
    int x, y, w;
    scanf("%d %d %d", &x, &y, &w);
    for(int j = 0; j < N; j++) {
      for(int k = 0; k < N; k++) {
        mat[j][k] += max(0, w - max(abs(y - j), abs(x - k)));
        ret = max(ret, mat[j][k]);
      }
    }
  }
  printf("%d\n", ret);
}

The Snake vs the Wind

www.hackerrank.com

問題概要

${n \times n(2 \le n \le 60)}$ グリッドがあって, 風が 4 方向どちらかに吹いている.

最初はどこかの角にいる. 上下左右に移動してすべてのマスを訪れる. 直前のマスには移動できない. いまいるマスから, 追い風の向き, 風と垂直の向き, 向かい風の向きの順に見て移動できるマスがあったらそのマスに進むことお繰り返す.

各マスに訪れる順番を出力せよ.

解法

これも問題文に書かれているねね

英文をよむだけになっている.

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

const string temp = "nwse";
const int vy[] = {-1, 0, 1, 0}, vx[] = {0, -1, 0, 1};

int N, Y, X, D;
char c;
int mat[60][60];

int main()
{
  memset(mat, -1, sizeof(mat));

  cin >> N >> c >> Y >> X;
  D = temp.find(c);

  mat[Y][X] = 1;
  for(int i = 2; i <= N * N; i++) {
    for(int j : {0, 1, 3, 2}) {
      int ny = Y + vy[(D + j) % 4], nx = vx[(D + j) % 4] + X;
      if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
      if(~mat[ny][nx]) continue;
      Y = ny, X = nx;
      mat[Y][X] = i;
      break;
    }
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(j > 0) cout << " ";
      cout << mat[i][j];
    }
    cout << endl;
  }
}

Bob's Game

www.hackerrank.com

問題概要

${n \times n(2 \le n \le 1000)}$ の二次元グリッドがあって, それぞれのマスはキングが ${1}$ 個ある, 空, 障害物があるのいずれかである.

${2}$ 人のプレイヤーで以下の行動を交互に繰り返す. 行動が出来なかったプレイヤーが負である.

${1}$ つのキングを選んでそれを障害物がないかつグリッド内の左, 上, 左上の 3 方向のいずれかに移動させる.

両者が最適に行動した時, 先攻のプレイヤーが勝てるかどうか判定し, 勝てるときは勝つための最初の動かし方の通り数を出力せよ.

解法

grundy数を知っていますか? 僕は知ってます(完

まずそれぞれのマスに対して, grundy数を求める. メモ化できるため ${O(n^2)}$ .

で, 最初にキングがいるマスの grundy数の xor をとって非 0 なら先手必勝.

動かし方は移動させた後に xor が 0 になるような個数で, これはできるため終わり.

ソース

最初, 最初の動かし方じゃなくて, ゲーム全体の動かし方の組み合わせだと思って不可能ってなってた. ちゃんと読もうね.

#include<bits/stdc++.h>

using namespace std;

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

int Q, N;
string S[1000];
int dp[1000][1000];

int rec(int y, int x)
{
  if(~dp[y][x]) return (dp[y][x]);
  set< int > grundy;
  for(int i = 0; i < 3; i++) {
    int ny = y + vy[i], nx = x + vx[i];
    if(ny >= 0 && nx >= 0 && S[ny][nx] != 'X') grundy.emplace(rec(ny, nx));
  }
  int mex = 0;
  while(grundy.count(mex)) mex++;
  return (dp[y][x] = mex);
}


int main()
{
  cin >> Q;
  while(Q--) {
    cin >> N;
    vector< pair< int, int > > put;
    for(int i = 0; i < N; i++) {
      cin >> S[i];
      for(int j = 0; j < N; j++) {
        if(S[i][j] == 'K') put.emplace_back(i, j);
      }
    }
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) rec(i, j);
    }
    int ss = 0;
    for(auto &p : put) ss ^= dp[p.first][p.second];
    int mult = 0;

    for(auto &p : put) {
      for(int i = 0; i < 3; i++) {
        int ny = p.first + vy[i], nx = p.second + vx[i];
        if(ny >= 0 && nx >= 0 && S[ny][nx] != 'X') {
          if(ss ^ dp[p.first][p.second] ^ dp[ny][nx]) continue;
          ++mult;
        }
      }
    }

    if(ss == 0) cout << "LOSE" << endl;
    else cout << "WIN " << mult << endl;
  }
}

Black White Tree

www.hackerrank.com

問題概要

${n(1 \le n \le 10^5)}$ 頂点の木が与えられる. それぞれの頂点は黒色か白色で塗られている.

この木から ${1}$ つの連結成分を取り出す. 連結成分内の頂点を見たとき, 黒色と白色の頂点数の差の最大値と, そのときに選んだ頂点の番号を出力せよ.

解法

黒を +1, 白を -1 とみなすと, 連結成分の総和の絶対値が求めたいものになっている.

要するに, 和が最大の連結成分と最小の連結成分を求めたい気持ちになる. ここで最小の連結成分はプラスマイナスを反転させれば最大と同じなので, 最大のアを解くことにする.

sub_large[x] := 頂点 ${x}$ を根とする部分木内の連結成分の最大の和
con_large[x] := 頂点 ${x}$ を根とする部分木で, 頂点 ${x}$ を含む連結成分のうち最大の和

とすれば, なんかいい感じに木DPしてえいすれば求まる. con_large[x] は初期値は自分の色の値で, それに子どもの con_large をみたときに正なら足すみたいなことをすれば求めることができて, sub_large[x] は子どもの頂点の sub_large と, con_large[x] との max みたいになる. 日本語難しくない?難しいね

ここまではまあいけるんですが復元がむずかしかった(con_large が最大となるアを選べばいいんだけど最大が複数あることがあって険しいみたいに考えるとむずかしくなる).

今回は con_large が最大の頂点を見つけて, その頂点を根として dfs しなおして, con_large[] が正の頂点のみで到達できる頂点をたどるみたいなことをして復元している.

ソース

この辺からむずかしくなってくるうし...

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

int N, W[100000];
vector< int > g[100000];
int sub_large[500000], con_large[500000];
vector< int > vs;

int dfs(int idx, int par = -1)
{
  sub_large[idx] = con_large[idx] = W[idx];
  for(auto &to : g[idx]) {
    if(par == to) continue;
    dfs(to, idx);
    con_large[idx] += max(0, con_large[to]);
    sub_large[idx] = max(sub_large[idx], sub_large[to]);
  }
  sub_large[idx] = max(sub_large[idx], con_large[idx]);
  return (sub_large[idx]);
}

void dfs2(int idx, int par = -1)
{
  vs.emplace_back(idx);
  for(auto &to : g[idx]) {
    if(par == to) continue;
    if(con_large[to] > 0) dfs2(to, idx);
  }
}

int main()
{
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> W[i];
    if(W[i] == 0) W[i] = -1;
  }
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  int latte = dfs(0);
  for(int i = 0; i < N; i++) W[i] *= -1;
  int malta = dfs(0);

  if(latte > malta) {
    cout << latte << endl;
    for(int i = 0; i < N; i++) W[i] *= -1;
    dfs(0);

    int root = 0;
    for(int i = 0; i < N; i++) if(latte == con_large[i]) root = i;
    dfs(root);
    dfs2(root);
  } else {
    cout << malta << endl;
    int root = 0;
    for(int i = 0; i < N; i++) if(malta == con_large[i]) root = i;
    dfs(root);
    dfs2(root);
  }
  sort(begin(vs), end(vs));
  cout << vs.size() << endl;
  for(int i : vs) cout << i + 1 << " ";
  cout << endl;
}

March of the King

www.hackerrank.com

問題概要

${8 \times 8}$ の二次元グリッドが与えられて, それぞれのマスにはアルファベット ${1}$ 文字が書かれている.

この中から ${k(1 \le k \le 11)}$ 文字の文字列 ${s_i}$ を探したい. あるマスからはじめて, 同じマスを ${2}$ 度通らない, また文字列 ${s_i}$ にマッチするように周囲 ${8}$ マスのいずれかのマスを辿って移動していく.

何通りの移動方法があるか求めよ.

解法

効率的なアルゴリズムがあるとは思えないため困る. DFSして全探索するしかないように見えるが, それだと間に合わない. 解けないね(終了

ここで天使からのお告げにより, なんとなく半分で分けてみたい気持ちになる. 長さ ${11}$ のパスを列挙するのは険しそうだし探索の無駄も多そうだが, 長さ ${6}$ のパスを列挙するのは簡単.

すると, 長さ ${\frac k 2}$ のパスと ${\frac k 2}$ のパスを組みわせる問題に帰着できるのだが, やっぱり効率的なアルゴリズムが浮かばないため終わり.

唐突だが ${8 \times 8 = 64}$ なので unsigned long long を用いることにより, それぞれのパスについて既に訪れたマスに bit をたてた表記で表すことができる. ${2}$ つのパスの and をとって, ${0}$ ならば全てのマスは高々 ${1}$ 回しか通ってないことになる.

えーーー, ここでとりあえずビット演算は高速だと信じて愚直を書いてみるとなんか間に合ってしまうのでやったぜ

ソース

ホンマにこれ想定解かなあ.

なんか全部同じ文字で ${k = 11}$ が自明に最悪ケースだが, 手元で実行するとループの回数は 1536670418 回っぽいのでシンプルだしこれくらい最近のコンピュータならまわってくれるのかなあという気持ちになる(は?.

#include<bits/stdc++.h>

using namespace std;

using int64 = unsigned long long;
int N;
string T, S[8];
bool v[8][8];
vector< int64 > latte[8][8], malta[8][8];

inline void rec(int idx, int sz, int sx, int sy, int x, int y, int64 used, int which)
{
  if(T[idx] != S[y][x] || v[y][x]) {
    return;
  }

  if(idx + 1 == sz) {
    if(which == 0) latte[y][x].emplace_back(used);
    else malta[sy][sx].emplace_back(used);
    return;
  }

  v[y][x] = true;

  for(int i = -1; i <= 1; i++) {
    for(int j = -1; j <= 1; j++) {
      int nx = i + x, ny = j + y;
      if(nx < 0 || ny < 0 || nx >= 8 || ny >= 8) continue;
      rec(idx + 1, sz, sx, sy, nx, ny, used | (1uLL << (ny * 8 + nx)), which);
    }
  }

  v[y][x] = false;
}

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

  int med = (N + 1) / 2;

  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      rec(0, med, j, i, j, i, 1uLL << (i * 8 + j), 0);
      rec(med - 1, N, j, i, j, i, 0, 1);
    }
  }

  int64 ret = 0;
  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      for(auto &k : latte[i][j]) {
        for(auto &o : malta[i][j]) {
          if(!(k & o)) ++ret;
        }
      }
    }
  }
    
  cout << ret << endl;
}

Simple Tree Counting

www.hackerrank.com

問題概要

${n(1 \le n \le 1.2 \times 10^5)}$ 頂点の木が与えられる. ${i}$ 番目の辺は頂点 ${a_i}$ と ${b_i(1 \le a_i, b_i \le n)}$ を結んでいて, 色 ${c_i(1 \le c_i \le 10^6)}$ で着色されている.

(以下, 翻訳力がなくて難読なので原文読んだほうが良さそう(ア

共通の色を持つ辺のみで連結成分を組む. ある辺が属する連結成分は ${1}$ つだが, 頂点に関しては複数属しうる. ここで ${X_i}$ を ${i}$ 番目の辺が属する連結成分の頂点集合と定義する. また ${S_c}$ を色 ${c}$ からなる連結成分の頂点集合の集合と定義する.

さらに頂点集合 ${X}$ に対して ${P(X)}$ を ${\frac {k(k - 1)} 2}$ と定義する. ${k}$ は頂点数である. 頂点集合の集合 ${S}$ に対して ${T(S)}$ を ${\sum_{X \in S} P(X)}$ と定義する.

時系列順に ${q(1 \le q \le 1.2 \times 10^5)}$ 個のクエリが与えられるので全て処理せよ.

${i}$ と ${c}$ が与えられるので, ${i}$ 番目の辺を色 ${c}$ に変更する.
${l}$ と ${r}$ が与えられるので, ${\sum_{c=l}^{r} T(S_c)}$ を求める.
${i}$ が与えられるので ${P(X_i)}$ を求める.

解法

クエリがあるとアなので, まずはクエリが与えられない場合で, それぞれのクエリ3の値を求める方法について考えてみる.

少し考えると, 色ごとに Union-Find を持っておけばいいことがわかる. 具体的に色 ${c}$ の Union-Find は, 色 ${c}$ を持つすべての辺の両端に属する頂点を持つ(座圧しておく). そして, すべての辺の両端の 2 頂点同士で unite しておけば, 容易に辺 ${i}$ が属する連結成分の頂点数を求めることができる.

また適当に累積和を使えばクエリ2も求めることができる.

クエリがある場合について考えてみる. 上記の考察より, 色を変更する操作は変更前の辺の色の Union-Find の unite を取り消して(辺の削除), 新しい色の Union-Find の unite 操作に帰着できる.

unite の逆は不可能やろ, うしーうしーと鳴いていると, Decomposable searching problem - オフラインの場合 - yukicoder の Batched Dynamic Connectivity の項目にたどり着く. できそうですね. やりたいことはこれです. ありがとう yukicoder.

大まかはURL先の記事の説明通りにやればOK. セグ木に区間加算で辺をのせたあとにDFSするイメージ. Union-Find の undo 操作は stack で詰んでおけば簡単. 累積和の部分を BIT で持っておけばクエリ2にも対応可能. 細かいことは下のソースコード参照(丸投げ. 座圧を無限回している.

計算量は ${O((n + m) \log^2 n)}$ となる.

ソース

セグ木上をDFS, 賢すぎる.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

template< class T >
struct BinaryIndexedTree
{
  vector< T > data;

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

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

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

struct UnionFind
{
  vector< int > data;
  stack< pair< int, int > > st;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    st.emplace(x, data[x]);
    st.emplace(y, data[y]);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }

  void undo()
  {
    auto p = st.top();
    st.pop();
    auto q = st.top();
    st.pop();
    data[p.first] = p.second;
    data[q.first] = q.second;
  }
};


struct Beet_Aizu
{
  typedef tuple< int, int, int > edge;

  int n, sz;
  vector< vector< edge > > edges;
  vector< pair< pair< int, int >, edge > > segs;
  map< edge, int > cnt, appear;

  Beet_Aizu(int n) : n(n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    edges.resize(2 * sz - 1);
  }

  void insert(int idx, int color, int x, int y)
  {
    if(x > y) swap(x, y);
    auto e = make_tuple(color, x, y);
    if(cnt[e]++ == 0) appear[e] = idx;
  }

  void erase(int idx, int color, int x, int y)
  {
    if(x > y) swap(x, y);
    auto e = make_tuple(color, x, y);
    if(--cnt[e] == 0) segs.emplace_back(make_pair(appear[e], idx), e);
  }

  void add(int a, int b, const edge e, int k, int l, int r)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      int x, y, z;
      tie(x, y, z) = e;
      edges[k].emplace_back(e);
      return;
    }
    add(a, b, e, 2 * k + 1, l, (l + r) >> 1);
    add(a, b, e, 2 * k + 2, (l + r) >> 1, r);
  }

  void add(int a, int b, const edge &e)
  {
    add(a, b, e, 0, 0, sz);
  }

  void execute() { execute(0); }

  void execute(int k);

  void build()
  {
    for(auto &p : cnt) {
      if(p.second > 0) segs.emplace_back(make_pair(appear[p.first], sz), p.first);
    }
    for(auto &s : segs) {
      int a, b, c;
      tie(a, b, c) = s.second;
      add(s.first.first, s.first.second, s.second);
    }

    for(auto &s : edges) {
      for(auto &p : s) {
        int x, y, z;
        tie(x, y, z) = p;
      }
    }
  }
};

int N, Q;
int A[120000], B[120000], C[120000];
int X[120000], Y[120000], Z[120000];
vector< int > order[1000000];
int64 ans[120000];
vector< UnionFind > ufs;
BinaryIndexedTree< int64 > bit(400001);
vector< pair< int, int64 > > vs[400001];

void Beet_Aizu::execute(int k)
{
  for(auto &e : edges[k]) {
    int a, b, c;
    tie(a, b, c) = e;
    int64 l = ufs[a].size(b), r = ufs[a].size(c);
    int64 add = 0;
    add -= l * (l - 1) / 2;
    add -= r * (r - 1) / 2;
    add += (l + r) * (l + r - 1) / 2;
    vs[k].emplace_back(a, add);
    bit.add(a, add);
    ufs[a].unite(b, c);
  }

  if(k < sz - 1) {
    execute(2 * k + 1);
    execute(2 * k + 2);
  } else if(k - (sz - 1) < n) {
    int query_index = k - (sz - 1);
    if(X[query_index] == 3) {
      int sz = ufs[Z[query_index]].size(Y[query_index]);
      ans[query_index] = 1LL * sz * (sz - 1) / 2;
    } else if(X[query_index] == 2) {
      ans[query_index] = bit.sum(Z[query_index]) - bit.sum(Y[query_index] - 1);
    }
  }
  for(auto &e : edges[k]) {
    int a, b, c;
    tie(a, b, c) = e;
    ufs[a].undo();
  }
  for(auto &s : vs[k]) bit.add(s.first, -s.second);
}

int main()
{
  scanf("%d", &N);
  vector< int > appear;
  for(int i = 0; i + 1 < N; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
    --A[i], --B[i], --C[i];
    order[C[i]].emplace_back(A[i]);
    order[C[i]].emplace_back(B[i]);
    appear.emplace_back(C[i]);
  }
  scanf("%d", &Q);
  for(int i = 0; i < Q; i++) {
    scanf("%d %d", &X[i], &Y[i]);
    if(X[i] <= 2) scanf("%d", &Z[i]);
    --Y[i];
    if(X[i] == 1) {
      --Z[i];
      order[Z[i]].emplace_back(A[Y[i]]);
      order[Z[i]].emplace_back(B[Y[i]]);
      appear.emplace_back(Z[i]);
    } else if(X[i] == 2) {
      --Z[i];
      appear.emplace_back(Y[i]);
      appear.emplace_back(Z[i]);
    }
  }
  sort(begin(appear), end(appear));
  appear.erase(unique(begin(appear), end(appear)), end(appear));
  for(auto &color : appear) {
    if(color < 0 || order[color].empty()) continue;
    sort(begin(order[color]), end(order[color]));
    order[color].erase(unique(begin(order[color]), end(order[color])), end(order[color]));
  }
  Beet_Aizu beet(Q);

  auto latte = [&](int color)
  {
    return (lower_bound(begin(appear), end(appear), color) - begin(appear));
  };

  auto access = [&](int color, int idx)
  {
    return (lower_bound(begin(order[color]), end(order[color]), idx) - begin(order[color]));
  };

  for(int i = 0; i < N - 1; i++) {
    beet.insert(0, latte(C[i]), access(C[i], A[i]), access(C[i], B[i]));
  }
  for(int i = 0; i < Q; i++) {
    if(X[i] == 1) {
      beet.erase(i, latte(C[Y[i]]), access(C[Y[i]], A[Y[i]]), access(C[Y[i]], B[Y[i]]));
      C[Y[i]] = Z[i];
      beet.insert(i, latte(C[Y[i]]), access(C[Y[i]], A[Y[i]]), access(C[Y[i]], B[Y[i]]));
    } else if(X[i] == 2) {
      Y[i] = latte(Y[i]);
      Z[i] = latte(Z[i]);
    } else if(X[i] == 3) {
      Z[i] = latte(C[Y[i]]);
      Y[i] = access(C[Y[i]], A[Y[i]]);
    }
  }
  beet.build();
  for(int i : appear) ufs.emplace_back(UnionFind(order[i].size()));
  beet.execute();
  for(int i = 0; i < Q; i++) {
    if(X[i] >= 2) printf("%lld\n", ans[i]);
  }
}