ARC101 参加記録
水色以上の人にとっては実に1ヶ月以上ぶりのratedコンテストとなりました。そのぶん気合十分、緊張も十分の状態で臨みましたが…
結果は74分台2完で139位。700点問題を解くことができて、レートも結構上がりました。
CとDを振り返っていきます。
C - Candles
解法
ろうそくの消し方は、初期位置（座標0）とろうそくの位置関係によって以下の3パターンに分かれます。
- ろうそくが全部左（0以下）にある。一番左のろうそくまでの片道距離がかかる。
- ろうそくが全部右（0以上）にある。一番右のろうそくまでの片道距離がかかる。
- ろうそくが左右どちらにもある。途中でUターンが必要であり、左右端のうち短いほうへの往復距離と長いほうへの片道距離がかかる。
これらどのパターンにおいても、「連続しないろうそくをわざわざ選ぶ」ことで得になることはないです。イメージとしては、できるだけ密集しているろうそくを選んだほうが得な気がしますよね。
個のろうそくから連続する
個のろうそくを選ぶ選び方は
通り。距離計算に使うのは両端だけなので、1パターンごとの計算は
でできます。全パターン探索しても全体計算量は
、
なので間に合います。
ACコード
- （Ruby） Submission #3072875 - AtCoder Regular Contest 101
- （C++） Submission #3081291 - AtCoder Regular Contest 101
D - Median of Medians
恐怖の700点問題。これはABCに出すには流石に無理がありますね…ただ、知っておいて損はない問題だとは思います。
長さ の数列の連続部分列のとり方は
通りありますが、それら全ての中央値を集めて、さらにその中央値を求める問題。要素数がとても多くなるので、直接求めるのは難しそうです。ちょっと細かく考察を書いていきます。
中央値について考察
「中央値」というのは、要素の個数に直接関係する概念です。例えば
という数列の中央値は4ですが、これは「4以上の要素が半数以上存在する」ということを意味します。
ただ、もちろん1や2についても同様のことが言えますね。「 以上の要素が半数以上存在する」を満たす数はたくさんありますが、そのうち最も大きな
が、（この問題上の定義における）中央値です。これは例えば
のように分布の偏った数列についても同じことが言えます。
平均値と違い、中央値を考える上では「中央値以上かどうか」だけが重要です。
でも、
でも、
でも、
どれも中央値は4です。
Yes/No問題＋二分探索への転換
前項で書いたとおり、「中央値は 以下である」ことと、「
以上の要素が半数以上存在する」ことは同値です。
そして、「整数 が与えられたとき、集合の要素の中に
以上の要素は半数以上存在するか？」というYes/No問題は、直接中央値を求める問題よりもずっと考えやすくなります。というのも、各要素の具体的な値は全部無視して、
以上かどうか、だけで2値化して考えれば良いからです。
このことから、中央値の二分探索を行うという方針が立ちそうです。具体的には、二分探索の各ステップごとに を固定して、先ほどのYes/No問題を解き、その結果に応じて範囲を狭めて求める中央値を特定していく…という方法を考えます。*1
区間数え上げの効率化
さて、元の問題は「 個の連続部分列の中央値
個を集めた集合の中央値を求めよ」でした。
Yes/No問題に切り替えた後は、 個の区間のうち、区間内の要素の中央値が
以上となるような区間の数を数えるのが次の目標になります。そのような区間は、やはり中央値の性質から「区間内に
以上の要素が半数以上あるような区間」と言い換えることができます。
これを全ての区間について直接計算すると結局 以上の時間がかかって間に合わないので、効率化のため累積和を使います。
以上の要素を+1、
未満の要素を-1として累積和を取った時、区間和が0以上であるものが「区間内に
以上の要素が半数以上あるような区間」です。
このように累積和を用いて、区間和がある条件を満たす区間を数え上げる問題はお馴染みです。ただ例えば「区間和がぴったり0」などの条件でしたら*2単純にmapなどで個数管理すればよいのですが、今回は「以上」なので範囲和が必要になります。そのため、BIT（Binary Indexed Tree）などを使うことになります。
BITについては、蟻本の解説、もしくは以下のスライドがオススメです。
http://hos.ac/slides/20140319_bit.pdf
解法まとめ
これで問題を解く全ての材料が揃いました。手順としては、
- 二分探索を試みる。各ステップでは
を固定し、「
個の中央値の中に
- 与えられた数列の、
- 数え上げ結果によってYes/No問題が解かれるので、これを繰り返して二分探索の範囲を狭め、解となる中央値を特定する。
となります。
何と言ってもABCに出たので凶悪難易度に見えますが、700点問題として見ると適正なのかな…と思います。
ACコード
実装上の細かい話ですが、BITは普通は負のインデックスに値を格納できないので、適当にオフセットを付けてやる必要があります。上のコードは0-indexedのBITなので +N してますが、1-indexedのBITだと0を格納しようとしてバグる危険性がちょっとだけあるので、不安なら長さを多めにとって +N+1 しましょう。
また、二分探索は制約範囲内の整数全部を考えても良いのですが、「元の数列に存在する要素のどれかしか中央値になり得ない」ということから、元の数列の要素をソートして候補として使っても良いです。上のコードはそうしています。反復回数がちょっと少なくなると思います。
さいごに
過去にABCで出た700点問題は「考察キツいけど数学で解ける」だったり「考察キツいけどDijkstraで解ける」だったりしたのですが、今回は考察もキツめでBITも必要だったことを考えるとかなり厳しかったのではないかと思います。ARCでもこれが解ければ最遅でも黃パフォだったので、そのくらいのレベルです。
私はこのくらいの難易度の問題を安定させられるようになりつつ、全く歯が立たなかった900点問題に少しでも手がかかるようにしたいな…と思います。ちょっと黄色が見えてきた気がするので、引き続き頑張ります。
