ARC100 参加記録

先日のABC100に続き、ARCも記念すべき100回目。

成績は…130分台2完で349位。Cでドツボにハマったので今回もレート大幅減を覚悟しましたが、最後5分でDが通って本当に良かった…！

f:id:betrue12:20180701235243p:plain

C, Dの2問を振り返っていきます。

C - Linear Approximation

まず、求めたい値は

$|A_{1} - (b+1)| + |A_{2} - (b+2)| + ... + |A_{N} - (b+N)|$

の最小値ですが、このままだと考えにくいので $A_{i} \leftarrow A_{i} - i$ と置き換えてしまいます。これにより求めたい値が

$|A_{1} - b| + |A_{2} - b| + ... + |A_{N} - b|$

の最小値となり、考えやすくなります。

この値を最小にする $b$ は、結論を言ってしまうと（置き換え後の） $A_{1}, A_{2}, ... , A_{N}$ の中央値になります。これを証明してみます。

「差の絶対値の総和」は、数直線上の距離の総和と見なすことができます。数直線を図示します。

要素数が奇数の場合

f:id:betrue12:20180702002648p:plain

要素数が奇数の場合、中央値は順序で見て真ん中の要素の値になります。そのため、「中央値から見て左右にある要素の数は等しい」ということが言えます。

そのため図示したように、 $b$ の値を中央値に近づけると距離総和は小さくなり、遠ざけると大きくなります。また中央値から値を動かすと、必ず距離総和は大きくなります。そのため、 $b$ は中央値に等しい値であることが最適です。

要素数が偶数の場合

f:id:betrue12:20180702003832p:plain

要素数が偶数の場合、順序で見て真ん中の要素が2つあるため、中央値はその2つの平均値と定義されています。

このとき、真ん中の要素2つの間に $b$ があれば、その両側にある要素の数は等しいので、真ん中の要素2つの間からはみ出ない範囲で $b$ を動かしても距離総和は変わりません。それ以外のところに $b$ がある場合は、奇数のときと同じように中央値に近づけるほうがよいです。そのため要素数が偶数の場合は、真ん中の要素2つの間に $b$ があることが最適であり、中央値はもちろんその条件を満たします。

以上より、要素数が奇数・偶数の場合ともに、 $A_{1}, A_{2}, ... , A_{N}$ の中央値に $b$ を取るのが最適となります*1。

実装においては、中央値はソートした後に真ん中の添字を指定して取ってくるのがシンプルです。

ACコード：Submission #2777708 - AtCoder Regular Contest 100

コンテスト本番では中央値ではなく平均値が性質を満たすとずっと思っていて、平均値の周囲を探索するコードを投げまくってWAを量産してしまいました…

D - Equal Cut

数列を4分割し、和の最大値と最小値をなるべく近づけるという問題。部分和の計算は累積和を使えばよいとして、分ける境界が3つもあるので何とかして効率的に探索しなければなりません。 $N \le 2 \times 10^{5}$ なので $O(N^{2})$ 以上は通らず、全探索できるのは1箇所が限界です。

「1個＋3個の境界」「2個＋2個の境界」のどちらかを全探索したくなりますが、1個+3個だと行き詰まります。今回の場合、結果的には2個+2個、つまり真ん中の境界を固定するのが正解です*2。

真ん中の境界を1つに固定して数列を2分割し、それぞれの和を $S_{1}, S_{2}$ とします。2分割した領域それぞれを、さらにどう分けていくのがよいか考えていきます。

f:id:betrue12:20180702220155p:plain

4分割した際のそれぞれの部分和は、非負の整数 $d_{1}, d_{2}$ を用いて

$(S_{1} - d_{1})/2$
$(S_{1} + d_{1})/2$
$(S_{2} - d_{2})/2$
$(S_{2} + d_{2})/2$

と表すことができます。ここで $d_{1}, d_{2}$ は、 $S_{1}, S_{2}$ をさらに分割した時の差であり、0の時に完全な2等分であることを意味します。

そしてこれら4つの部分和の最大値と最小値は、

最大値： $\max( S_{1} + d_{1}, S_{2} + d_{2} )/2$
最小値： $\min( S_{1} - d_{1}, S_{2} - d_{2} )/2$

となります。 $d_{1}, d_{2}$ の値が増えると、最大値は大きくなり最小値は小さくなるので、その差は広がってしまいます。 $d_{1} = d_{2} = 0$ になれば理想です。

もちろん数列の並びによっては、都合よく $d_{1} = d_{2} = 0$ とできないことのほうが多いでしょう。ですが、これらの値をできるだけ小さくするように分割しようという方針が立ちます。

二分探索で解く

「部分和の差を最も小さくするように分割する」ことを効率的に行える1つの方法は二分探索です。例えば $S_{1}$ を分割したそれぞれの部分和を左から $s_{1}, s_{2}$ とすると、最初に $s_{1} \gt s_{2}$ となる境界の中で一番左にあるものは二分探索で求めることができます。

とはいえこれが最適とは限りません。 $s_{1} \le s_{2}$ *3の場合のほうに最適解があるかもしれないからです。この場合、先程とは逆に $s_{1} \le s_{2}$ を満たす中で一番右にある境界を使いたいので、先程求めた境界の1つ左を考えればよいです。これを2通り試して、より差の小さい方を取ります。

f:id:betrue12:20180702231030p:plain

$S_{2}$ についても同じことをすれば、4つの部分和が出揃うので、最大値と最小値の差を取れば「真ん中の境界を1つ固定した時の」最適値が求まります。あとは真ん中の境界を全探索すれば良いです。

二分探索ACコード：Submission #2780112 - AtCoder Regular Contest 100

しゃくとり法で解く

また、しゃくとり法で解くこともできます。節がいっぱいあるので、ちょっと気持ち悪いしゃくとり虫の動きになりますね。

具体的には、

真ん中の境界を、左から1ずつずらしていく。
その真ん中の境界について、 $d_{1}$ が最も小さくなるまで左の境界をずらす。具体的には、「境界を1つ右にずらして $d_{1}$ が改善するならば、1つずらす」を繰り返す。
その真ん中の境界について、 $d_{2}$ が最も小さくなるまで右の境界をずらす。同上。
部分和4つが出揃うので、最大値と最小値の差を計算する。
以降繰り返し。