Codeforces Round #352 (Div. 2)

1714->1716(+2). 485位. ABCDを出してCD落ちた. 早解きに成功していたので命拾いした感じだけど, なんか最近バグを埋め込む不治の病を患って悲しい.

A. Summer Camp

問題概要

"123456789101112131415..." のように 1 から数字を並べた文字列がある.
${n(1 \le n \le 1000)}$ 文字目の数字は何か求めよ.

解法

高々1000文字以下なので, 実際に "12345..." のような文字列を生成して, $n$ 文字目を出力すれば解ける.

ソース

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

int main()
{
  string S = "";
  for(int i = 1; S.size() < 1500; i++) {
    stringstream sss;
    sss << i;
    S += sss.str();
  }
  int N;
  cin >> N;
  cout << S[N - 1] << endl;
}

B. Different is Good

問題概要

長さ ${n(1 \le n \le 100 000)}$ の小文字のアルファベットからなる文字列 $s$ が与えられる.
$s$ の任意の部分文字列が異なるようにするとき, 出来ない場合は-1, 出来る場合は最小でいくつの文字を変えればよいか求めよ.

解法

まず, 1文字の部分文字列すべてを考えれば, 任意の2文字以上の部分文字列は考えなくて良いことが分かる.
アルファベットの種類は 26 文字なので, $n \lt 26$ のとき, 異なるように出来ない.
$n \le 26$ の場合は, 任意の文字が2個以上存在してはダメなことより, すべて1個以下になるように文字を変える.
アルファベット $c$ の文字の個数を ${sum_{c}}$ とすると, 答えは $\sum_{'a' \le i \le 'z' } \max(0, sum_i - 1)$ となる.

ソース

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

int main()
{
  int N;
  string S;
  cin >> N;
  cin >> S;
  if(S.size() > 26) {
    cout << -1 << endl;
  } else {
    int sum[26] = {};
    for(int i = 0; i < N; i++) ++sum[S[i] - 'a'];
    int ret = 0;
    for(int i = 0; i < 26; i++) ret += max(0, sum[i] - 1);
    cout << ret << endl;
  }
}

C. Recycling Bottles

問題概要

座標平面上に ${n(1 \le n \le 100 000)}$ 個のボトルと, 1つのリサイクル箱, 2人の人間が存在する.
ボトルはそれぞれ ${(x_{i}, y_{i})}$ , リサイクル箱は ${(t_{x}, t_{y})}$ , 2人の人間はそれぞれ ${(a_{x}, a_{y})}$ , ${(b_{x}, b_{y})}$ に存在する ${(0 \le x_{i}, y_{i}, t_{x}, t_{y}, a_{x}, a_{y}, b_{x}, b_{y} \le 10^{9})}$ . ボトルをすべて, リサイクル箱に入れたい. それぞれの人間が, 最大 1 個のボトルを持って移動することが出来るとき, 2 人の移動距離の和を最小化せよ.

解法

人間の初期位置がリサイクル箱であるときのことを考えると, 任意のボトルと直線で往復すると移動距離の最小値となるのは明らか.
具体的には, $\sum_{i = 1}^{n} {2 \sqrt{ x_{i}^2 + y_{i}^2 }}$ .
人間の初期位置がリサイクル箱以外のときは, そこからボトル $i$ に向かうとき移動距離は, (初期位置から $i$ までの距離) - ( $i$ とリサイクル箱の距離(往路分)) だけ増減する. この増減分を $D_{i}$ とする.
最初に向かうボトル $i$ は全通り試せないので, よくある一般的なテク( ${D_{i}}$ の小さい順でソートして,　最小値同士をみて, それらのリサイクル箱が同じなら2番目の最小値でえいみたいなやつ)を使えばよい.

ソース

Wrong answer on test 61(1回目の絶望). ${n = 1}$ のときなんか落ちてたのでつらい.

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

struct Point
{
  int64 x, y;
};


Point a, b, t, p[100000];
double to[100000];
int64 N;

double dist(Point xx, Point yy)
{
  return(sqrt((xx.x - yy.x) * (xx.x - yy.x) + (xx.y - yy.y) * (xx.y - yy.y)));
}

int main()
{  
  
  cin >> a.x >> a.y >> b.x >> b.y >> t.x >> t.y;
  cin >> N;
  double sum = 0;
  vector< pair< double, int > > Anear, Bnear;
  for(int i = 0; i < N; i++) {
    cin >> p[i].x >> p[i].y;
    sum += dist(t, p[i]) * 2.0;
    Anear.push_back({dist(a, p[i]) - dist(t, p[i]), i});
    Bnear.push_back({dist(b, p[i]) - dist(t, p[i]), i});
  }
  
  sort(Anear.begin(), Anear.end());
  sort(Bnear.begin(), Bnear.end());

  double best = min(Anear[0].first, Bnear[0].first);
  if(N > 1) {
    if(Anear[0].second == Bnear[0].second) {
      best = min({best, Anear[0].first + Bnear[1].first, Anear[1].first + Bnear[0].first});
    } else {
      best = min(best, Anear[0].first + Bnear[0].first);
    }
  }
  cout << fixed << setprecision(15) << sum + best << endl;
}

D. Robin Hood

問題概要

長さ $n(1 \le n \le 500 000)$ の数列 ${c_{i} (1 \le c_{i} \le 10^9)}$ がある.
以下の操作を $k(0 \le k \le 10^9)$ 回繰り返す.

まず, ${c_{i}}$ の最大値の要素を選んで, それを -1 する. (複数あればそれらからランダム選択)
次に, ${c_{i}}$ の最小値の要素を選んで, それを +1 する. (複数あればそれらからランダム選択)

${\max_{1 \le i \le n} (c_{i}) - \min_{1 \le j \le n} (c_{j})}$ の最終的な値を求めよ.

解法(ちょっと強引です...)

$k$ 回シミュレーションをしようとしても間に合わないのでこれを高速化することを考える.
事前に, 1回以上出現する任意の数字の出現回数を map を使って, 数えておく. 出現する数字を $d_{i}$ , $d_{i}$ の出現回数を $e_{i}$ とする.
mapは出現する数字でソートされるので, 数列の最小値が $d_{begin}$ で最大値が $d_{end}$ である.
${d_{begin}}$ と ${d_{end}}$ がそれぞれ最小値, 最大値である回数は, ${\min(e_{begin}(d_{begin + 1} - d_{begin}), e_{end}(d_{end} - d_{end-1}))}$ であるので, この分だけ一気に回数を進めて更新する.
これを, 回数が余ってる場合で $d_{end} - d_{begin} \gt 1$ の間繰り返す(差が 1 以下になれば変動しなくなる).
計算量は, 各更新によって出現する数字が高々 $n$ 個なので, map の計算量と合わせて, $O(n \log n)$ となる(定数が重いのでかなりというか極めて怖いけど 0.98s / 1s で通ってるのでまあ).

ソース

Wrong answer on test 54(2回目の絶望). これもコーナーケースみたいなのに引っかかったんだよね...

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


int main()
{
  int N, K;
  scanf("%d %d", &N, &K);
  
  map< int64, int64 > mp;
  
  for(int i = 0; i < N; i++) {
    int c;
    scanf("%d", &c);
    mp[c]++;
  }

 
  while(K > 0 && (--mp.end()) -> first - mp.begin() -> first > 1) {
    auto small = *mp.begin();
    auto small2 = *++mp.begin();

    auto big   = *--mp.end();
    auto big2  = *(--(--mp.end()));

    int64 distsmall = small2.first - small.first;
    int64 distbig   = big.first - big2.first;
    
    int64 count_sum = min((int64)K, min(distsmall * small.second, distbig * big.second));
    if(small == big2) count_sum /= 2;
    
    int64 nextSmallUp = small.first + count_sum / small.second;
    int64 nextBigDown = big.first - count_sum / big.second;
    
    int64 nextSmallUpUp_count = count_sum % small.second;
    int64 nextBigDownDown_count = count_sum % big.second;
    
    K -= count_sum;
    
    mp.erase(mp.begin());
    mp.erase(--mp.end());
    
    mp[nextSmallUp] += small.second - nextSmallUpUp_count;
    if(nextSmallUpUp_count > 0) mp[nextSmallUp + 1] += nextSmallUpUp_count;

    mp[nextBigDown] += big.second - nextBigDownDown_count;
    if(nextBigDownDown_count > 0) mp[nextBigDown - 1] += nextBigDownDown_count;
  }
  printf("%d\n", (--mp.end()) -> first - mp.begin() -> first);
}

ei1333の日記

ぺこい

Codeforces Round #352 (Div. 2)

A. Summer Camp

問題概要

解法

ソース

B. Different is Good

問題概要

解法

ソース

C. Recycling Bottles

問題概要

解法

ソース

D. Robin Hood

問題概要

解法(ちょっと強引です...)

ソース