ei1333の日記

ぺこい

Educational Codeforces Round 23

にゃん.

oo-oo- 160th.

A. Treasure Hunt

codeforces.com

問題概要

 {(x, y) (1 \le x, y \le 10^5)} が与えられる. 次の操作を何回か行って  {(x_1, y_1) (-10^5 \le x_1, y_1 \le 10^5)} {(x_2, y_2) (-10^5 \le x_2, y_2 \le 10^5)} にできるか判定せよ.

  •  {(a, b) \to (a + x, b + y)}.
  •  {(a, b) \to (a + x, b - y)}.
  •  {(a, b) \to (a - x, b + y)}.
  •  {(a, b) \to (a - x, b - y)}.

解法

あまりにも むずかしすぎる.

 {(a, b) \to (a + x, b + y) \to (a - x, b + y)} みたいな操作をすると,  {a} の値を動かさずに  {b} の値を  {2y} 動かせる.

あとはフィーリングでえいすれば解ける.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int X1, Y1, X2, Y2, X, Y;

  cin >> X1 >> Y1 >> X2 >> Y2;
  cin >> X >> Y;

  int sa1 = abs(X1 - X2), sa2 = abs(Y1 - Y2);
  if(sa1 % X != 0 || sa2 % Y != 0) {
    cout << "NO" << endl;
  } else {
    sa1 /= X;
    sa2 /= Y;
    if((abs(Y1 - Y2) + sa1*Y) % (2 * Y) == 0 || (abs(X1 - X2) + sa2*X) % (2 * X) == 0) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
}

B. Makes And The Product

codeforces.com

問題概要

長さ  {n(3 \le n \le 10^5)} の数列  {a_i(1 \le a_i \le 10^9)} が与えられる.

 {a_i a_j a_k} が最小となるような  {(i, j, k) (i \lt j \lt k)} の組は何個あるか求めよ.

解法

 {n} 分考えてよくわからなかったので貼った(正確には面倒そうだった).

まずソートしても答えは変わらないのでソートする. すると  {3} つの値が  {a_1, a_2, a_3} となるものが最小の選び方.

 {\mathrm{dp}[i][j]:=} 今までで  {i} 個選んでいて最後に  {j} 番目の要素を選んだ時の組み合わせの個数

とすればなんかいい感じの DP ができる.

 {a_j = a_i} を満たす要素  {j} に対して  {\displaystyle \mathrm{dp}[i][j]=\sum_{k=1}^{j-1} \mathrm{dp}[i-1][k]} みたいな遷移をする.

サボって BIT を使えば  {O(n \log n)}.

ソース

#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(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 main()
{
  int N, A[100000];

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

  BinaryIndexedTree< int64 > bit(N);
  for(int i = 0; i < 3; i++) {
    BinaryIndexedTree< int64 > bit2(N);
    for(int j = 0; j < N; j++) {
      if(A[j] == A[i]) bit2.add(j, i==0?1:bit.sum(j - 1));
    }
    swap(bit, bit2);
  }
  cout << bit.sum(N - 1) << endl;
}

C. Really Big Numbers

codeforces.com

問題概要

 {n(1 \le n \le 10^{18})} 以下の正整数  {x} のうち  {x} {x} の桁ごとの和の差が  {s(1 \le s \le 10^{18})} となるようなものは何個あるか求めよ.

解法

解けない(ア

方針が違っていて無限にバグった. 何でもかんでも桁DPを考えるのよくないね…

桁DPを考えると

 {\mathrm{dp}[idx][free][sa]:=} 上から  {idx} 桁目まで見て, 今までで  {n} を下回る桁があったかどうかが  {free} で 差が  {sa} のときの条件を満たす個数

となる.  {sa} の状態数がアレなのでDPできてない気がするが闇をすれば通る.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int64 T;
string S;

unordered_map< int64, int64 > dp[19][2];
int64 dp2[19][2];
unsigned long long mod_pow[19];

int64 rec2(int idx, bool free)
{
  if(idx == S.size()) return (1);
  if(~dp2[idx][free]) return (dp2[idx][free]);
  int end = free ? 9 : S[idx] - '0';
  int64 ret = 0;
  for(int i = 0; i <= end; i++)
    ret += rec2(idx + 1, free | (i != end));
  return (dp2[idx][free] = ret);
}

int64 rec(int idx, bool free, int64 ketasum, int64 oddsum)
{
  if(idx == S.size()) return (oddsum - ketasum >= T);
  if(oddsum - ketasum >= T) return (rec2(idx, free));
  if(dp[idx][free].count(oddsum - ketasum)) return (dp[idx][free][oddsum - ketasum]);
  if(oddsum + (mod_pow[S.size() - idx] - 1) - ketasum < T) return (0);
  int end = free ? 9 : S[idx] - '0';
  int64 ret = 0;
  for(int i = 0; i <= end; i++)
    ret += rec(idx + 1, free | (i != end), ketasum + i, oddsum + i * mod_pow[S.size() - idx - 1]);
  return (dp[idx][free][oddsum - ketasum] = ret);
}

int main()
{
  memset(dp2, -1, sizeof(dp2));
  mod_pow[0] = 1;
  for(int i = 1; i < 19; i++) mod_pow[i] = mod_pow[i - 1] * 10;
  cin >> S >> T;
  cout << rec(0, false, 0, 0) << endl;
}

D. Imbalanced Array

codeforces.com

問題概要

長さ  {n(1 \le n \le 10^6)} の数列  {a_i(1 \le a_i \le 10^6)} が与えられる.

ある数列の imbalance value を, 要素の最大値 - 最小値 と定義する.

数列の任意の subsegment について imbalance value を計算して, それらを足し合わたときの和を求めよ.

解法

実 家 の よ う な 安 心 感

だと思って解いたけど stack を使ったり分割統治したりする賢い解法があった. 悲しいね(?).

まず inbalance value の最大値と最小値は独立なので, 全体の最大値の和を計算して最小値の和を引く.

ぐっと睨むと subsegment の最小値を固定して考えたくなる. (最大値も反転させれば同様に求まる).

最小値として  {a_i} を含むような subsegment をそれぞれの  {i} について数える.

これは値  {a_i} を含みつつ  {a_i} 未満の値を含まないものなので, 左右方向をみたときに  {a_i} 未満の値が出現する最も近い index が分かれば良い.

これは BIT でできるためうん.

あとははい.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

const int INF = 1 << 30;

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

  BinaryIndexedTree1(int sz)
  {
    data.assign(++sz, -INF);
  }

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

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


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

  BinaryIndexedTree2(int sz)
  {
    data.assign(++sz, INF);
  }

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

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

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

  CumulativeSum(int sz) : data(sz, 0) {};

  void add(int k, int x)
  {
    data[k] += x;
  }

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

  T query(int k)
  {
    if(k < 0) return (0);
    return (data[min(k, (int) data.size() - 1)]);
  }
};

int N, A[1000000], Latte[1000000], Malta[1000000];
int latte[1000000], malta[1000000];
vector< int > appear[1000001];

int main()
{
  scanf("%d", &N);
  CumulativeSum< int64 > sum(N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    sum.add(i, A[i]);
    appear[A[i]].push_back(i);
  }
  sum.build();
  BinaryIndexedTree1< int > bit1(1000001);
  BinaryIndexedTree2< int > bit2(1000001);
  BinaryIndexedTree1< int > bit3(1000001);
  BinaryIndexedTree2< int > bit4(1000001);

  for(int i = 0; i < N; i++) {
    Latte[i] = max(-1, bit1.sum(A[i]));
    bit1.add(A[i], i);
  }
  for(int i = N - 1; i >= 0; i--) {
    Malta[i] = min(N, bit2.sum(A[i] - 1));
    bit2.add(A[i], i);
  }
  for(int i = 0; i < N; i++) {
    A[i] = 1000001 - A[i];
  }
  for(int i = 0; i < N; i++) {
    latte[i] = max(-1, bit3.sum(A[i]));
    bit3.add(A[i], i);
  }
  for(int i = N - 1; i >= 0; i--) {
    malta[i] = min(N, bit4.sum(A[i] - 1));
    bit4.add(A[i], i);
  }

  int64 ret = 0;
  for(int i = 0; i < 1000001; i++) {
    for(int j : appear[i]) {
      int64 L = Latte[j] + 1;
      int64 R = Malta[j] - 1;
      ret -= (R - j + 1) * (j - L + 1) * i;
    }
    for(int j : appear[i]) {
      int64 L = latte[j] + 1;
      int64 R = malta[j] - 1;
      ret += (R - j + 1) * (j - L + 1) * i;
    }
  }
  cout << ret << endl;
}

E. Choosing The Commander

codeforces.com

問題概要

 {q(1 \le q \le 10^5)} 個のクエリが与えられるので全て処理せよ.

  1.  {p_i} {1} 個集合に加える.
  2.  {p_i} {1} 個集合から消す.
  3.  {p_i} と集合の各要素の値と XOR をとった値が  {l_i} 未満であるものの個数を数える.

解法

Trieを貼ります(終わり)(これは罠でライブラリがないので終わらない).

クエリ  {1, 2} に対しては値を  {2} 進数で表した時のあれを追加削除する.

クエリ  {3} に対してはいい感じにXORをとりながら上からくだっていく(解説になってないね).

雰囲気は  {l_i} の境界のノードをぐいーって感じでたどる.

ソース

なんか文字列を管理するTrieしかなかったので, 整数にしてたら時間がかかった.

#include<bits/stdc++.h>

using namespace std;

struct TrieNode
{
  int nxt[2];
  int exist;
  //vector< int > accept;

  TrieNode() : exist(0)
  {
    memset(nxt, -1, sizeof(nxt));
  }
};

struct Trie
{
  vector< TrieNode > nodes;
  int root;

  Trie() : root(0)
  {
    nodes.push_back(TrieNode());
  }

  virtual void direct_action(int node, int id) {}

  virtual void child_action(int node, int child, int id) {}

  void update_direct(int node, int id)
  {
    nodes[node].exist += id;
  }

  void update_child(int node, int child, int id)
  {
    nodes[node].exist += id;
  }

  void add(int str, int str_index, int node_index, int id)
  {
    if(str_index == -1) {
      update_direct(node_index, id);
    } else {
      const int c = (str >> str_index) & 1;
      if(nodes[node_index].nxt[c] == -1) {
        nodes[node_index].nxt[c] = (int) nodes.size();
        nodes.push_back(TrieNode());
      }
      add(str, str_index - 1, nodes[node_index].nxt[c], id);
      update_child(node_index, nodes[node_index].nxt[c], id);
    }
  }

  void add(int str, int id)
  {
    add(str, 29, 0, id);
  }

  int query(int str, int t, int str_index, int node_index, int mask)
  {
    if(str_index == -1) {
      return (0);
    } else {
      const int c = (str >> str_index) & 1;

      int next_mask = mask | (1 << str_index);
      int ret = 0;
      if(next_mask >= t) {
        if(c == 1) {
          if(~nodes[node_index].nxt[0]) ret += nodes[nodes[node_index].nxt[0]].exist;
          if(~nodes[node_index].nxt[1]) ret += query(str, t, str_index - 1, nodes[node_index].nxt[1], mask);
        } else {
          if(~nodes[node_index].nxt[1]) ret += nodes[nodes[node_index].nxt[1]].exist;
          if(~nodes[node_index].nxt[0]) ret += query(str, t, str_index - 1, nodes[node_index].nxt[0], mask);
        }
      } else {
        if(c == 1) {
          if(~nodes[node_index].nxt[0]) ret += query(str, t, str_index - 1, nodes[node_index].nxt[0], next_mask);
        } else {
          if(~nodes[node_index].nxt[1]) ret += query(str, t, str_index - 1, nodes[node_index].nxt[1], next_mask);
        }
      }
      return (ret);
    }
  }

  int query(int str, int t)
  {
    return (nodes[0].exist - query(str, t, 29, 0, 0));
  }
};

int main()
{
  int Q;
  scanf("%d", &Q);
  Trie trie;
  while(Q--) {
    int T, P, L;
    scanf("%d %d", &T, &P);
    if(T == 1) {
      trie.add(P, 1);
    } else if(T == 2) {
      trie.add(P, -1);
    } else {
      scanf("%d", &L);
      printf("%d\n", trie.query(P, L));
    }
  }
}