Codeforces Round #441 (Div. 1)

だみだこり.

A. Classroom Watch

codeforces.com

問題概要

arc034.contest.atcoder.jp

解法

${n}$ の近辺しか ${n}$ になり得ないため, 近辺を適当に試せばよい.

なんだけど, 頭がないため ${10^8}$ の最悪をした. えー, ${8}$ 桁決めれば残り ${1}$ 桁は計算で求まります.

ソース

#include<bits/stdc++.h>

using namespace std;

int mult[] = {100000001, 10000001, 1000001, 100001, 10001, 1001, 101, 11, 2};
int mult2[] = {100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};


int main()
{
  int N;
  cin >> N;


  int fact = 1;
  vector< int > vs;
  for(int i = 0; i < 10; i++) {  // 0
    for(int j = 0; j < 10; j++) { // 1
      for(int k = 0; k < 10; k++) { // 2
        for(int l = 0; l < 10; l++) { // 3
          for(int m = 0; m < 10; m++) { // 4
            for(int n = 0; n < 10; n++) { // 5
              for(int o = 0; o < 10; o++) { // 6
                for(int p = 0; p < 10; p++) { // 7
                  int sum = mult[0] * i + mult[1] * j + mult[2] * k + mult[3] * l + mult[4] * m + mult[5] * n + mult[6] * o + mult[7] * p;
                  sum = N - sum;
                  if(sum < 0 || (sum & 1)) continue;
                  if(sum >= 20) continue;
                  sum >>= 1;
                  vs.push_back(mult2[0] * i + mult2[1] * j + mult2[2] * k + mult2[3] * l + mult2[4] * m + mult2[5] * n + mult2[6] * o + mult2[7] * p + sum);
                }
              }
            }
          }
        }
      }
    }
  }

  sort(begin(vs), end(vs));
  cout << vs.size() << endl;
  for(int i = 0; i < vs.size(); i++) cout << vs[i] << endl;

}

B. Sorting the Coins

codeforces.com

問題概要

${n}$ 枚のコインがあって最初は全部表向きである.

${i}$ 番目の操作では左から ${p_i}$ 番目のコインをひっくり返す.

それぞれの操作について, 以下の操作を何回行うか求めよ.

左から今見ているコインが裏向きかつその右のコインが左向きなら交換する操作を行う.

解法

何をやってもできそう.

Union-Find が好きなため, Union-Find でやった. 末尾のアと適切に unite しておけば末尾から連続する裏向きのコインの数がわかるため, えい.

ソース

#include<bits/stdc++.h>

using namespace std;

struct UnionFind
{
  vector< int > data;

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

  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, P[300000];

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

  cout << 1 << " ";
  UnionFind uf(N);
  bool kill[300000] = {};
  int sz = 0;

  for(int i = 0; i < N; i++) {
    ++sz;
    kill[P[i]] = true;
    if(P[i] > 0 && kill[P[i] - 1]) uf.unite(P[i] - 1, P[i]);
    if(P[i] + 1 < N && kill[P[i] + 1]) uf.unite(P[i] + 1, P[i]);
    int ret = sz;
    if(kill[N - 1]) ret -= uf.size(N - 1);
    cout << ret + 1 << " ";
  }
  cout << endl;
}

C. National Property

codeforces.com

問題概要

${1}$ から ${m}$ までの ${m}$ 種類の文字があって, それぞれ小文字か大文字がある.

${n}$ 個の文字列が順番に与えられる. 最初全ての文字は小文字である.

いくつかの種類の文字を大文字にすることで辞書順にできるか判定し, できるときはその一例を求めよ.

解法

2-SAT.

${i}$ 番目の文字を大文字にするとき真とする, bool変数を考える.

隣り合っている文字列の大小関係のみを考慮すれば良くて, また文字列の共通部分もどうでもよいため, 基本的には最初に異なる文字だけ考えれば良い.

この文字を ${s_{i-1,j}, s_{i,j}}$ とする.

${s_{i-1,j} \lt s_{i,j}}$ のとき, ${s_{i,j}}$ を真かつ ${s_{i-1,j}}$ を偽するとダメ. ${ (\lnot s_{i,j} \lor s_{i-1,j})}$ なので, はい.

${s_{i-1,j} \gt s_{i,j}}$ のとき, ${s_{i,j}}$ を真かつ ${s_{i-1,j}}$ を偽にしないとダメ. まあこれもはい.

できる.

復元は ${x}$ を含む強連結成分が ${\lnot x}$ を含む強連結成分より後かどうかでOK.

ソース

ライブラリを作ったね.

#include<bits/stdc++.h>

using namespace std;

struct StronglyConnectedComponents
{
  vector< vector< int > > gg, rg;
  vector< pair< int, int > > edges;
  vector< int > comp, order, used;

  StronglyConnectedComponents(size_t v) : gg(v), rg(v), comp(v, -1), used(v, 0) {}

  virtual void add_edge(int x, int y)
  {
    gg[x].push_back(y);
    rg[y].push_back(x);
    edges.emplace_back(x, y);
  }

  int operator[](int k)
  {
    return (comp[k]);
  }

  void dfs(int idx)
  {
    if(used[idx]) return;
    used[idx] = true;
    for(int to : gg[idx]) dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt)
  {
    if(comp[idx] != -1) return;
    comp[idx] = cnt;
    for(int to : rg[idx]) rdfs(to, cnt);
  }

  void build(vector< vector< int > > &t)
  {
    for(int i = 0; i < gg.size(); i++) dfs(i);
    reverse(begin(order), end(order));
    int ptr = 0;
    for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++;

    t.resize(ptr);
    set< pair< int, int > > connect;
    for(auto &e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      if(connect.count({x, y})) continue;
      t[x].push_back(y);
      connect.emplace(x, y);
    }
  }
};

struct TwoSatisfiability : StronglyConnectedComponents
{
  int sz;

  TwoSatisfiability(size_t v) : sz(v), StronglyConnectedComponents(v + v) {}

  void add_edge(int u, int v) // (u or v)
  {
    StronglyConnectedComponents::add_edge(rev(u), v);
    StronglyConnectedComponents::add_edge(rev(v), u);
  }

  void add_edge(int u)
  {
    TwoSatisfiability::add_edge(u, u);
  }

  inline int rev(int x)
  {
    if(x >= sz) return (x - sz);
    return (x + sz);
  }

  bool operator()(int v) // note
  {
    return ((*this)[v] > (*this)[rev(v)]);
  }

  bool solve()
  {
    vector< vector< int > > g;
    build(g);
    for(int i = 0; i < sz; i++) {
      if((*this)[i] == (*this)[rev(i)]) return (false);
    }
    return (true);
  }
};

void fail()
{
  puts("No");
  exit(0);
}

int main()
{
  int N, M;
  vector< int > s[100000];

  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    int L;
    cin >> L;
    s[i].resize(L);
    for(auto &p : s[i]) cin >> p, --p;
  }

  TwoSatisfiability sat(M);
  for(int i = 1; i < N; i++) {
    int lcp = 0;
    while(lcp < min(s[i - 1].size(), s[i].size()) && s[i - 1][lcp] == s[i][lcp]) ++lcp;
    if(lcp == s[i - 1].size()) {
      continue;
    } else if(lcp == s[i].size()) {
      fail();
    } else if(s[i - 1][lcp] < s[i][lcp]) {
      sat.add_edge(s[i - 1][lcp], sat.rev(s[i][lcp]));
    } else {
      sat.add_edge(s[i - 1][lcp]);
      sat.add_edge(sat.rev(s[i][lcp]));
    }
  }
  if(!sat.solve()) fail();
  vector< int > change;
  for(int i = 0; i < M; i++) {
    if(sat(i)) change.emplace_back(i);
  }
  puts("Yes");
  printf("%d\n", (int) change.size());
  for(auto &p : change) printf("%d ", p + 1);
  puts("");
}

D. High Cry

codeforces.com

問題概要

長さ ${n}$ の数列 ${a_i}$ が与えられる.

任意の ${(l, r)}$ のペアのうち, 区間の ${a_i}$ の OR が区間内の任意の要素を上回るようなものの個数を求めよ.

解法

以下, 簡単のため要素が相異なると仮定する.

ある区間 ${[l, r)}$ をとってきたときに条件を満たすか判定するために必要な要素は, 区間のORの値と区間の最大値だけである.

区間のORの値から考えるのはヤバいため, 区間の最大値の方の値を固定して考えてみる.

区間の最大値 ${x}$ を昇順に試していき, ${x}$ 未満が最大値となる場合は処理済みであるとする.

${x}$ 未満のアをいい感じに処理しておけば ${x}$ が最大となる場合の区間 ${[L,R]}$ を ${O(1)}$ で求めることができる. 自分より左側, 右側それぞれについて ${x}$ 未満の値が何個連続してつながってるかを求めれば, それが答えになっている(ここでは左端と右端を持ったUnion-Findを使っている).

この区間 ${[L,R]}$ 内かつ最大値 ${x}$ を含む区間の取り方のうち, 区間のORの値が ${x}$ より大きくなるものを求めればよい.

区間のORがアになるものは, ${x}$ で立ってないbitが立っている要素が含まれる場合である. このようなアもなんか区間になっていて, 自分の左側の最右の立っているアの位置を ${a}$ , 自分の右側の最左の立っているアの位置を ${b}$ とすると, 左端 ${[L,a]}$ と右端 ${[i, R]}$ のペア, 左端 ${[L,i]}$ と右端 ${[b, R]}$ のペアをとるみたいな雰囲気が生えて, 共通部分を引いたりするとなんかとくことができる.

相異なる場合を考えていたが, 同じものがあっても左のほうから処理することでいい感じに求めることができる.

計算量は ${O(n \log a_i)}$ .

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

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

  UnionFind(int sz)
  {
    data.assign(sz, -1);
    left.resize(sz);
    right.resize(sz);
    for(int i = 0; i < sz; i++) left[i] = i;
    for(int i = 0; i < sz; i++) right[i] = i;
  }

  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);
  }

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

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

const int INF = 1 << 30;

int N, A[200000];
int latte[31][200000], malta[31][200000];

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

  vector< int > order(N);
  iota(begin(order), end(order), 0);
  sort(begin(order), end(order), [&](int a, int b)
  {
    if(A[a] == A[b]) return (a < b);
    return (A[a] < A[b]);
  });

  for(int j = 0; j < 31; j++) {
    for(int i = 0; i < N; i++) {
      if((A[i] >> j) & 1) malta[j][i] = i;
      else if(i == 0) malta[j][i] = -INF;
      else malta[j][i] = malta[j][i - 1];
    }
    for(int i = N - 1; i >= 0; i--) {
      if((A[i] >> j) & 1) latte[j][i] = i;
      else if(i == N - 1) latte[j][i] = INF;
      else latte[j][i] = latte[j][i + 1];
    }
  }

  UnionFind uf(N);
  bool live[200000] = {};
  int64 ret = 0;
  for(int i : order) {
    int left = -INF, right = INF;
    for(int j = 0; j < 31; j++) {
      if((A[i] >> j) & 1) continue;
      left = max(left, malta[j][i]);
      right = min(right, latte[j][i]);
    }
    if(i > 0 && live[i - 1]) uf.unite(i, i - 1);
    if(i + 1 < N && live[i + 1]) uf.unite(i, i + 1);
    const auto LL = uf.left[uf.find(i)];
    const auto RR = uf.right[uf.find(i)];
    const auto beet1 = max(0, left - LL + 1);
    const auto beet2 = max(0, RR - right + 1);
    ret += 1LL * beet1 * (RR - i + 1);
    ret += 1LL * beet2 * (i - LL + 1);
    ret -= 1LL * beet1 * beet2;
    live[i] = true;
  }
  cout << ret << endl;
}

ei1333の日記

ぺこい

Codeforces Round #441 (Div. 1)

A. Classroom Watch

問題概要

解法

ソース

B. Sorting the Coins

問題概要

解法

ソース

C. National Property

問題概要

解法

ソース

D. High Cry

問題概要

解法

ソース