ei1333の日記

ぺこい

Codeforces Round #353 (Div. 2)

A, B, D を出してそれらは通った. C 解けないのは頭が悪い.
D に変なバグを埋め込まなかったの久しぶり.
1716 -> 1800(+84). ちょっとずつ上がっていってる.

A. Infinite Sequence

問題概要

3 つの整数  {a, b, c (-10^9 \le a, b, c \le 10^9)} が与えられる.
数列  {s} について  {s_{1} = a},  {s_{i} - s_{i - 1} = c} の場合を考えるとき,  {s} の中に  {b} が含まれれば "YES", 含まれなければ "NO" を出力せよ.

解法

  •  {c = 0} のとき,  {a} が無限に続くので  {a == b} か見る.
  •  {c \gt 0} のとき,  {a \gt b} のときは "NO". それ以外は {b - a}{c} の倍数かどうか見れば良い.
  •  {c \lt 0} のとき,  {a \lt b} のときは "NO". それ以外は {b - a}{c} の倍数かどうか見れば良い.

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int main()
{
  int64 A, B, C;
  cin >> A >> B >> C;

  B -= A;
  A -= A;

  if(A == B) {
    cout << "YES" << endl;
  } else if(C == 0) {
    cout << "NO" << endl;
  } else if(C > 0 && A > B) {
    cout << "NO" << endl;
  } else if(C < 0 && A < B) {
    cout << "NO" << endl;
  } else if(B % abs(C) == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

B. Restoring Painting

問題概要

?a?
b?c
?d?

上のような  {3 \times 3} のマスがある. 各マスには,  {\lbrack 1, n \rbrack (1 \le n \le 100 000)} の数字を書くことが出来るが, どの連続した  {2 \times 2} のグリッドを取り出しても総和が等しくなる必要がある.
 {a, b, c, d (1 \le a, b, c, d \le n)} が分かっている.  {?} に当てはまる数字の組み合わせの個数を求めよ.

解法

真ん中を決めると、それぞれの  {2 \times 2} のグリッドで分からない値がそれぞれ独立に 1 つ残る.
するとそれぞれのグリッドの総和の上限(+N)と下限(+1)がわかるので, そのすべてを満たす範囲を足せばよい.

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int main()
{
  int64 N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  int64 ret = 0;
  for(int i = 1; i <= N; i++) {
    int64 a = i + A + B;
    int64 b = i + A + C;
    int64 c = i + B + D;
    int64 d = i + C + D;
    auto mx = minmax({a, b, c, d});
    ret += max(N - mx.second + mx.first, 0LL);
  }
  cout << ret << endl;
}

C. Money Transfers

問題概要

長さ  N (1 \le N \le 100 000) の円環があり, 各要素は  {a_{i} (-10^{9} \le a_{i} \le 10^{9})} である.
1 ステップで, ある要素  {i} を選んで任意の量だけ,  {i + 1} {i - 1} の要素に送ることができる.
すべての要素を  {0} にするための最小ステップ数を求めよ.

解法

気づけばあっさり.
まず, それぞれなるべく短い区間で送受信を終えたいので, 合計すると 0 になるような連続部分列をたくさん作るとよい.

任意の地点から右に流し始めることを考えると, 累積したときに 0 になる回数が連続部分列の個数となる.
また, 1 つの地点からの累積和をとっておけば, 任意の地点から始めたときの回数は累積和の途中でその値になった回数に置き換えることができて, これで解くことができる. (日本語が難しい)

ソース

なんとなくはわかっていたんだけど難しく考えるとダメだね...

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int INF = 1 << 30;
int main()
{
  int N;
  cin >> N;
  int64 sum = 0;
  map< int64, int > mp;
  for(int i = 0; i < N; i++) {
    int D;
    cin >> D;
    sum += D;
    ++mp[sum];
  }
  int ret = INF;
  for(auto k : mp) {
    ret = min(ret, N - k.second);
  }
  cout << ret << endl;
}

D. Tree Construction

問題概要

長さ  {n(2 \le n \le 100 000)}の, 数列  {a_i(1 \le a_i \le 10^9, a_i \ne a_j(i \ne j))} がある.
二分探索木を以下の手順に基づいて構築していく.

  1.  {a_1} を木の根とする.
  2.  {a_2, a_3, ..., a_n} の順に, 左部分木 < 右部分木となるように値を木に追加する.

このとき  {a_2, a_3, ..., a_n} のノードについて, それぞれの親ノードの値を求めよ.

解法

愚直にやるのは, 木が偏ったときに  {O(n^2)}となるのでダメ. なので工夫する(それはそう).
二分探索木の性質上, 任意のノード  {i}をとったとき,  iの左部分木の各値 <  iの値 <  iの右部分木の各値 となる. よって, 追加される場所は  {a_i} より 1 個大きい値をもつノードの左の子か  {a_i} より 1 個小さい値をもつノードの右の子のどちらかとなる.
この値を求めるにはsetの lower_bound() 等を使えば良いので,  {O(n \log n)} で解ける.

ソース

わりとあっさり.

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int main()
{
  int64 N, A[100000];
  pair< int, int > tree[100001];
  vector< int > nums;
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    nums.push_back(A[i]);
  }
  sort(nums.begin(), nums.end());
  for(int i = 0; i < N; i++) {
    A[i] = lower_bound(nums.begin(), nums.end(), A[i]) - nums.begin();
  }

  set< int > val;
  fill_n(tree, N, make_pair(-1, -1));
  val.insert(A[0]);
  for(int i = 1; i < N; i++) {
    auto p = val.lower_bound(A[i]);
    if(p != val.end() && tree[*p].first == -1) {
      tree[*p].first = A[i];
      cout << nums[*p] << " ";
    } else {
      --p;
      tree[*p].second = A[i];
      cout << nums[*p] << " ";
    }
    val.insert(A[i]); 
  }
}