Mister雑記

競プロやります。

3日目 CFR537 (Div2)

codeforces.com

本番ならB落としてた。CまでとD以降の差が酷くない?

f:id:misteer:20190205002207p:plain


B. Average Superhero Gang Power

Problem - B - Codeforces

概要

長さ Nの数列 \{a_i\}が与えられる。あなたはこの数列に、以下のいずれかの操作を高々 M回行うことができる。

  • 長さが2以上であれば、好きな要素を1つ消す。
  • 好きな要素を1増やす。ただし、1つの要素は高々 K回しか増やせない。

こうして得られた数列の平均値として、考えうる最大値を求めよ。

制約

  •  1 \leq N \leq 10^5
  •  1 \leq K \leq 10^5
  •  1 \leq M \leq 10^7
  •  1 \leq a_i \leq 10^6

解説

「1つになるまで消せるだけ消して、できるだけインクリメント」という貪欲でいけそうに見えるが、これは a_iが全て同じケースに撃墜される1

答えを求めるには、「いくつ減らすか」を全探索する必要がある。減らすのはもちろん小さい方からで、 i個消したときインクリメントは min(M - i, K(N - i))回行える。よって累積和とこの値から総和、及び平均値を求めればいい。


ここまで分かっていたのだが、結局注意力不足で3WAを吐いてしまった。その内容が以下の2つ。

  • 要素を M個以上減らした。
  •  K(N - i)がintに収まらないのに気づかなかった。

故意かは知らないが、罠が多すぎる...。

実装例

本番でバグを一切埋め込まずに実装できた人は本当に凄いと思う。

#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {
    ll n, k, m;
    cin >> n >> k >> m;

    double a[n];
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n, greater<double>());
    for (int i = 1; i < n; ++i) a[i] += a[i - 1];  // 累積和に変換

    double ans = 0;
    for (int i = 0; i <= min(n - 1, m); ++i) {
        // i人を減らす
        double sum = a[n - i - 1];
        sum += min(m - i, k * (n - i));
        ans = max(ans, sum / (n - i));
    }

    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}


C. Creative Snap

Problem - C - Codeforces

概要

※本文をそのまま和訳すると長くなるので、全く別の設定にしています。

同一直線上に並んだ 2^N個の穴があり、いくつかの穴にはゴミが入っている。 i個目のゴミは左から a_i番目の穴に入っている。

あなたは以下のように全ての穴を埋めていくことにした。

  • 最初は全体区間から始める。
  • 今見ている区間に対して、以下のいずれかを適用する。
    1. 長さが等しい2つの区間に分割し、再帰的に埋める。
    2. その区間を埋める。
      • 区間内にゴミが1つもない場合、コスト Aがかかる。
      • ゴミが n個( n \gt 0)あったとき、コスト B \times n \times lがかかる。ここで l区間長。

このとき、全ての穴を埋めるのにかかる最小コストを求めよ。

制約

  •  1 \leq N \leq 30
  •  1 \leq K \leq 10^5
  •  1 \leq A, B \leq 10^4

解説

以降、区間 (l, r]のように半開区間で考えることにする。これは ( l, \frac{l + r}{2}]と (\frac{l + r}{2}, r]のように区間を分割しやすいことと、後述するようにコストを求めやすいことによる。


まず解法だが、問題文にあるまま再帰的に求めれば良い。つまり「分割する場合」と「埋める場合」の両方を試し、安い方を採用するということだ。計算量解析がしにくいのでTLEが不安になるが、ちゃんと空区間をスキップすれば、再帰関数の呼び出し回数は O(NK)に抑えられるはずだ。

問題となるのは、「埋める場合」のコストの算出だろう。「区間 (l, r]に含まれる a_iの数」、言い換えれば「 \{a_i\} r以下の要素数」から「 \{a_i\} l以下の要素数」を引いたものを高速に求める必要がある。

 \{a_i\} r以下の要素数」は二分探索で高速に求められるが、自分で実装しなくてもstd::upper_boundを使うことで

upper_bound(a.begin(), a.end(), r) - a.begin()

のように求められる2。便利。


今回区間を半開区間として扱ったが、基本的に閉区間や開区間より半開区間の方が扱いやすい。というのも、半開区間

  • 区間の分割・マージが楽。
  • 区間和」を求めるのが楽(「 rまでの累積和」から「 lまでの累積和」を引くだけ)。

といった性質を持つからだ。「バグの原因となりやすい \pm 1の調整が出ない」ことも大きい。

実装例

区間の扱いに \pm 1の微調整が一切入っていないのが分かる。これは半開区間だからこそ為せる技である。

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int n, k, a, b;
int p[100010];

ll rec(ll l, ll r) {
    // 区間内のa_iの数
    ll num = upper_bound(p, p + k, r) - upper_bound(p, p + k, l);

    if (num == 0) return a;          // 空区間をスキップ
    if (r - l == 1) return b * num;  // 長さが1のときは、終了しないと無限ループになる

    // 2つの区間に分割
    int m = (l + r) / 2;
    return min(b * num * (r - l), rec(l, m) + rec(m, r));
}

int main() {
    cin >> n >> k >> a >> b;
    for (int i = 0; i < k; ++i) cin >> p[i];
    sort(p, p + k);

    cout << rec(0, 1 << n) << endl;
    return 0;
}


感想

  • std::upper_boundの使い方をまた1つ学んだ。
  • Bをバグなしで通せるようになりたい。
  • D, Eは何。

  1. 本番ではこれがpretestを通ってしまい、こどふぉ春のHack祭りだったらしい(立春だけに)。

  2. ただしaはソート済みとする。