Educational Codeforces Round 37

ooo-ooo 20th.

うしし

A. Water The Garden

codeforces.com

問題概要

えーえー面倒

解法

そのまま実装すれば良いため.

ソース

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int T, N, K, X[200];

  cin >> T;
  while(T--) {
    cin >> N >> K;
    for(int i = 0; i < K; i++) {
      cin >> X[i];
      --X[i];
    }
    for(int t = 1;; t++) {
      vector< int > used(N);
      for(int i = 0; i < K; i++) {
        for(int j = max(0, X[i] - t + 1); j <= min(N - 1, X[i] + t - 1); j++) {
          used[j] = 1;
        }
      }
      if(count(begin(used), end(used), 1) == N) {
        cout << t << endl;
        break;
      }
    }
  }
}

B. Tea Queue

codeforces.com

問題概要

えー

解法

えーこれむずかしい.

ソース

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int T, N;

  cin >> T;
  while(T--) {
    cin >> N;
    queue< pair< int, int > > que;
    vector< int > ans(N);
    int now = 0;

    auto sweep = [&](int x)
    {
      while(que.size() && now < x) {
        int idx, tt;
        tie(idx, tt) = que.front();
        que.pop();
        if(now > tt) continue;
        ans[idx] = now;
        ++now;
      }
      now = x;
    };

    for(int i = 0; i < N; i++) {
      int l, r;
      cin >> l >> r;
      sweep(l);
      que.emplace(i, r);
    }
    sweep(13333);

    for(int i = 0; i < N; i++) {
      cout << ans[i] << " ";
    }
    cout << endl;
  }
}

C. Swap Adjacent Elements

codeforces.com

問題概要

長さ ${n(2 \le n \le 2 \times 10^5)}$ の順列が与えられる.

隣接要素を繰り返し交換して昇順列にできるか判定せよ.

ただし隣接要素を交換できない位置が何個かある.

解法

えーstd::is_sorted() を使いたかっただけですが...

交換可能なところはUnion-Findを使ってまとめる.

手前の連結成分から, 成分内に含まれる値のうち min と max を取り出してそれらを並べる.

ソートされていればソートできる. ほとんど ${O(N)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

struct UnionFindRange
{
  vector< int > data;
  vector< int > left, right;

  UnionFindRange(vector< int > &vs)
  {
    data.assign(vs.size(), -1);
    left = vs;
    right = vs;
  }

  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);
    left[x] = min(left[x], left[y]);
    right[x] = max(right[x], right[y]);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  pair< int, int > range(int k)
  {
    k = find(k);
    return {left[k], right[k]};
  };

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

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

int main()
{
  int N;
  string S;

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

  UnionFindRange uf(A);
  for(int i = 1; i < N; i++) {
    if(S[i - 1] == '1') uf.unite(i - 1, i);
  }

  vector< int > vs;
  for(int i = 0; i < N; i++) {
    if(uf.find(i) == i) {
      auto p = uf.range(i);
      vs.emplace_back(p.first);
      vs.emplace_back(p.second);
    }
  }

  if(is_sorted(begin(vs), end(vs))) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

D. Tanks

codeforces.com

問題概要

${N(2 \le N \le 5000)}$ 個のボトルがあって ${i}$ 番目のボトルには水が ${a_i(0 \le a_i \le 10^9)}$ ml 入っている.

${K(1 \le K \le 5000)}$ ml のコップを使って水をうつすことができる. ${1}$ 回の操作でいずれかのボトルを選ぶ. このボトルに ${v}$ ml 入っているとすると水を ${\min(v, K)}$ ml 入れることができる. 途中で水を入れるのをやめることはできない. 次にいずれかのボトルを選択してそのボトルにコップの水をすべて移動する.

${V(0 \le V \le 10^9)}$ ml の水が入ったボトルを得ることが可能なら, その操作手順を出力せよ.

解法

なんか正当性の証明が難しそうなのでエスパーして解く.

まず ${V}$ が ${K}$ で割り切れる時, 全部の水を ${1}$ 箇所に集めていい感じにえいするのが最適.

それ以外のときは難しそう.

えー, すべてのボトルを ${2}$ つの集合 ${X, Y}$ に分割し, それぞれの和を ${x, y}$ とする. ${x = V \bmod K}$ が成立するとき, ${\lfloor \frac {y} {K} \rfloor} \times$ と ${x}$ との和が ${V}$ 以上のとき ${V}$ のボトルを構成できることがわかる(そのような操作ができるので). 具体的には ${x}$ のあるボトルに, 他の ${X}$ の全ての水を集め, 同様に ${y}$ のあるボトルに, 他の ${Y}$ の全ての水を集める. 次に ${Y}$ のボトルから ${\lfloor \frac {y} {K} \rfloor} \times K$ の分だけ ${X}$ のボトルに移動すると, ボトルの水の和 ${x}$ は ${V}$ 以上かつ ${(x-V) \bmod K = 0}$ となる. 最後に ${x-V}$ の分だけ他のボトルに移動すれば ${V}$ のボトルを構成できる.

このとき ${x = V \bmod K}$ を満たすどのような集合 ${X, Y}$ をとってきても, 余す水の量は一意で最小(伝わって) にできることに注目すると, 結局ボトルの部分集合をとってきて, その和を ${K}$ で割った余りが ${V}$ と一致するようなものがあるか探す問題に帰着できる.

で, これは DP すればできるため ${O(NK)}$ .

ソース

や、難しすぎるだろ.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int N, K, V, A[5000];
bool v[5001];
vector< int > used;
bool visited[5000][5001];

int rec(int idx, int mod)
{
  if(mod == V % K) return (true);
  if(idx == N) return (false);
  if(visited[idx][mod]++) return (false);
  if(rec(idx + 1, mod)) return (true);
  if(rec(idx + 1, (mod + A[idx]) % K)) {
    used.push_back(idx);
    v[idx] = true;
    return (true);
  }
  return (false);
}

int main()
{
  cin >> N >> K >> V;
  bool found = false;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }

  if(rec(0, 0)) {
    vector< int > unused;
    for(int i = 0; i < N; i++) {
      if(!v[i]) unused.emplace_back(i);
    }

    vector< tuple< int, int, int > > order;
    int latte = 0, malta = 0;
    for(int i : used) latte += A[i];
    for(int i : unused) malta += A[i];

    for(int i = 1; i < used.size(); i++) {
      order.emplace_back(used[i], used[0], 1000000000);
    }
    for(int i = 1; i < unused.size(); i++) {
      order.emplace_back(unused[i], unused[0], 1000000000);
    }
    malta = malta / K * K;
    if(malta > 0) {
      order.emplace_back(unused[0], used.size() ? used[0] : 0, malta / K);
      latte += malta;
    }
    if(latte < V) {
      cout << "NO" << endl;
      return (0);
    }
    if(V % K == 0) order.emplace_back(0, 1, V / K);
    else order.emplace_back(used[0], used[0] == 0, (latte - V) / K);
    cout << "YES" << endl;
    for(auto &p : order) {
      int x, y, z;
      tie(x, y, z) = p;
      if(z) cout << z << " " << x + 1 << " " << y + 1 << endl;
    }
  } else {
    cout << "NO" << endl;
  }
}

E. Connected Components?

codeforces.com

問題概要

${n(1 \le n \le 2 \times 10^5)}$ 頂点 ${\frac {n(n-1)} {2} - m}$ 辺のグラフがある.

${m(1 \le m \le \min(\frac {n(n-1)} {2}, 2 \times 10^5))}$ 個の頂点 ${x, y(1 \le x, y \le n, x \ne y)}$ を結ぶ辺以外の任意の辺はグラフ上で存在する.

それぞれの連結成分の大きさを昇順で出力せよ.

解法

連結成分の求め方は何があったかなーと思うと, UnionFindが浮かぶが無理そうなので他の方法を考えるとBFSじゃんとなる.

でBFSをかんがえる. ある頂点から到達できる頂点はいくつかの区間になっているので, 未到達頂点を set で持っておくといい感じに訪問できる.

ソース

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N, M;
  vector< int > ev[200000];

  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x, --y;
    ev[x].emplace_back(y);
    ev[y].emplace_back(x);
  }

  set< int > rest;
  for(int i = 0; i < N; i++) {
    ev[i].emplace_back(-1);
    ev[i].emplace_back(N);
    sort(begin(ev[i]), end(ev[i]));
    rest.emplace(i);
  }
  rest.emplace(13333333);
  vector< int > sz;
  for(int i = 0; i < N; i++) {
    if(rest.count(i) == 0) continue;
    queue< int > que;
    que.emplace(i);
    rest.erase(i);
    sz.emplace_back(0);
    while(!que.empty()) {
      int idx = que.front();
      que.pop();
      sz.back()++;
      for(int j = 1; j < ev[idx].size(); j++) {
        const int L = ev[idx][j - 1] + 1;
        const int R = ev[idx][j] - 1;
        auto ptr = rest.lower_bound(L);
        while(*ptr <= R) {
          que.emplace(*ptr);
          ptr = rest.erase(ptr);
        }
      }
    }
  }

  sort(begin(sz), end(sz));
  printf("%d\n", (int) sz.size());
  for(int i = 0; i < sz.size(); i++) {
    printf("%d ", sz[i]);
  }
  puts("");
}

F. SUM and REPLACE

codeforces.com

問題概要

${D(x)}$ を ${x}$ の約数の個数と定義する.

長さ ${n(1 \le n \le 3 \times 10^5)}$ の数列 ${a_i(1 \le a_i \le 10^6)}$ が与えられる. 次の ${m(1 \le m \le 10^6)}$ 個のクエリを処理せよ.

区間 ${[l, r]}$ の数列の要素を ${D(a_i)}$ に置き換える.
区間 ${[l, r]}$ の和を求める.

解法

ある要素に対して REPLACE 操作は高々 ${6}$ 行えば ${2}$ 以下になる.

区間の和を効率的に求めたくて, 更新もしたいので BIT を持っておく.

${3}$ 以上の要素を持つ要素位置を set でもっておいて, set 内に存在する間は愚直にBITを更新, ${2}$ 以下になれば set から消す.

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

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

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

  T sum(int 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;
  }
};

int N, M, A[300000];
int con[10000001];

int main()
{
  for(int i = 1; i <= 1000000; i++) {
    for(int j = i; j <= 1000000; j += i) {
      ++con[j];
    }
  }

  scanf("%d %d", &N, &M);
  BinaryIndexedTree< int64 > bit(N);
  set< int > st;
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    bit.add(i, A[i]);
    if(con[A[i]] != A[i]) st.emplace(i);
  }
  st.emplace(13333333);
  for(int i = 0; i < M; i++) {
    int t, l, r;
    scanf("%d %d %d", &t, &l, &r);
    --l, --r;
    if(t == 1) {
      auto it = st.lower_bound(l);
      while(*it <= r) {
        bit.add(*it, -A[*it]);
        A[*it] = con[A[*it]];
        bit.add(*it, A[*it]);
        if(con[A[*it]] != A[*it]) ++it;
        else it = st.erase(it);
      }
    } else {
      printf("%lld\n", bit.sum(r) - bit.sum(l-1));
    }
  }
}

G. List Of Integers

codeforces.com

問題概要

${L(x, p)}$ を ${gcd(p, y) = 1}$ かつ ${y \gt x}$ となるような ${y}$ を昇順に並べた数列と定義する.

${L(x, p)}$ 上で ${k(1 \le x, p, k \le 10^6)}$ 番目の値を求める ${t(1 \le t \le 30000)}$ 個のクエリを処理せよ.

解法

${X}$ と互いに素であるためには, ${X}$ と共通の素因数を持たない必要がある. ここで素因数の数は高々 ${7}$ 個.

ある値 ${v}$ 以下で ${X}$ と互いに素である値の個数が数えられれば二分探索ができる.

包除原理を考えると, 少なくとも ${1}$ 個共通の素因数を持つものの個数が分かればよくてこれは割れば求まるためできる.

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

vector< int > prime_factor(int n)
{
  vector< int > primes;
  for(int i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      primes.emplace_back(i);
      while(n % i == 0) n /= i;
    }
  }
  if(n != 1) primes.emplace_back(n);
  return (primes);
}

int main()
{
  int T;
  cin >> T;
  while(T--) {
    int X, P, K;
    cin >> X >> P >> K;

    auto ps = prime_factor(P);

    auto check = [&](int x)
    {
      int64 ret = 0;
      for(int i = 0; i < (1 << ps.size()); i++) {
        int64 sum = 0, factor = 1;
        for(int j = 0; j < ps.size(); j++) {
          if(i & (1 << j)) factor *= ps[j];
        }
        if(__builtin_popcount(i) % 2 == 0) ret += x / factor;
        else ret -= x / factor;
      }
      return(ret);
    };

    int ok = 10000000, ng = X;
    auto pre_count = check(X);
    while(ok - ng > 1) {
      int mid = (ok + ng) / 2;
      if(check(mid) - pre_count >= K) ok = mid;
      else ng = mid;
    }
    cout << ok << endl;
  }
}

ei1333の日記

ぺこい

Educational Codeforces Round 37

A. Water The Garden

問題概要

解法

ソース

B. Tea Queue

問題概要

解法

ソース

C. Swap Adjacent Elements

問題概要

解法

ソース

D. Tanks

問題概要

解法

ソース

E. Connected Components?

問題概要

解法

ソース

F. SUM and REPLACE

問題概要

解法

ソース

G. List Of Integers

問題概要

解法

ソース