Mujin Programming Challenge 2017 - A - Robot Racing - Senの競技プログラミング備忘録

概要

数直線上にN匹のカエルがいて、それぞれx_i(>0)にいる。次の操作を、カエルが残ってる限り好きな回数行える。

数直線上にいる任意のカエルがx_iにいるとき、それを選んで、(x_i)-1 or (x_i)-2に動かす。ただし、動かす先に別のカエルがいる場合はその動かし方をしてはならない。また、動いた先の座標が0以下ならば、そのカエルは「ゴールした」とみなし、数直線から取り除かれる。

カエルのゴールする順番としてありうる通りの数を答えよ。

制約： 1 <= N <= 10^5, 0 < x_1 < x_2 < ... < x_N

ACするまで

1. 最初の状態でゴールできないカエルは、ジャンプしてる道中で、ほかのカエルによって道をふさがれている、つまり2つ連続になってるとわかる。
2. 連続してると、基本的に道をふさぐが、数直線の負の向きで十分に距離があるのならば、連続してるカエルたちを1つ空きにして、連続してるところから左を数直線の負の向きに近づければ、通れる場合はある(このステップで連続してる列の中での順番の入れ替えもできそう)
3. 実験をしてみると、i番目(0-idx)(i>= 1の時)のカエルがそのままゴールインできる条件として、x[i - 1] >= 2 * i - 1であるとわかる。(理由は後述)
4. これでひとまず、部分点での判定方法が分かる。
5. 答え自体は、サンプルから見てわかる通り合成数っぽいので、なにかしらの積であると見当はつく。~~サンプルエスパーはよくない。~~
6. 手元で実験してみると、一度道をふさがれてると、それより右のカエルはたとえどれほどの距離が離れていようとも、ほかのカエルを出し抜いてゴールインすることができない。逆に言うと、ふさがってる場所があるのならば、その時点でゴールインできるカエルは、前から見たいくつかに限られる、とわかる。
7. もう少し考察すると、6のように決定される段階で、そのうちの1つのカエルをゴールインさせれば、道のふさがりがいったん解消するとわかる。
8. ここまでくれば、もう簡単。前から順に道のふさがりが出てきたらカエルを1つ選んでゴールインさせて、最後に残ったカエル同士では任意に並べていい。->AC!

考察

部分点解法については、全探索をすればいいが、「その順番にゴールできるか？」をどう判定すればいいのか？が部分点解法のネックとなる。
実験をしてみると、できるだけ着目してるカエルより前のカエルを、1つ空きしたうえでできるだけ左詰めするのが最善であるとわかる。図にすると、

カエルが存在するのを'o', しないのを'x'とする。
xxoxxxooxoxxoo
oxoxoxoxoxxxxx
このような左詰めは必ずできる。

このように左詰めができる状態は、数式にすると、
i番目(0-idx, i >= 1のみを考える。0番目は必ずできるので、考えないこととする) $x_{i-1} >= 2i-1$
を満たせばゴールできる。この式は、「数直線上にいる0番目のカエルから、今着目してるカエルより1つ前のカエルまで、"oxoxox..."のようにできるだけ左詰めできるか？」を示してる。これを満たさないと、左詰めの家庭のどこかで必ずカエルが連続する場所が現れ、結局そこで今着目してるカエルが進めなくなる。

上の判定法をもって考えれば、部分点は獲得できる。

満点解法については、これをさらに掘り下げていく。

ひとまず、最初のN個のカエルのうち、最初にゴールできるカエルはどのように分布されるかを考える。

実は、これはある場所を境にゴールできる or できないが分かれる。なぜならば、境となる場所でいわゆるそれより後ろのカエルが「詰まる」(他のカエルをゴールさせずに、自分だけゴールするのはできない)ので、たとえ後ろでどれだけ空白の余裕があろうとも、1か所詰まってしまえば、自分より前のカエルのゴールなしに自分がゴールインできないからである。

言い換えれば、「詰り」が発生した時、その状況でゴールインできるカエルというのはすでに限られている、といえる。

ここからカエルたちをゴールインさせるにあたってやるべきことは、ゴールインできるカエルたちを必要最低限の、「詰まり」を解消するに足りるぶんだけ、ひとまずゴールインさせることである。必要最低限の数をゴールさせる(A)と、「詰り」がないという状況にまた戻るので、それから次を考えればに進めればよい。
そして、最後に「詰り」解消のためにすでに使ったカエル以外は、自由な順番でゴールできるため、残ったカエルの階乗を掛ければよい。(B)
この時、回答は(A)と(B)の両パートから成る。

(A)では、いくつかのゴールできるものから、1つを選びゴールさせる。k個の候補があるとして、そのk個のどれを選んでも、「詰り」解消の働きは同じ(後述)なので、答えはk倍になる。
(B)では、全部のカエルのうち、(A)で使われたものを除けば、それらはすべて任意の順序で自由にゴール可能とわかるので(「詰り」をできるだけ解消するようにしてるので)、s個あるとしてs!倍となる。

さて、「詰り」解消の効果を考える。
まず、 $x_{i-1} >= 2i-1$ の式で、 $x_i >= x_{i-1}+1$ なので、 $i=i+1$ としたときに、(左辺)の最低増分は1である。一方、(右辺)は2なので、(左辺)-(右辺)は1回で-1まで減る。
ここで、実は前にあるカエルが1つ少なかったとすると、"ox"のセットを1つなくせるので、右辺が2減り、(左辺)-(右辺)は2増加する。
ここの考察から、「詰り」解消には、カエルを取り除くのは1回しかやらなくていいし、1回さえやれば、操作後にまた「詰まる」ことはない、とわかる。