今回の活動はC++講習会とバーチャルコンテストを行いました。

C++講習会

C++講習会では AtCoder Programming Guide for beginners (APG4b) の内容にそって解説を行う予定です。
第1回では1章の1.01～1.07のif文までとfor文について解説しました。

コンテスト

コンテストのリンクはこちら

• YNU CPC 2019 VC 003 A for Beginners
• YNU CPC 2019 VC 003 A

いくつかの問題について解説します。

ABC073 B - Theater

https://atcoder.jp/contests/abc073/tasks/abc073_b

問題概要

劇場に席 $1$ から 席 $100000$ までの $100000$ 個の積があります。
$N$ 組の団体が来て、 $i$ 番目の団体は席 $l_i$ から 席 $r_i$ までの連続した席に座っています。
今、劇場の席には何人座っているか求めてください。

制約

• $1 \le N \le 1000$
• $1 \le l_i \le r_i \le 100000$
• 同じ席に複数人が座ることはない

解説

$i$ 番目の団体は席 $l_i$ から 席 $r_i$ までの連続した席に座っているので、人数は $r_i - l_i + 1$ と求まります。
同じ席に複数人座ったりすることはないので各団体の人数の総和が答えになります。

よって、 $\sum_{i=1}^{N} (r_i - l_i + 1)$ が答えです。

コード例

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0;
    cin >> n;
    for(int i=0; i<n; i++){
        int l, r;
        cin >> l >> r;
        sum += (r-l+1);
    }
    cout << sum << endl;
    return 0;
}

ABC100 C - Linear Approximation

https://atcoder.jp/contests/arc100/tasks/arc100_a

問題概要

長さ $N$ の数列 $A$ があります。
ある整数 $b$ を適切に選んだとき、次式の最小値を求めてください。
ただし $abs(x)$ は $x$ の絶対値を返す関数です。

$abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + … + abs(A_N - (b+N))$

制約

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^5$

解説

$B_i = A_i - i$ とおくと、自由に $b$ を選んだときの $abs(B_i - b)$ の総和を最小化する問題と置き換えられます。

このとき、$b$ を $B_i$ の中央値にしたとき最小値をとることが分かります。

いま $b$ を適当に選んで $B_i \le b$ なる $B_i$ が $K$ 個 であるとします。
ここで $b$ を $1$ だけ増加させることを考えます。絶対値の変化は

• $B_i \le b$ の $K$ 個については遠ざかるのでそれぞれ $+1$
• $B_i > b$ の $N-K$ 個については近づくのでそれぞれ $-1$

となるので、全体では $2K - N$ 変化します。

よって $K < N/2$ であるとき $b$ を増加させればさせるほど $abs(B_i - b)$ の総和は減少します。
また、$K = N/2$ のとき変化は $0$ となり、$K > N/2$ では $b$ を増加させるほど絶対値の総和は単調に増加します。

以上より $b \le B_i$ となる $B_i$ が $K=N/2$ 個のとき最小値をとることが分かり、これは $b$ が $B_i$ の中央値のときです。
$b$ を減少させるように考えたときも同様の結果になります。

プログラムでは $A_i - i$ の中央値を求め、絶対値の和を求めていけばよいです。

コード例

sort() は #include <algorithm>
abs() は #include <cmath>
を書くと使用できるようになります。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    long long int n, a[200000], b[200000], mid, sum = 0;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    for(int i=0; i<n; i++){
        b[i] = a[i] - (i+1);
    }
    // ソートして中央値を求める
    sort(b, b+n);
    med = b[n/2];

    for(int i=0; i<n; i++){
        sum += abs(b[i] - med);
    }
    cout << sum << endl;
    return 0;
}