Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ARC100 (ABC102) 解説

いつもよりちょっとだけ早かった1週間振りのABC/ARC。 配点は先週同様violence、果たしてMisterの人権やいかに......?

まぁ言ってしまうとC, Dの2完だったのでいつも通りA〜Dの4問を解説します。

目次

本編

A - Multiple of 2 and N

概要

問題リンク

 2 Nのどちらでも割り切れる最小の正整数を出力せよ。

制約

  •  1 \leq N \leq 10^{9}

解説

まず Nで割り切れるという条件の時点で答えは Nの倍数となる。

よって答えの最小値は Nなわけで、 N 2で割り切れる場合(つまり Nが偶数の場合)はそれが答えになる。

一方奇数の場合はより小さい値を掛けて偶数にしたいわけだから、 2を掛けて 2Nが答えとなる。

回答例

#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    if (N % 2 == 0) {
        // Nが偶数の場合はNが答え
        cout << N << endl;
    } else {
        // Nが奇数の場合は2Nが答え
        cout << N * 2 << endl;
    }
    return 0;
}

ちなみに今後はA,B問題に関しては、define系のマクロを一切使わないコードを載せることにする。

B - Maximum Difference

概要

問題リンク

長さ Nの数列 Aが与えられる。 Aの異なる2要素の差で、絶対値が最大のものを求めよ。

制約

  •  2 \leq N \leq 100
  •  1 \leq A_i \leq 10^{9}

解説

2要素の絶対値が最大となるのは、 A中の最大値と最小値を取ったときになる。よって Aの最大値と最小値を求めればその差が答えとなるわけだが、これは

  • 最大値と最小値を更新していく
  • ソートして先頭と末尾の要素を取る

の2つの方法が主に考えられる。計算量を比較すると前者は O(N)、後者は O(N \log N)で後者の方が若干遅いが、どちらにせよ余裕で通るので問題ない1

回答例その1: 最大値と最小値の更新

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    int ma = 0, mi = 1e9 + 10;
    // maが最大値、miが最小値
    
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;
        
        // 最大値、最小値を更新
        ma = max(ma, A);
        mi = min(mi, A);
    }
    cout << ma - mi << endl;
    return 0;
}

制約から最大値は0以上、最小値は 10^{9}以下と確定しているので上のような初期値で問題ない。ただし最小値の初期値を 10^{10}とかにするとint型ではオーバーフローを起こすので注意。

なおmaxminはalgorithmライブラリに入っているのでわざわざ実装する必要はない。

回答例その2: ソート

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<int> A(N);
    // 入力を記録する配列
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    sort(A.begin(), A.end());
    // Aを昇順にソート
    
    cout << A.back() - A.front() << endl;
    // A.back()でAの末尾、A.front()でAの先頭が取り出せる
    
    return 0;
}

vectorは言うなれば「長さを変えられる配列」で、配列の上位互換と言っても過言ではない(果たしてそうでしょうか)。B問題レベルではvectorはまだ難しいかもしれないが、D問題以降では使用頻度が格段に増すので今のうちに使えるようになっておくと後々有利。Google先生を頼っていこう。

なおsortもalgorithmライブラリに入っていて、引数にイテレータを渡すことで範囲を指定する。第3引数に関数を渡せば並び替え方の指定も出来たりしてとても便利。

C - Linear Approximation

概要

問題リンク

長さ Nの数列 Aが与えられる。 bに対して「悲しさ」 s(b) \displaystyle
s(b) = \sum_{i=1}^{N} \left| A_i - (b + i) \right|
によって定めたとき、悲しさの最小値を求めよ。

制約

  •  1 \leq N \leq 2 \times 10^{5}
  •  1 \leq A_i \leq 10^{9}

解説

 s(b) A_iのindex2に依存しているが、上の定義式は書き直すと  \displaystyle
s(b) = \sum_{i=1}^{N} \left| (A_i - i) - b \right|
となるため、 B_i = A_i - iなる数列 Bを新たに作れば  \displaystyle
s(b) = \sum_{i=1}^{N} \left| B_i - b \right|
となり、indexに依存しない形になる。これでソートなどの順番を変える操作も行えるようになるので、以降 Bソート済みとする。

あとはこの「各要素の bからの距離」の総和を最小化したいわけだが、ここで Bの各値を二次元平面にプロットしてみる。横軸を i、縦軸を B_iとすると、以下のような具合になる。

f:id:misteer:20180702204749j:plain

さて、 bが上のように B_k B_{k+1}の間にあるとき、 bを1増やすと s(b)はどれだけ変化するだろうか?

f:id:misteer:20180702204806j:plain

結果は上のように、

  •  i \in [1, k]については距離が1増加
  •  i \in [k + 1, N]については距離が1減少

となるため、 s(b+1) - s(b) = k - (N - k)となる。ここで d(k) = 2k - Nとしておこう。

 k \dfrac{N}{2}前後で場合分けすると以下のようになる。

 k \lt \dfrac{N}{2}  k \gt \dfrac{N}{2}
 d(k) \lt 0  d(k) \gt 0
 s(b+1) \lt s(b)  s(b+1) \gt s(b)
 bを増やした方が得  bを減らした方が得

ここから k \fallingdotseq \dfrac{N}{2} s(b)が最小になることが分かるが、厳密にはどうなるだろうか。これは Nが偶数のケースと奇数のケースで場合分けする必要があるが、結論だけ言うと3どちらの場合も b = B_{\frac{N + 1}{2}}で最小となる(分数は切り捨て)。あとはこのときの s(b)を実際に計算すればACとなる。

計算量はソートがボトルネックとなり O(N \log N) O(N)中央値を出すアルゴリズムもあるらしいが、そこまでする必要はないだろう。

回答例

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define NREP(i, n) FOR(i, 1, n + 1)
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ---------- */

int main() {
    ll N;
    cin >> N;
    
    V<ll> B(N + 1);
    // 入力ではなく、上で変換したBの方を記録(1-indexed)
    
    NREP(i, N) {
        ll A;
        cin >> A;
        B[i] -= A - i;
    }

    sort(B.begin() + 1, B.end());
    // B[0]はソート対象外
    
    ll b = B[(N + 1) / 2];
    // Bの中央値がbの最適値

    ll ans = 0;
    NREP(i, N) {
        ans += abs(B[i] - b);
    }

    cout << ans << endl;
    return 0;
}

分かってしまえば実装はさして苦でもない。0-indexedの場合はb = B[N / 2]で通るはず(私は本番そっちでやったので)。

別解1: 三分探索

先に上げた表を基準に s(b)のグラフを書いてみると、これは下に凸のグラフになっていることが分かる。こういった「凸性があるグラフについて極値を求めたい」というときに使えるのが「三分探索」というアルゴリズムである。ここでは詳しく解説しないが、興味がある方は調べてみるといいだろう。

このアルゴリズムを使う問題を1つ載せておく(ネタバレになるので問題名は伏せておく)。実のところ数学でも殴れる。

ちなみにこの解法でも探索で使う値を求めるのに O(N)、探索は二分探索同様 O(\log N)かかるので全体計算量は O(N \log N)となり、上の解法と同じになる。

別解2: 累積和

「最適な b B_1 \sim B_Nのどれかだろう」と目星をつければ、累積和を利用することで全探索が可能。具体的には b = B_kの場合 
s(B_k) = ((sum_N - sum_k) - (N - k)B_k) + ((k - 1)B_k - sum_{k - 1})

となる。ただし Bはソート済み、 sum_i = B_1 + \dots + B_iとする。

計算量は多少多いが問題となるレベルではないし、十分現実的な解法である。

D - Equal Cut

概要

長さ Nの数列 Aを3箇所で切って出来た4つの空でない数列について、それぞれの総和を P, Q, R, Sとする。このとき、「 P, Q, R, Sの最大値と最長値の差」の最小値を求めよ。

制約

  •  4 \leq N \leq 2 \times 10^{5}
  •  1 \leq A_i \leq 10^{9}

解説

まず何となく「 P, Q, R, S Aの総和を大体4等分するんだろうな〜」と考えて、

  • 和が Aの総和の1/4になるまで数列を伸ばして、超えたらその前後で切る

みたいな解法を思いつく。しかしそれではサンプルにあるケースがどうにも上手くいかないことに気づき、ここで行き詰まる。

次に注目したのが問題文。いわゆるメタ解きというやつ。

  • なぜカット数は変数ではなく3で固定なのか?
  •  Nの制約的に解法は O(N \log N)くらいだろう

の2点に注目した結果、

  1. まず Aの2つの切り方を全探索する。
  2. 各パートについて、なるべく2等分するような切断位置を二分探索で探す。

という解法に至った。これなら O(N \log N)で間に合うし、 先程考えた解法は4つだと上手くいかないが2つなら上手くいくことも証明できる4のでここで実装に移る。

二分探索する上でカットしたときの数列の区間和を O(1)で求める必要があるが、これは累積和を作っておけば大丈夫。

あと注意点として、数列をなるべく均等に2つに切ったときのそれぞれの和を前から P, Qとしたとき、  P \leq Q P \gt Qの2パターンを考える必要がある。 これは二分探索で境界となった値をどっちに入れるかを実際に試せばいい。

回答例

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;
template <typename T>
using V = vector<T>;
template <typename S, typename T>
using P = pair<S, T>;
using ll = long long;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define NREP(i, n) FOR(i, 1, n + 1)
// Natural REP runs from 1 to n 

/* ---------- ここまでマクロ ----------- */

ll N;
V<ll> A(200010), sum(200010, 0);


// 閉区間[b, e]をできるだけ均等に2等分したときの、
// 各配列の総和をペアで返す
P<ll, ll> divide(ll b, ll e) {
    ll ok = b, ng = e;
    ll ds = sum[e] - sum[b - 1];

    // 二分探索で[b, ok]の和が[b, e]の半分以下になる最大のokを探す
    while (ng - ok > 1) {
        ll mid = (ok + ng) / 2;
        ll ps = sum[mid] - sum[b - 1];
        if (ps * 2 <= ds) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    // P <= Qの場合
    P<ll, ll> ret1 = make_pair(sum[ok] - sum[b - 1], sum[e] - sum[ok]);
    // P > Qの場合
    P<ll, ll> ret2 = make_pair(sum[ok + 1] - sum[b - 1], sum[e] - sum[ok + 1]);
    
    // 両者を比較
    if (ret1.first - ret1.second > ret2.second - ret2.first) {
        return ret1;
    } else {
        return ret2;
    }
}


// [0, itr)と[itr, N)に分割したときの最適解
ll cut(ll itr) {
    V<P<ll, ll>> psum(2);
    
    psum[0] = divide(1, itr);        // (P, Q)
    psum[1] = divide(itr + 1, N);    // (R, S)

    V<ll> elem;    // [P, Q, R, S]
    
    for (auto p : psum) {
        elem.push_back(p.first);
        elem.push_back(p.second);
    }

    sort(elem.begin(), elem.end());
    return elem.back() - elem.front();
    // 最大値と最小値の差を返す(B問題その2を参照)
}


int main() {
    cin >> N;
    NREP(i, N) {
        cin >> A[i];
        sum[i] = sum[i - 1] + A[i];
        // 同時に累積和も計算
    }

    ll ans = sum[N];

    FOR(i, 2, N - 1) {
        // 全ての2分割を試す(ただし分割後の要素数>=2)
        ans = min(ans, cut(i));
    }

    cout << ans << endl;
    return 0;
}

もう少しキレイに実装したいな〜という感じ。ちなみに上のコードをそのまま投げると通る。

確かに実装は重いが、「こどふぉに比べればマシか...」とか思いながら実装していた。バグがほとんど生まれなかったのはこどふぉ様々だろうか。

別解?: 尺取り法

別解というよりこちらがEditorialに載っていた解法なので上が別解なのだが、二分探索の部分は尺取り法で代用できる。 というのも2つに切ったあとでさらに2つに切るとき、切るべき位置は単調性があるため前回切った位置を覚えておけば続きから探索できるからだ。 この解法は O(N)で、上の方法より僅かだが速い。

この問題に限った話ではなく、累積和で境界を探す問題のときはにぶたんと尺取り法がどちらも使えることが多い。 尺取り法の方が \logの分だけ速いが例によって大した問題にはならないので、どちらを使うかはお好みで。

感想

前回D500が解けなかった翌週で今回D600と知ったときには死を悟ったが、なんとかなって助かった。 欲を言えばE700も解きたかったが、良い解法が浮かばず。パフォは2000乗ったので上々といったところか。

それにしても先週は学問と競プロに対するモチベが尋常じゃなく低かった。 睡眠不足か、栄養不足か、はたまたストレスか。分からん。


  1. そもそも競技プログラミングにおいて計算量 \logの差が致命的になることはほとんどないので、定数倍程度に思っていい。

  2. 数列中での位置。要素を A_iと表記したときの iのこと。

  3. ここに書いても助長な感じがしたので省きました。詳しい証明はHackMD版を見てください。

  4. 証明と言えるほど堅いものではないが、まぁ任意のケースでより優れてることを言うだけ。ちなみに A_i \leq 0の場合は成り立たない。その場合は O(N^{3})でしか解けないんじゃないかね。