HackerRank World CodeSprint 7

勉強になった

Sock Merchant

問題概要

${n(1 \le n \le 100)}$ 枚の靴下があって, それぞれの色は ${c_i(1 \le c_i \le 100)}$ である. お客さんは ${2}$ 枚の同じ色の靴下を ${1}$ ペアとして購入する.

最大で何ペア作れるか.

解法

色別に何枚の靴下があるかを数える.

色 ${i}$ の靴下が ${a_i}$ 枚あったとする. すると明らかに, $\sum_{ i = 1 }^{ 100 } \lfloor \frac{a_i} {2} \rfloor$ が答え.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int N;
  bool f[101] = {};
  cin >> N;
  int ret = 0;
  for(int i = 0; i < N; i++) {
    int C;
    cin >> C;
    ret += f[C];
    f[C] ^= 1;
  }
  cout << ret << endl;
}

Two Characters

問題概要

${t}$ を ${2}$ 種類の文字が交互に現れる文字列と定義する.

文字列 ${s(1 \le |s| \le 1000)}$ が与えられる. ある ${1}$ 文字を選んで ${s}$ の中に含まれるすべてのその文字を削除する操作を何回か行って ${t}$ にしたい.

このとき, でき得る ${t}$ の最大の長さを求めよ.

解法

${t}$ にするためには, ${2}$ 種類以外の文字を消すしかない.

ここで, 残す ${2}$ 種類の文字は ${26 \times 25}$ 通りしかなくて全通り試すことが出来る. 残さなかった文字を無視しながら見たとき, それが交互文字列になっているか見れば良い.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int N;
  string S;

  cin >> N;
  cin >> S;

  int all = 0;
  for(char c = 'a'; c <= 'z'; c++) {
    for(char d = 'a'; d <= 'z'; d++) {
      if(c == d) continue;
      int ret = 0;
      char now = c, other = d;
      bool flag = true;
      for(char& chara : S) {
        if(chara != c && chara != d) continue;
        if(chara == now) {
          ++ret;
          swap(now, other);
        } else {
          flag = false;
        }
      }
      if(flag && ret >= 2) all = max(all, ret);
    }
  }
  cout << all << endl;
}

Gridland Metro

問題概要

${n \times m(1 \le n, m \le 10^9)}$ の行列がある.

${(y, x)}$ を ${y}$ 行目 ${x}$ 列目とする. ${k(1 \le k \le 1000)}$ 個バスが通っていて, それぞれ ${(r, c_1)}$ を始点とし ${r, c_2}$ を終点とする経路である. 常に経路は行と平行である. 複数のバスの経路が重なることもある.

どのバスの経路にもあたらないセルに街灯を置きたい. そのようなセルは何個あるか.

解法

${n, m}$ が非常に大きいので, ${n \times m}$ のセルから街灯を置けないマスをひいていくことを考える.

経路が重なることがなければ, ${n \times m}$ から ${c_2 - c_1 + 1}$ をひいていけばそれが答え.

しかし重なるらしいので, 重なった部分を計算したい. バスの経路は行で独立なので, 行別に考える(ここで考えるべき行は座標圧縮すれば ${O(k)}$ 行).

${(c_1, c_2)}$ のペアを ${c_1}$ の昇順でソートしておく. すると尺取りっぽく計算できるのでする(これは僕の日本語力だと説明ができないのでソースコードを参照.

計算量は ${\mathcal{O}(k \log k)}$ .

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int H, W, K;
  int r[1000], c1[1000], c2[1000];

  vector< int > nums;

  cin >> H >> W >> K;
  for(int i = 0; i < K; i++) {
    cin >> r[i] >> c1[i] >> c2[i];
    nums.push_back(r[i]);
  }
  sort(begin(nums), end(nums));
  nums.erase(unique(begin(nums), end(nums)), end(nums));
  vector< vector< pair< int, int > > > merged(nums.size());
  for(int i = 0; i < K; i++) {
    int idx = lower_bound(begin(nums), end(nums), r[i]) - begin(nums);
    merged[idx].emplace_back(c1[i], c2[i] + 1);
  }

  int64 ret = 0;
  for(auto& obj : merged) {
    sort(begin(obj), end(obj));
    int last = obj[0].second;
    int all = W - obj[0].first;
    for(int i = 1; i < obj.size(); i++) {
      if(last < obj[i].first) all -= obj[i].first - last;
      last = max(last, obj[i].second);
    }
    all -= W - last;
    ret += all;
  }
  cout << 1LL * W * H - ret << endl;
}

Summing Pieces

問題概要

長さ ${n(1 \le n \le 10^6)}$ の配列 ${A}$ がある. 配列 ${A}$ を, 連続した要素が ${1}$ 個の部品となるように分割しこれを配列 ${B}$ とする.

ピースの価値を (ピースに含まれる要素の和) ${\times}$ (ピースの長さ) と定義する. 配列 ${B}$ の価値は ${B}$ に含まれるピースの価値をすべて足したものである.

配列 ${A}$ からでき得るすべての分割の仕方を考えたとき, 配列 ${B}$ の価値を合計して ${10^9 + 7}$ で割った余りを求めよ.

解法

すべての ${B}$ の組み合わせを列挙するのは大変なので, 配列 ${A}$ のそれぞれの要素位置で独立して考える.

まず ${A_1}$ の要素が最終的な解の価値にどれだけ影響するかを考えると, これは ${A_1 \times (2^{n}-1)}$ らしい(実験するとそうだった.

${A_{i}}$ の要素から ${A_{i+1}}$ の要素に視点を移動させる. ピースに加わる分と減る分を考えると, ${\mathcal{O}(1)}$ で計算できるのでする.

小さいケースで実験して察したので, これは説明できません....

ソース

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int inv = 5e8 + 4;

int pow_mod(int x, int n)
{
  int ret = 1;
  while(n > 0) {
    if(n & 1) ret = 1LL * ret * x % mod;
    x = 1LL * x * x % mod;
    n >>= 1;
  }
  return ret;
}

int main()
{
  int N, A[1000000];
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  int now = pow_mod(2, N) - 1;
  int sub = 1;
  int add = pow_mod(2, N - 2);
  int ret = 0;
  for(int i = 0; i < (N + 1) / 2; i++) {
    ret = (ret + 1LL * now * A[i]) % mod;
    if(N % 2 == 1 && N / 2 == i) break;
    ret = (ret + 1LL * now * A[N - i - 1]) % mod;
    now = now + add - sub;
    while(now < 0) now += mod;
    now %= mod;
    add = 1LL * add * inv % mod;
    sub = sub * 2 % mod;
  }
  cout << ret << endl;
}

Inverse RMQ

問題概要

セグメント木による ${0-indexed}$ の RMQ を考える.

一般的に長さ ${n(1 \le n \le 2^{18}, n}$ は ${2}$ の累乗数 ${)}$ の区間のセグメント木を配列表現しようとすると, ${2n - 1}$ 個の要素が必要である. また, ${i}$ 番目の要素の右の子は ${2i+1}$ 番目, 左の子は ${2i+2}$ 番目の要素位置となる. ${i}$ 番目の要素に格納される値は, ${2i+1}$ 番目と ${2i+2}$ 番目の要素のうちの最小値である.

相異なる値からなる配列を配列によるセグメント木で表したが, 悪い人がこの配列をシャッフルしてしまった.

このときもとの配列を復元できるか判定し, できるのなら辞書順(自然順??) 最小の配列を出力せよ.

解法

まず, 各々の数の出現回数を数える. このとき, ${1}$ 番多く出現した数が根に格納されるはずである. ${1}$ 番目から ${2}$ 番目に多く出現した数が, 深さ ${2}$ のいずれかの要素位置に格納されるはずである. 同様に深さ ${k}$ になるまで繰り返すと, 任意の深さに入る数が一意に定まる(定まらなければ復元できない).

あとは辞書順最小の配列を求めたい気持ちになるが, これは木を行きがけ順に走査して貪欲に確定できる. 親ノードがあってその値が ${T_k}$ であるとすると, 明らかに左の子のノードの値も ${T_k}$ である. 右の子ノードは, その深さで初めて現れる数字で, ${T_k}$ より大きい最小の値を使えばよい(使えなけば復元できない). 行きがけ順に走査しているのでこれが成立する.

${\mathcal{O}(n \log n)}$ .

ソース

#include<bits/stdc++.h>

using namespace std;

set< int > nums[24];
int depth;
int tree[1 << 24];

bool build(int dep, int k)
{
  if(dep == depth) return (true);
  if(nums[dep + 1].empty()) return (false);
  auto get = nums[dep + 1].lower_bound(tree[k]);
  if(get == nums[dep + 1].end()) return (false);
  nums[dep + 1].erase(get);
  tree[k * 2 + 1] = tree[k];
  tree[k * 2 + 2] = *get;
  return (build(dep + 1, 2 * k + 1) & build(dep + 1, 2 * k + 2));
}

int main()
{
  int N;
  map< int, int > sz;

  cin >> N;
  for(int i = 0; i < 2 * N - 1; i++) {
    int K;
    cin >> K;
    ++sz[K];
  }

  int size = 1;
  depth = 1;
  while(size < N) size <<= 1, depth++;

  for(int i = depth; i > 0; i--) {
    for(auto& k : sz) {
      if(k.second == 0) continue;
      k.second--;
      if(k.second == 0) {
        stringstream sss;
        sss << k.first;
        nums[i].insert(k.first);
      }
    }
  }

  if(nums[1].size() != 1) {
    cout << "NO" << endl;
    return (0);
  }

  tree[0] = *nums[1].begin();
  if(build(1, 0)) {
    cout << "YES" << endl;
    for(int i = 0; i < 2 * N - 1; i++) {
      if(i > 0) cout << " ";
      cout << tree[i];
    }
    cout << endl;
  } else {
    cout << "NO" << endl;
  }
}

Recording Episodes

問題概要

${q(1 \le q \le 100)}$ 個のデータセットからなる.

${n(1 \le n \le 100)}$ 個のエピソードが放送される. すべての番組は ${2}$ 回放送され, ${i}$ 番目のエピソードは時刻 ${(s_l, t_l)}$ の間と時間 ${(s_r, t_r)}$ の間である.

連続したエピソードを録画したい. ${i}$ 番目のエピソードを見るには ${2}$ 回のうちどちらかの放送を録画しなくてはならず, 時間が被っている別のエピソードを同時に録画することはできない.

最大で何個連続して録画できるか求め, そのときの区間 ${[L, R]}$ を出力せよ. 複数ある場合は ${L}$ が最小となるものを出力せよ.

解法

これ知らなかったんだけど, 調べてみると 2-SAT の典型らしい.

区間 ${[i, j]}$ が録画可能で, ${[i, j + 1]}$ は録画不可能だったとする. このとき区間 ${[i + 1, j]}$ は明らかに録画可能, ${[i + 1, j + 1]}$ はわからない. よって, 試すべき ${j}$ は ${i}$ が増加するに従って ${j}$ は増加するので ${\mathcal{O}(n)}$ の尺取りが出来る.

区間 ${[i, j]}$ が録画可能かどうか判定したい.

${k(i \le k \le j)}$ 番目の放送は必ず ${2}$ 回の放送のどちらかで録画しなければならない.

たとえば, ${k}$ 番目の放送を最初の放送で録画したとする. この状態を ${b_{k,0} = 1}$ とする. ${b_{k, 0} = 1}$ のとき, ${k}$ 番目の最初の放送と被っている他の放送は録画できない. 録画できない放送 ${p}$ について ${b_{p,?} = 0}$ を満たす必要がある. 同様に ${k}$ 番目の放送を ${2}$ 回目の放送で録画したとする. この状態を ${b_{k,1} = 1}$ として, そのとき被っている放送 ${q}$ について ${b_{q,?} = 0}$ を満たす必要がある.

この関係性をグラフにすれば 2-SAT なので強連結成分分解して解くと ${\mathcal{O}(n^2)}$ .

全体で ${\mathcal{O}(qn^3)}$ となって怪しいが, 重い ${\mathcal{O}(n^3)}$ ではない(?)ので間に合う.

ソース

#include<bits/stdc++.h>

using namespace std;

int Q, N;
int S1[100], E1[100], S2[100], E2[100];
bool graph[200][200];

int order[200], ptr;
bool used[200];
int cmp[200];

void dfs(int idx, const int L, const int R)
{
  if(used[idx]++) return;
  for(int i = L; i < R; i++) if(graph[idx][i]) dfs(i, L, R);
  order[ptr++] = idx;
}

void rdfs(int idx, const int cnt, const int L, const int R)
{
  if(~cmp[idx]) return;
  cmp[idx] = cnt;
  for(int i = L; i < R; i++) if(graph[i][idx]) rdfs(i, cnt, L, R);
}

bool checkSCC(int L, int R)
{
  for(int i = L; i < R; i++) {
    used[i] = false;
    cmp[i] = -1;
  }
  ptr = 0;
  for(int i = L; i < R; i++) {
    dfs(i, L, R);
  }
  for(int i = ptr - 1; i >= 0; i--) {
    rdfs(order[i], i, L, R);
  }
  for(int i = L; i < R; i += 2) {
    if(cmp[i] == cmp[i + 1]) return (false);
  }
  return (true);
}

bool cross(int a, int b, int c, int d)
{
  return (c <= b && a <= d);
}

int main()
{
  scanf("%d", &Q);
  while(Q--) {
    memset(graph, false, sizeof(graph));

    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
      scanf("%d %d %d %d", &S1[i], &E1[i], &S2[i], &E2[i]);
    }
    for(int i = 0; i < N; i++) {
      for(int j = i + 1; j < N; j++) {
        if(cross(S1[i], E1[i], S1[j], E1[j])) {  // 0 - 0
          graph[i << 1][(j << 1) | 1] = true;
          graph[j << 1][(i << 1) | 1] = true;
        }
        if(cross(S1[i], E1[i], S2[j], E2[j])) { // 0 - 1
          graph[i << 1][j << 1] = true;
          graph[(j << 1) | 1][(i << 1) | 1] = true;
        }
        if(cross(S2[i], E2[i], S1[j], E1[j])) { // 1 - 0
          graph[(i << 1) | 1][(j << 1) | 1] = true;
          graph[j << 1][i << 1] = true;
        }
        if(cross(S2[i], E2[i], S2[j], E2[j])) { // 1 - 1
          graph[(i << 1) | 1][j << 1] = true;
          graph[(j << 1) | 1][i << 1] = true;
        }
      }
    }

    int R = 1;
    pair< int, int > ret(-1, -1);
    for(int L = 0; L < N; L++) {
      while(R < N && checkSCC(2 * L, 2 * R + 2)) ++R;
      ret = max(ret, {R - L, -L});
    }

    printf("%d %d\n", -ret.second + 1, ret.first - ret.second);
  }
}

Similar Strings

問題概要

文字列 ${A}$ と ${B}$ が似ているというのは以下の条件を満たす文字列である.

${|A| = |B|}$
すべてのペア ${i, j}$ について, ${A_i = A_j\ and\ B_i = B_j}$ あるいは ${A_i \ne A_j\ and\ B_i \ne B_j}$ を満たす

長さ ${n(1 \le n \le 5 \times 10^4)}$ の文字列 ${S(S_i \in \{a, b, c, d, e, f, g, h, i, j\})}$ と ${q(1 \le q \le 5 \times 10^4)}$ 個のクエリが与えられる. それぞれのクエリについて, ${S[l_i, r_i]}$ と似ている ${S}$ の部分文字列は何個あるか出力せよ.

解法

まず, ${S}$ と ${T}$ が似ているということは ${S}$ と ${T}$ の文字の割り当てを入れ替えた時に ${S = T}$ にできるということと同義である.

ここで ${S}$ のすべての部分文字列 ${S[L, R)}$ を ${1}$ 番目に現れる文字を ${a}$ , ${2}$ 番目に現れる文字を ${b}$ というように置換すれば, 置換した文字列上で ${S = T}$ を判定することと同じである.

以下文字の種類数を ${c}$ とする. この問題では ${10}$ 種類の文字があるのだが, 種類別に Rolling Hash で事前に前計算しておけばハッシュ値を ${\mathcal{O}(c)}$ で求めることが出来る. 種類別の ${S[L, R)}$ ] のハッシュ値を ${\mathcal{O}(1)}$ で求めて, ${S[L, R)}$ を置換した順番でソートして計算すれば良い.

${2}$ つの部分文字列の大小関係の比較はどこまでハッシュ値が一致するかで二分探索して, その位置の文字同士を比較すればよいので ${\mathcal{O}(c \log n)}$ で計算できる.

文字列 ${S}$ の中に部分文字列 ${S[L, R)}$ が何回現れるかという問題を考える. これは一般的に Suffix Array を構築して二分探索すれば求めることが出来る.

Suffix Array の構築は, 比較に ${\mathcal{O}(\log n)}$ かけて ${\mathcal{O}(cn \log^2 n)}$ で出来る.

二分探索は Suffix Array 上で部分文字列が一致する上限と下限を求めるのだが, これも ${1}$ 回あたり ${\mathcal{O}(c \log^2 n)}$ で求めることができる.

全体の計算量は ${\mathcal{O}(c (n + q)\log^2 n)}$ となって怪しい計算量になるのだが, ぎりぎり間に合う(本当にぎりぎりでハッシュ値 ${1}$ つで mod とならない Rolling Hash にしてやっと 1.98sec...)

ソース

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long hash_type;

struct RollingHash
{
  hash_type base1;
  vector< hash_type > hash1, pow1;

  RollingHash() : base1(11LL)
  {
  }

  void init(const bool *s, int n)
  {
    hash1.assign(n + 1, 0);
    pow1.assign(n + 1, 1);
    for(int i = 0; i < n; i++) {
      hash1[i + 1] = (hash1[i] + s[i]) * base1;
      pow1[i + 1] = pow1[i] * base1;
    }
  }

  hash_type get(int l, int r)
  {
    if(r >= hash1.size()) return (~0);
    return ((hash1[r] - hash1[l] * pow1[r - l]));
  }

};

int N, Q;
char S[50001];

int A[50001][10];
int B[50001][10];

int idx[50001];
int inv[50001];

RollingHash hashed[10];
bool buff[10][50001];

hash_type dump(int left, int right)
{
  hash_type val = 0;
  for(int i = 0; i < 10; i++) {
    val = (val + hashed[A[left][i]].get(left, right)) * 100003;
  }
  return (val);
}

bool compare(const int& a, const int& b)
{
  int low = 0, high = min(N - a, N - b) + 1;
  while(high - low > 1) {
    int mid = (low + high) >> 1;
    if(dump(a, a + mid) == dump(b, b + mid)) low = mid;
    else high = mid;
  }
  if(low == min(N - a, N - b)) return (low == N - a);
  return (B[a][S[a + low]] < B[b][S[b + low]]);
}

void build()
{
  for(int i = 0; i < N; i++) S[i] -= 'a';

  for(int i = 0; i < N; i++) buff[S[i]][i] = true;
  for(int i = 0; i < 10; i++) hashed[i].init(buff[i], N);

  for(int i = 0; i < 10; i++) A[N][i] = i;
  for(int i = N - 1; i >= 0; i--) {
    int last;
    for(int j = 0; j < 10; j++) {
      A[i][j] = A[i + 1][j];
      if(A[i][j] == S[i]) last = j;
    }
    while(last--) swap(A[i][last], A[i][last + 1]);
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < 10; j++) {
      B[i][A[i][j]] = j;
    }
  }

  iota(idx, idx + N, 0);
  sort(idx, idx + N, compare);

  for(int i = 0; i < N; i++) {
    inv[idx[i]] = i;
  }
}

int main()
{
  scanf("%d %d", &N, &Q);
  scanf(" %s", S);
  build();

  while(Q--) {
    int L, R;
    scanf("%d %d", &L, &R);
    --L;
    int low1 = -1, high1 = inv[L];
    while(high1 - low1 > 1) {
      int mid = (low1 + high1) >> 1;
      if(dump(L, R) == dump(idx[mid], idx[mid] + R - L)) high1 = mid;
      else low1 = mid;
    }
    int low2 = inv[L], high2 = N;
    while(high2 - low2 > 1) {
      int mid = (low2 + high2) >> 1;
      if(dump(L, R) == dump(idx[mid], idx[mid] + R - L)) low2 = mid;
      else high2 = mid;
    }
    printf("%d\n", low2 - high1 + 1);
  }
}

ei1333の日記

ぺこい

HackerRank World CodeSprint 7

Sock Merchant

問題概要

解法

ソース

Two Characters

問題概要

解法

ソース

Gridland Metro

問題概要

解法

ソース

Summing Pieces

問題概要

解法

ソース

Inverse RMQ

問題概要

解法

ソース

Recording Episodes

問題概要

解法

ソース

Similar Strings

問題概要

解法

ソース