Codeforces Round #404 (Div. 2)

おー.

A. Anton and Polyhedrons

codeforces.com

問題概要

わすれた. 多分立体の何かが与えられる.

解法

†やるだけ†

この問題が†やるだけ†じゃなかったら, 他の任意の問題の解法の†やるだけ†は成立しなさそう.

ソース

スペルミスして落ちそうでこわかった.

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  cin >> N;
  int ret = 0;
  while(N--) {
    string S;
    cin >> S;
    if(S == "Tetrahedron") ret += 4;
    else if(S == "Cube") ret += 6;
    else if(S == "Octahedron") ret += 8;
    else if(S == "Dodecahedron") ret += 12;
    else ret += 20;
  }
  cout << ret << endl;
}

B. Anton and Classes

codeforces.com

問題概要

${n}$ 個の区間集合 ${[l_{1,i},r_{1,i}]}$ と ${m}$ 個の区間集合 ${[l_{2,i},r_{2,i}]}$ が与えられる.

それぞれの集合から ${1}$ 個ずつ取ってきて, 距離を最大化せよ.

解法

一方の区間集合を固定し, もう一方で総当り.

ある区間に最も離れた区間は ${R_i}$ の最小値か ${L_i}$ の最大値の区間なので, このうち最大をとる.

ソース

うん. はまるとこわそう.

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, M, L[200000], R[200000];

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


  int ret = 0;
  cin >> M;
  for(int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B;
    ret = max(ret, A - R[0]);
    ret = max(ret, L[N - 1] - B);
  }

  cout << ret << endl;
}

C. Anton and Fairy Tale

codeforces.com

問題概要

最大で ${n(1 \le n \le 10^{18})}$ 個穀物を入れられる納屋があって, 最初は満タンである. ${i}$ 日目において以下の操作を繰り返した時, 最初に納屋の穀物が空となる日は何日目か求めよ.

納屋に ${m(1 \le m \le 10^{18})}$ 個の穀物を補充する. 納屋の容量を上回る分は無視する.
${i}$ 個の穀物が納屋から減る.

解法

${n \le m}$ のとき答えは ${n}$ なので, それ以外を考える.

${m + 1}$ 日目開始前までは納屋が満タンであるが, それ以降穀物を補充することにより納屋が満タンになることはない. この事実を利用すると ${i}$ 日目終了時の穀物の個数が何個かを立式できる. 最初に穀物の個数が ${0}$ 以下になる日を探すのは二分探索で可能なので, えいってやる.

ソース

答えの最大値を考えるのが面倒で, オーバーフローしそうなので python した. python は偉大.

N, M = map(int, input().split())

if N <= M:
    print(N)
else:
    low = M + 1
    high = 1000000000000000000
    while high - low > 0:
        mid = (low + high) // 2
        if N + (mid - (M + 1)) * M - ((mid - M) * (M + 1 + mid) // 2) <= 0:
            high = mid
        else:
            low = mid + 1
    print(low)

D. Anton and School - 2

codeforces.com

問題概要

長さ ${n}$ の RSBS は, 以下の条件をすべて満たす文字列である.

${n \ne 0}$
${n}$ は偶数
最初の ${n/2}$ 文字は ‘(’
つづく ${n/2}$ 文字は ‘)’

文字列 ${s(1 \le |s| \le 2 \times 10^5)}$ が与えられる. いくつかの文字を削除することにより, 文字列を RSBS にしたい. 削除する文字位置の組み合わせを ${10^9 + 7}$ で割った余りで求めよ.

解法

生成する RSBS で一番右の ‘(’ の位置で総当りする.

一番右の ‘(’ の位置が分かっているとする. 生成できる最大の RSBS の長さは, min({それを含む左の ‘(’ の個数 ${l}$ }, {それより右の ‘)’ の個数 ${r}$ }) ${\times 2}$ である.

従ってこのとき生成できる RSBS の個数は ${\sum_{i=1}^{\min(l,r)} {}_{l-1} \mathrm{ C }_{i-1} {}_{r} \mathrm{ C }_{i} = \frac {(l+r-1)!} {l! (r-1)!}}$ である. この値は階乗と階乗の逆元のテーブルがあれば ${O(1)}$ で求めることができる.

ソース

式変形がわりと非自明.

#include<bits/stdc++.h>

using namespace std;

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

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

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}

inline int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}

static int64 fact[404040], rfact[404040];


int main()
{
  fact[0] = rfact[0] = 1;
  for(int i = 1; i < 404040; i++) {
    fact[i] = fact[i - 1] * i % mod;
    rfact[i] = modInv(fact[i]);
  }

  string S;
  cin >> S;
  int N = (int) S.size();
  CumulativeSum< int > open(N), close(N);
  for(int i = 0; i < S.size(); i++) {
    if(S[i] == '(') open.add(i, 1);
    else close.add(i, 1);
  }
  open.build();
  close.build();

  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    if(S[i] == '(') {
      int l = open.query(i), r = close.query(N) - close.query(i);
      (ret += fact[l + r - 1] % mod * rfact[l] % mod * rfact[r - 1] % mod) %= mod;
    }
  }

  cout << ret << endl;
}

E. Anton and Permutation

codeforces.com

問題概要

長さ ${n(1 \le n \le 200000)}$ の数列 ${a_1, a_2, \dots, a_n}$ があって最初は順に ${1, 2, \dots, n}$ である.

${l_i}$ 番目の要素と ${r_i}$ 番目の要素をswapして, 数列全体の転倒数の個数を求める ${q(1 \le q \le 50000)}$ 個のクエリが時系列順に与えられるので全て処理せよ.

解法

ある数列の状態でこれを二次元平面にプロット( ${(i, a_i)}$ の位置)してみる.

ここで, ${2}$ つの要素を入れ替えた時の転倒数の個数の変化は, 左下の点 ${(l, a_l)}$ , 右上の点 ${(r, a_r)}$ とする長方形内に含まれる点の数 ${\times 2 + 1}$ となることが知られている(JOI のバブルソートの解説とかを参照).

よってやりたいことはすぐ分かって, 二次元平面の点の追加削除とある長方形内の点の個数を求めるクエリを効率的に処理できればよい.

これは, セグメント木に平衡二分探索木をのせればできるため(?) 勝てる. ${O(n \log^2 n)}$ .

定数倍が厳しいので注意.

ソース

データ構造で殴る人だ. なんかのせてはいけないものをのせてしまった感.

pb_ds の tree をはじめてつかった.

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

struct SegmentTree
{
  int sz;
  vector< tree< int, null_type, less< int >, rb_tree_tag, tree_order_statistics_node_update > > seg;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.resize(2 * sz - 1);
  }

  int query(int a, int b, int lower, int upper, int k, int l, int r)
  {
    if(a >= r || b <= l) {
      return (0);
    } else if(a <= l && r <= b) {
      return (seg[k].order_of_key(upper) - seg[k].order_of_key(lower));
    } else {
      return (query(a, b, lower, upper, 2 * k + 1, l, (l + r) >> 1) + query(a, b, lower, upper, 2 * k + 2, (l + r) >> 1, r));
    }
  }

  int query(int a, int b, int l, int r)
  {
    return (query(a, b, l, r, 0, 0, sz));
  }

  void update(int k, int x, bool type)
  {
    k += sz - 1;
    if(type) seg[k].insert(x);
    else seg[k].erase(x);
    while(k > 0) {
      k = (k - 1) >> 1;
      if(type) seg[k].insert(x);
      else seg[k].erase(x);
    }
  }
};

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

  long long sum = 0;
  int S[200000];
  SegmentTree tree(N);
  for(int i = 0; i < N; i++) S[i] = i, tree.update(i, i, true);

  for(int i = 0; i < Q; i++) {
    int L, R;
    scanf("%d %d", &L, &R);
    --L, --R;
    if(L > R) swap(L, R);
    if(L != R) {
      if(S[L] < S[R]) sum += 1LL * 2 * tree.query(L + 1, R, S[L], S[R]) + 1;
      else sum -= 1LL * 2 * tree.query(L + 1, R, S[R], S[L]) + 1;
      tree.update(L, S[L], false);
      tree.update(R, S[R], false);
      swap(S[L], S[R]);
      tree.update(L, S[L], true);
      tree.update(R, S[R], true);
    }
    printf("%lld\n", sum);
  }
}

ei1333の日記

ぺこい

Codeforces Round #404 (Div. 2)

A. Anton and Polyhedrons

問題概要

解法

ソース

B. Anton and Classes

問題概要

解法

ソース

C. Anton and Fairy Tale

問題概要

解法

ソース

D. Anton and School - 2

問題概要

解法

ソース

E. Anton and Permutation

問題概要

解法

ソース