ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

ARC100 参加記録

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

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

f:id:betrue12:20180701235243p:plain

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

C - Linear Approximation

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

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

のような流れになります。

このとき、左右の境界の最適な位置は単調性がある、つまり後戻りすることがありません。この理由は直感的には以下のように説明できます。

例えば左半分を考えると、真ん中の境界を右にずらすごとに、右側の要素がどんどん増えていきます。それをほぼ半分に分ける境界も、右に右にずれていくはずです。

右半分についても、真ん中の境界を右にずらすと左側の要素が減るので、半分に分ける境界も右にずれていくはずです。

厳密には不等式をこねくり回すと多分示せます。(雑)

しゃくとり法ACコード:Submission #2780125 - AtCoder Regular Contest 100

さいごに

前回に引き続き、C問題でハマってしまいました…最近は600~800点くらいの問題を少しずつ進めていましたが、300~400点くらいの問題を少し復習したほうがいいのかなあ、とも思ったり。

次のratedコンテストは、レート2000未満の人にとってはSoundHoundコンテストになりますね。社会人対象オンサイトコンテストの予選ということで、ほんの少しだけ本選出場の望みも持ちつつ、レートも上げられるように頑張りたいです。

脚注

*1:今回は「bの値を動かすとどうなる」ということだけで説明しました。数学的に言うと、凸性から局所最適=全体最適だということを使うとスマートだと思います。

*2:このへんの判断は難しいですが、「どれかの値を固定するときに、問題が対称になるようにする」という考え方は役立つ場面が多いように思います。他には例えばARC084-C「Snuke Festival」など。

*3:等号はどちらにあっても良いです。