ウクーニャたんお誕生日コンテスト参加記録

ウクーニャたんお誕生日コンテスト - AtCoder

チーム参加OKの非公式コンテスト。ウクーニャたんさん誕生日おめでとうございます！

外出の予定があったので途中からでしたが、ゆかもちさんに急遽お誘いいただき参加しました。ありがとうございました！

f:id:betrue12:20180708131909p:plain

私はBの実装をやりました。2問振り返っていきます。

A - UkuNumber

式の形がフィボナッチ数列によく似ています。実際計算してみると、

$u_{1} = a$
$u_{2} = b$
$u_{3} = a + b$
$u_{4} = a + 2b$
$u_{5} = 2a + 3b$
$u_{6} = 3a + 5b$

と、各項の係数がフィボナッチ数列になっています。具体的にはフィボナッチ数列 $f_{i}$ を1, 1, 2, 3, 5, ... として、 $u_{i+2} = f_{i} * a + f_{i+1} * b$ です。

数列が $X$ を含むような「辞書順最小」のペアを求めるにあたり、 $a = 1$ の解が必ず存在することに気づけるかどうかがカギとなります。例えば $a = 1, b = X - 1$ とすると $u_{3} = X$ となります。また、もっと単純に $a = 1, b = X$ でもいいです。

そのため、 $a \ge 2$ の解は上記のものより必ず辞書順で後ろになるので、 $a = 1$ のものだけを探索すればよいです。

$a = 1$ とすることで、この問題は「 $X = f_{i} + f_{i+1} * b$ となる $i$ が存在するような $b$ の最小値を求めよ」という問題に帰着できます。

あとはどうするかですが、フィボナッチ数を全探索します。 $10^{18}$ という値が恐怖を感じさせますが、フィボナッチ数列の増加スピードも恐怖で、これ以下のフィボナッチ数は87個しかないです。 $X$ は100個ありますが、100回やっても大丈夫です。

ACコード：Submission #2800522 - ウクーニャたんお誕生日コンテスト

（ACコードのリンクは、チームではなく私のアカウントで出したものにしています）

B - Sprinkler

限られたスプリンクラーの操作回数で与える水の合計を最大化したいので、1回1回の効率を最大化するなら、一番広く水を与えられる範囲を選び続ければよさそうです。ただ水を最大に与えてしまった甜菜は範囲に選べなくなるので、「水をあげる」ことがデメリットになるかもしれない、という気も少しだけあります。

以下の図のように考えると、一番広い範囲を選ぶことが得である（少なくとも、損をしない）ことがわかります。つまり、あえて狭い範囲を選んだ時に、「範囲を広く選んだほうが得」または「範囲を広く選んだとしても同じ構造が作れる」のどちらかが言えます。

f:id:betrue12:20180708154730p:plain

というわけで、1回1回の効率を最大化するよう貪欲に範囲を選んでいけばよいです。

また、 $A_{i}$ が大きいので、水やり1回ずつ考えていくのは無理です。その時点での一番広い範囲を決めたら、その範囲で水をあげられるだけあげてしまいましょう。範囲内で残り容量が一番小さいものを探し、その容量だけ水をあげることができます。その後は、残り容量が0になった点で範囲を分割します。

f:id:betrue12:20180708154524p:plain

これを、全部の甜菜の残り容量が0になるか、水やり回数が $M$ に達するまで続けます。

ということで、実装です。以下のことができる必要があります。

貪欲に広いほうから範囲を取るため、範囲たちを管理し、それらを広い順に取り出す。→プライオリティキュー
水をあげられる回数を得るため、範囲の最小値を求める→セグメント木
範囲を分割する点を得るため、最小値を持っている点を求める→後述（※1）
水をあげたということを反映するため、範囲の全ての値から、決まった値を引く→後述（※2）

まず（※1）についてですが、蟻本記載のセグメント木では最小値を求めることはできてもそれがどの点なのかは分かりません。ですが、実は $A_{i} \ne A_{j}$ という条件があるので、インデックス→値の逆写像をmap等で持っておけば最小値→インデックスが得られます。

また（※2）についても蟻本のセグメント木では求められませんが、各区間ごとに「それまで累計いくつ水が与えられたか」の情報を付与しておけば、セグメント木にその情報を入れる必要はありません。

Submission #2800469 - ウクーニャたんお誕生日コンテスト

計算量オーダーですが、区間を1つ処理するごとにどこかの甜菜の残り容量が0になるので、区間を処理する回数は高々 $N$ です。1回の処理につきセグメント木やプライオリティキューの操作で $O(\log N)$ かかるので、全体は $O(N \log N)$ となります。

さいごに

今回はチーム戦ということで、slackのDMで意見交換しながら進めていきました。しっかり作戦を決めて臨んだわけではないので緩い感じでしたが、1人ではなかなか気づけないコーナーケースや考察ミスが早く発覚したり、問題の分担を考えたり、ソロとはやっぱり感覚が違うなと思いました。チームプレイをしっかり回すのは難しいんだろうな、とも。

デバッグに関しては、やっぱり言語が揃っていたほうが良いのかなという気もしました…

何はともあれ、2完はけっこう上出来なんじゃないかと思います。ゆかもちさんありがとうございました！