University CodeSprint 4

45 位. パーカーゲット.

Summer Lesson

www.hackerrank.com

問題概要

らずひるど

解法

らてまるた

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, M;
  cin >> N >> M;
  int sum[1000] = {};
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    sum[x]++;
  }
  for(int i = 0; i < M; i++) {
    cout << sum[i] << " ";
  }
  cout << endl;
}

Cubes and Cylinders

www.hackerrank.com

問題概要

種類の立方体のパッケージと, 個の円柱の容器がある.

種類 のパッケージの立方体の一辺の長さは で, それが 個ある.

容器 の円柱の底面の半径は で, 円柱の側面に触れないようにパッケージを 個入れられる.

最大何個のパッケージを容器に入れられるか.

解法

パッケージと容器を長さでソートして, 条件を満たすように雰囲気でたくさんいれる.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, M, R[500], C[500];

  cin >> N >> M;
  vector< pair< int, int > > package(N);
  for(int i = 0; i < N; i++) cin >> package[i].first;
  for(int i = 0; i < N; i++) cin >> package[i].second;
  sort(begin(package), end(package));
  for(int i = 0; i < M; i++) cin >> R[i];
  for(int i = 0; i < M; i++) cin >> C[i];

  vector< int > order(M);
  iota(begin(order), end(order), 0);
  sort(begin(order), end(order), [&](int a, int b)
  {
    return (R[a] > R[b]);
  });


  int ptr = (int) package.size() - 1;
  int ret = 0;
  for(auto &i : order) {
    while(ptr >= 0 && 2 * R[i] <= package[ptr].first * sqrt(2)) --ptr;
    while(ptr >= 0 && C[i] > 0) {
      while(package[ptr].second > 0 && C[i] > 0) {
        package[ptr].second--;
        --C[i];
        ++ret;
      }
      if(C[i] == 0) break;
      --ptr;
    }
  }
  cout << ret << endl;
}

Two Kings

www.hackerrank.com

問題概要

チェスボード上に つのキングがおかれている. それぞれの座標は である.

チェックボード上に最小の個数の駒(クイーン, ナイト, ビショップ, ルークから任意個) をおいて, つのキングをチェックメイトしたい.

ここでのチェックメイトは特殊で, その盤面でどのキングを 手動かした時も, 両方のキングがチェックされていると定義する.

解法

クイーンの動きがビショップとルークの上位互換なので実質 クイーンとナイトを つの駒を考えれば良い.

全探索するしかなくて, 問題文に書かれている通りに最悪をする.

ソース

#include <bits/stdc++.h>

using namespace std;

int mp[8][8];
int ans;
vector< tuple< char, int, int > > vv;
int X1, Y1, X2, Y2;
string T = "QN";
bool mark[8][8];
const int RX[] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int RY[] = {-1, -2, -2, -1, 1, 2, 2, 1};

bool isin(int x, int y)
{
  return (0 <= x && x < 8 && 0 <= y && y < 8);
}

bool checked()
{
  memset(mark, false, sizeof(mark));
  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      if(0 <= mp[i][j] && mp[i][j] < 2) {
        if(mp[i][j] == 0) {
          for(int k = -1; k <= 1; k++) {
            for(int l = -1; l <= 1; l++) {
              if(k == 0 && l == 0) continue;
              if(isin(i + k, j + l)) mark[i + k][j + l] = true;
            }
          }

          for(int k = 1; k <= 8; k++) {
            if(isin(i + k, j)) {
              mark[i + k][j] = true;
              if(mp[i + k][j] != -1) break;
            }
          }

          for(int k = 1; k <= 8; k++) {
            if(isin(i, j + k)) {
              mark[i][j + k] = true;
              if(mp[i][j + k] != -1) break;

            }
          }

          for(int k = 1; k <= 8; k++) {
            if(isin(i - k, j)) {
              mark[i - k][j] = true;
              if(mp[i - k][j] != -1) break;
            }
          }

          for(int k = 1; k <= 8; k++) {
            if(isin(i, j - k)) {
              mark[i][j - k] = true;
              if(mp[i][j - k] != -1) break;

            }
          }

          for(int k = 1; k <= 8; k++) {
            if(isin(i - k, j - k)) {
              mark[i - k][j - k] = true;
              if(mp[i - k][j - k] != -1) break;
            }
          }

          for(int k = 1; k <= 8; k++) {
            if(isin(i - k, j + k)) {
              mark[i - k][j + k] = true;
              if(mp[i - k][j + k] != -1) break;
            }
          }

          for(int k = 1; k <= 8; k++) {
            if(isin(i + k, j + k)) {
              mark[i + k][j + k] = true;
              if(mp[i + k][j + k] != -1) break;
            }
          }

          for(int k = 1; k <= 8; k++) {
            if(isin(i + k, j - k)) {
              mark[i + k][j - k] = true;
              if(mp[i + k][j - k] != -1) break;
            }
          }

        } else {
          for(int k = 0; k < 8; k++) {
            int nx = i + RX[k], ny = j + RY[k];
            if(isin(nx, ny)) mark[nx][ny] = true;
          }
        }
      }
    }
  }

  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      if(mp[i][j] >= 2) {
        if(!mark[i][j]) return (false);
      }
    }
  }
  return (true);
}

bool ischeckmate()
{
  mp[X1][Y1] = -1;
  for(int i = -1; i <= 1; i++) {
    for(int j = -1; j <= 1; j++) {
      if(!isin(X1 + i, Y1 + j)) continue;
      if(mp[X1 + i][Y1 + j] == 100) continue;
      if(i == 0 && j == 0) continue;
      int buff = mp[X1 + i][Y1 + j];
      mp[X1 + i][Y1 + j] = 1333;
      bool f = checked();
      mp[X1 + i][Y1 + j] = buff;
      if(!f) {
        mp[X1][Y1] = 100;
        return (false);
      }
    }
  }
  mp[X1][Y1] = 100;
  mp[X2][Y2] = -1;
  for(int i = -1; i <= 1; i++) {
    for(int j = -1; j <= 1; j++) {
      if(!isin(X2 + i, Y2 + j)) continue;
      if(mp[X2 + i][Y2 + j] == 100) continue;
      if(i == 0 && j == 0) continue;
      int buff = mp[X2 + i][Y2 + j];
      mp[X2 + i][Y2 + j] = 1333;
      bool f = checked();
      mp[X2 + i][Y2 + j] = buff;
      if(!f) {
        mp[X2][Y2] = 100;
        return (false);
      }
    }
  }
  mp[X2][Y2] = 100;
  return (true);
}

void createMap(int idx, int lastX = 0, int lastY = 0)
{
  if(idx >= ans) return;
  if(ischeckmate()) {
    ans = idx;
    vv.clear();
    for(int i = 0; i < 8; i++) {
      for(int j = 0; j < 8; j++) {
        if(0 <= mp[i][j] && mp[i][j] < 2) {
          vv.emplace_back(T[mp[i][j]], i, j);
        }
      }
    }
    return;
  }
  bool f = false;
  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      if(i == lastX && j == lastY) f = true;
      if(mp[i][j] != -1) continue;
      if(f) {
        for(int k = 1; k >= 0; k--) {
          mp[i][j] = k;
          createMap(idx + 1, i, j);
        }
        mp[i][j] = -1;
      }
    }
  }
}

int main()
{
  int Q;


  cin >> Q;
  while(Q--) {
    cin >> Y1 >> X1 >> Y2 >> X2;
    ans = 4;
    memset(mp, -1, sizeof(mp));
    mp[X1][Y1] = mp[X2][Y2] = 100;
    createMap(0);
    cout << ans << endl;
    assert(ans < 4);
    for(auto &p : vv) {
      char c;
      int x, y;
      tie(c, x, y) = p;
      cout << c << " " << y << " " << x << endl;
    }
  }
}

Maximum Permutation

www.hackerrank.com

問題概要

文字列 において, 文字列 の並び替えかつ最も部分文字列に現れる文字列のうち辞書順最小のものを求めよ.

解法

文字列 のある区間が の並び替えかどうかはいもすっぽくやると, 効率的に求まる.

条件を満たす区間の文字列をローリングハッシュを使って値に変換して, その値の出現回数を数え上げる. こうすることで, 出現回数のの最大値とそのときのハッシュ値を求めることができる.

条件を満たすハッシュ値のうち辞書順最小のものはSuffixArrayを使うと求まるため終わり.

ソース

#include <bits/stdc++.h>

using namespace std;

const int _base1 = 1e9 + 7;
const int _base2 = 1e9 + 3;


struct RollingHash
{
  const int _base;
  vector< unsigned > hashed, power;

  RollingHash(const string &s, int base) : _base(base)
  {
    int sz = s.size();
    hashed.assign(sz + 1, 0);
    power.assign(sz + 1, 0);

    power[0] = 1;
    for(int i = 0; i < sz; i++) {
      power[i + 1] = power[i] * _base;
    }
    for(int i = 0; i < sz; i++) {
      hashed[i + 1] = (hashed[i] + s[i]) * _base;
    }
  }

  unsigned get(int l, int r) // [l, r)
  {
    return ((hashed[r] - hashed[l] * power[r - l]));
  }

  unsigned connect(int h1, int h2, int h2len)
  {
    return (h1 * power[h2len] + h2);
  }

  int LCP(RollingHash &b, int l1, int r1, int l2, int r2)
  {
    int len = min(r1 - l1, r2 - l2);
    int low = -1, high = len + 1;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
      else high = mid;
    }
    return (low);
  }
};


struct SuffixArray
{
  vector< int > SA;
  string s;

  void Build_SA(const string &str)
  {
    s = str;
    SA.resize(s.size());
    iota(begin(SA), end(SA), 0);
    sort(begin(SA), end(SA), [&](const int &a, const int &b)
    {
      if(s[a] == s[b]) return (a > b);
      return (s[a] < s[b]);
    });
    vector< int > classes(s.size()), c(s.size()), cnt(s.size());
    for(int i = 0; i < s.size(); i++) {
      c[i] = s[i];
    }
    for(int len = 1; len < s.size(); len <<= 1) {
      for(int i = 0; i < s.size(); i++) {
        if(i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) {
          classes[SA[i]] = classes[SA[i - 1]];
        } else {
          classes[SA[i]] = i;
        }
      }
      iota(begin(cnt), end(cnt), 0);
      copy(begin(SA), end(SA), begin(c));
      for(int i = 0; i < s.size(); i++) {
        int s1 = c[i] - len;
        if(s1 >= 0) SA[cnt[classes[s1]]++] = s1;
      }
      classes.swap(c);
    }
  }

  int operator[](int k) const
  {
    return (SA[k]);
  }

  int size() const
  {
    return (s.size());
  }

  bool lt_substr(string &t, int si = 0, int ti = 0)
  {
    int sn = s.size(), tn = t.size();
    while(si < sn && ti < tn) {
      if(s[si] < t[ti]) return (true);
      if(s[si] > t[ti]) return (false);
      ++si, ++ti;
    }
    return (si >= sn && ti < tn);
  }

  int lower_bound(string &t)
  {
    int low = -1, high = SA.size();
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    return (high);
  }

  pair< int, int > lower_upper_bound(string &t)
  {
    int idx = lower_bound(t);
    int low = idx - 1, high = SA.size();
    t.back()++;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    t.back()--;
    return (make_pair(idx, high));
  }

  void output()
  {
    for(int i = 0; i < size(); i++) {
      cout << i << ": " << s.substr(SA[i]) << endl;
    }
  }
};

const int INF = 1 << 30;

void beet()
{
  string S, T;
  cin >> S >> T;
  vector< int > vi(26, 0), si(26, 0);
  for(auto &c : S) vi[c - 'a']++;
  RollingHash latte(T, _base1);
  RollingHash malta(T, _base2);
  map< pair< unsigned, unsigned >, int > mp;
  for(int i = 0; i < T.size(); i++) {
    if(i >= S.size()) si[T[i - S.size()] - 'a']--;
    si[T[i] - 'a']++;
    if(vi == si) {
      int l = i - (int) S.size() + 1;
      int r = i + 1;
      mp[{latte.get(l, r), malta.get(l, r)}]++;
    }
  }
  int large = 0;
  for(auto &x : mp) large = max(large, x.second);

  if(large == 0) {
    cout << -1 << endl;
    return;
  }
  SuffixArray sa;
  sa.Build_SA(T);
  si.assign(26, 0);
  int ret = INF;
  vector< int > rev(T.size());
  for(int i = 0; i < T.size(); i++) rev[sa[i]] = i;

  for(int i = 0; i < T.size(); i++) {
    if(i >= S.size()) si[T[i - S.size()] - 'a']--;
    si[T[i] - 'a']++;
    if(vi == si) {
      int l = i - (int) S.size() + 1;
      int r = i + 1;
      if(mp[{latte.get(l, r), malta.get(l, r)}] == large) {
        ret = min(ret, rev[l]);
      }
    }
  }
  cout << T.substr(sa[ret], S.size()) << endl;
}

int main()
{
  int T;
  cin >> T;
  while(T--) beet();
}

Unique Art

www.hackerrank.com

問題概要

長さ の数列 が与えられる.

次の 個のクエリに答えよ.

• 区間 の数列を取り出す. このうち重複して出現しない値の種類数を求める.

解法

まず数列については座圧して, クエリについては区間の右端でソートし, 右端で処理する.

つぎに長さ のBITを持ちながら左から走査する.

まず BIT の 番目の要素を にする. つぎに直前に現れた の位置を にする. その前に現れた の位置を にする. こうすることで, クエリに答える時にその区間の和を求めればそれがユニークな値の個数と一致する(1つ現れる値は+1, 2つ以上現れる値は相殺されて±0となる).

ソース

#include <bits/stdc++.h>

using namespace std;

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

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

  T sum(int k)
  {
    T ret = 0;
    for(++k; k < data.size(); k += k & -k) ret += data[k];
    return (ret);
  }

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

int main()
{
  int N, T[1000000];
  int Q;

  scanf("%d", &N);
  vector< int > vs(N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &T[i]);
    vs[i] = T[i];
  }
  sort(begin(vs), end(vs));
  vs.erase(unique(begin(vs), end(vs)), end(vs));
  for(int i = 0; i < N; i++) {
    T[i] = lower_bound(begin(vs), end(vs), T[i]) - begin(vs);
  }
  scanf("%d", &Q);
  vector< pair< int, int > > querys[1000000];
  for(int i = 0; i < Q; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x, --y;
    querys[y].emplace_back(i, x);
  }
  vector< int > last(vs.size(), -1), pv(N);
  for(int i = 0; i < N; i++) {
    pv[i] = last[T[i]];
    last[T[i]] = i;
  }

  BinaryIndexedTreeReversed< int > bit(N);
  vector< int > ans(Q);
  for(int i = 0; i < N; i++) {
    bit.add(i, 1);
    if(~pv[i]) {
      bit.add(pv[i], -2);
      if(~pv[pv[i]]) bit.add(pv[pv[i]], 1);
    }
    for(auto &p : querys[i]) {
      ans[p.first] = bit.sum(p.second);
    }
  }
  for(int i = 0; i < Q; i++) {
    printf("%d\n", ans[i]);
  }
}

Magic Value

www.hackerrank.com

問題概要

ある長さ の数列 について を と定義する. をそれぞれ任意のペア のうち の最大値と最小値と定義する. そして数列 の Magic Value を と定義する.

長さ の数列 が与えられる. 数列の考えられるすべての連続する部分列の Magic Value の和を で割った余りで求めよ.

解法

わからなかった, かなしいね.

部分点解法

は独立に計算しても良い.

は数列のうち一要素だけ取り出すのが最適. gcd なので複数取り出すと損. ふつうにやると で求めることができる.

は が含まれれば がよくて, それ以外は数列全体を選ぶべき. これもふつうにやると .

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

int main()
{
  int N;
  int64 A[200001];

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

  int64 latte = 0;

  for(int i = 1; i <= N; i++) {
    int64 smin = 0;
    bool iszero = false;
    for(int j = i; j >= 1; j--) {
      if(A[j] == 0) break;
      smin = __gcd(smin, A[j]);
      latte += (i - j + 1) * smin % mod;
      latte %= mod;
    }
  }

  int64 malta = 0;
  for(int i = 1; i <= N; i++) {
    int64 smax = 0;
    for(int j = i; j <= N; j++) {
      smax = max(smax, (j - i + 1) * A[j]);
      malta += smax * (j - i + 1) % mod;
      malta %= mod;
    }
  }
  cout << (malta + mod - latte) % mod << endl;
}

Drawing Rectangles

www.hackerrank.com

問題概要

から の二次元グリッドがある.

個のある長方形領域の色を塗るクエリが与えられる. ここで長方形の和集合で, 色が塗られているセルの個数は 以下であることが保証される.

任意の行か列を選択してその線上のセルの色を消す操作を繰り返し行える.

操作の最小回数を求め, その操作の具体例を出力せよ.

解法

実際に塗られているセルは 個しかないため, これをまず求めたい.

平面走査を考えると, 区間加減算と区間全体で 以上の要素位置を求めるみたいな操作を何回か行うことになる.

区間全体で 以上の要素は愚直に見ているとかなり険しいので, の要素をスキップしたい. これは区間 max を取得できるようにしておくとセグ木上をDFSで走査するみたいなことができて, 効率よく求めることが出来る.

あとは蟻本にも載っているように行と列を頂点とした二部グラフの最大マッチングをして最小点カバーを求めれば良い. 二部グラフの最大マッチングは のものだとおそらく険しいが Hopcroft-Karp を使うと になる. 最小点カバーの具体例の求め方は

qiita.com

が詳しい.

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

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

  Bipartite_Matching(int n, int m)
  {
    graph.resize(n);
    match.assign(m, -1);
    used.assign(n, false);
  }

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

  void bfs()
  {
    dist.assign(graph.size(), -1);
    queue< int > que;
    for(int i = 0; i < graph.size(); i++) {
      if(!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }

    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : graph[a]) {
        int c = match[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool dfs(int a)
  {
    vv[a] = true;
    for(auto &b : graph[a]) {
      int c = match[b];
      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching()
  {
    int ret = 0;
    while(true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for(int i = 0; i < graph.size(); i++) {
        if(!used[i] && dfs(i)) ++flow;
      }
      if(flow == 0) return (ret);
      ret += flow;
    }
  }
};

struct StarrySkyTree
{
  int sz;
  vector< int > seg, add;

  StarrySkyTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, 0);
    add.assign(2 * sz - 1, 0);
  }

  void range_add(int a, int b, int x, int k, int l, int r)
  {
    if(a >= r || b <= l) {
      return;
    } else if(a <= l && r <= b) {
      add[k] += x;
    } else {
      range_add(a, b, x, 2 * k + 1, l, (l + r) >> 1);
      range_add(a, b, x, 2 * k + 2, (l + r) >> 1, r);
      seg[k] = max(seg[2 * k + 1] + add[2 * k + 1], seg[2 * k + 2] + add[2 * k + 2]);
    }
  }

  void range_add(int a, int b, int x)
  {
    range_add(a, b, x, 0, 0, sz);
  }

  void get_points(int y, vector< pair< int, int > > &pts, int par, int k, int l, int r)
  {
    par += add[k];
    if(par + seg[k] <= 0) {
      return;
    } else if(l + 1 >= r) {
      pts.emplace_back(l, y);
    } else {
      get_points(y, pts, par, 2 * k + 1, l, (l + r) >> 1);
      get_points(y, pts, par, 2 * k + 2, (l + r) >> 1, r);
    }
  }

  void get_points(int y, vector< pair< int, int > > &pts)
  {
    get_points(y, pts, 0, 0, 0, sz);
  }
};

int main()
{
  int N;
  scanf("%d", &N);
  vector< pair< int, int > > add[300001], del[300001];
  for(int i = 0; i < N; i++) {
    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    add[y1].emplace_back(x1, x2 + 1);
    del[y2].emplace_back(x1, x2 + 1);
  }
  StarrySkyTree seg(300001);
  vector< pair< int, int > > points;
  for(int i = 0; i < 300001; i++) {
    for(auto &p : add[i]) seg.range_add(p.first, p.second, +1);
    seg.get_points(i, points);
    for(auto &p : del[i]) seg.range_add(p.first, p.second, -1);
  }
  Bipartite_Matching flow(3000001, 300001);
  for(auto &p : points) flow.add_edge(p.first, p.second);
  set< pair< int, int > > st(begin(points), end(points));
  cout << flow.bipartite_matching() << endl;

  vector< int > g[600002];
  bool red[600002] = {};
  for(int i = 0; i < 300001; i++) red[i] = true;
  for(int i = 0; i < 300001; i++) {
    if(~flow.match[i]) {
      g[i + 300001].emplace_back(flow.match[i]);
      st.erase({flow.match[i], i});
      red[flow.match[i]] = false;
    }
  }
  for(auto &rest : st) {
    g[rest.first].emplace_back(rest.second + 300001);
  }
  queue< int > que;
  for(int i = 0; i < 300001; i++) {
    if(red[i]) que.emplace(i);
  }
  while(que.size()) {
    int idx = que.front();
    que.pop();
    for(auto &x : g[idx]) {
      if(red[x]++) continue;
      que.emplace(x);
    }
  }
  vector< int > x, y;
  for(int i = 0; i < 300001; i++) {
    if(!red[i]) x.emplace_back(i);
    if(red[i + 300001]) y.emplace_back(i);
  }

  printf("%d\n", (int) x.size());
  for(int a : x) printf("%d ", a);
  puts("");
  printf("%d\n", (int) y.size());
  for(int a : y) printf("%d ", a);
  puts("");
}