AtCoder ABC101C Minimization

 

C - Minimization

前置きと内容説明

自分がコンテスト中に解けなかった問題です。この問題について「問題概要及び制約」「コンテスト中の自分の考察」「解法」「数列の順序が解に影響がないことについて」「反省」をまとめていこうと思います。

問題概要

1からNを並び変えた数列が与えられる。以下の操作を最小回数繰り返し、数列の全ての要素を等しくせよ。

・連続するK個の区間を選択し、その区間の全ての数を区間内の最小値に置き換える。

制約　2 ≦ K ≦ N ≦ 100000

コンテスト中の自分の考察

実験しました。

こんな感じの絵をたくさん書きました。

この結果わかったこと。

・最後は全て１になる。

・操作は１を含まない範囲で行ってはならない（回数の無駄になるので）

・１以外の数字の順番は解答には関係がない。

・１がどこにあったとしても、操作の順番を変るだけで全ての要素を１にすることができる。

（詳細、数列の順序が解に関係ないことにて後述）

・１の場所も解答には関係がないのでは？

ここでKとNでサンプルを見ながらエスパーを始めます（敗因）。

N/(K-1)が見えます。投げます。WA。

上記の絵をたくさん書いた結果、K=２の時、上記の式に合わないことがわかりました。そんなコーナーケースあるわけない、と思い実験をたくさんしました。なぜかN＝２以外では上記の式に当てはまってしまいます（敗因２）。N＝２をコーナーケースとした解答を投げます。２WA。

諦めました。

解法

数列の順序は解に関係がないです。これについては後述。

上で乗せた図をもう一度乗せます。

全ての矢印で覆っている部分をX、矢印の数をGとします。初めに、１を含む連続するK個の部分に矢印を置くと、矢印で覆っている部分はK個になります。この操作以降、矢印の末端同士が重なるように矢印を置いていかなければならないので、Kー1個ずつ矢印の覆っている部分が増加していきます。よって、矢印をG個置いた時、全ての矢印で覆っている部分Xは、

X=K+(G-1)(K-1)

と書けます。よって、N≦Xとなれば良いので、

N≦K+(G-1)(K-1)

となるGの最小値が答えです。　

数列の順序が最小回数に影響がないことについて

（何回出すんやこの図）

「コンテスト中の自分の考察」で出てきた

・１がどこにあったとしても、操作の順番を変えるだけで全ての要素を１にすることができる。

について説明します。

数列の左端を１番目とし、矢印の左端を数列のa番目、右端をb番目に置くことを(a,b)と書くことにします。現在、３番目に１があり、(2,4)(1,3)(4,6)(6,8)と矢印を置いていくことで、題意をみたすことができました。ここで１番目に１を置いた時のことを考えましょう。この時、(1,3)(2,4)(4,6)(6,8)という上記の操作の順番を並び替えただけで、数列の全ての要素を１に変えることができました。この実験により、ある特定の並びでの最小回数がG回の時、他の並びでもG回で全ての要素が１に入れ替えることができると言えそうです。（もっと厳密な証明方法があると思いますが、これである程度納得出来るかと思います。）このことを認めて議論を進めます。

ある並びでの最小回数G回で、他の並びでも全ての要素が１に出来るからといって、それが最小回数であるということは示されていません。このことを簡単な背理法で示します。

任意のNとKについて題意をみたす最小回数が並び方によって異なると仮定します。

全ての並び方の中に、最も小さい最小回数を持つ並び方は必ずあります。この並びをAとして、その回数をa回とします。また、違う並び方で最小回数がAより大きい並び方も必ず存在します。この並びをBとし、この時の最小回数をb回とします。よって

a < b

が成り立ちます。しかし、ある並びにおいて成り立った最小回数で、他の並びでも全ての数列の要素を１に出来ると認めています。つまり、数列Aでの最小回数a回で、数列Bも全ての要素を１に出来ます。なので、

a=b

が成り立ちます。

しかし、これは前述のa<bに矛盾します。よって最初の仮定は間違っており、任意のNとKについて最小回数は並び方によって変わらないことが示されました。

反省

・なぜあの図が書けていて、数式立てれなかった。

・エスパーしない。

・論理に基づいて計算式を立てる。

※6月26日(火)

誤字修正