little star's memory

競プロの参加記など

yukicoder No.1286 Stone Skipping

yukicoderで初めてwriterをしました!作成した問題はこちらです。

yukicoder.me

この記事ではこの問題に関する裏話的なことを書いていこうと思います。

問題ができるまで

作問には大きく分けて「問題から作る」「解法から作る」の2種類があると思いますが、今回は前者でした。石を投げる遊びのことをぼんやり考えていたら生まれた気がします。こうして問題文ができました。実際に解いてみると、問題からは想像していなかったテクニックが出てきて面白かったです。

yukicoder上で問題文・解説・テストケースを作成しました。テストケースづくりには一部苦労したところがありますが、それについては下の方で書きます。一通り完成した後、テスターを募集しました。テスターを引き受けてくださった方は、かなり丁寧に作業してくださったのでとても感謝しています。問題文やテストケースの改善を行うことができました。

想定誤解法とテストケースづくり

サンプル3を見ると、答えとD/2がかなり近いように見えます。答えがD/2以上であることは、$x+\frac{x}{2}+\frac{x}{4}+\cdots=2x$であることからわかります。答えがD/2に十分近いと予想して、D/2から順番に試していくという方法が考えられます。

作問した当初はこの解法を別解にしていましたが、本当に成り立つのだろうか?と思い検証することにしました。すると、答えとD/2との差は大抵の場合小さいのですが、まれに大きくなることがわかりました。この解法は成り立たないかも、と思いましたが、実際にこの解法を落とすためには答えとD/2との差がかなり大きくなるようなケースを見つけなければなりません。うまい構成方法が思いつかなかったのでひたすらランダムに探索しました。こうして見つかったのがD=562021979554812640です(テストケース05_hand_7)。答えとD/2との差が261711887になります。上の解法では、高速な言語でも5秒ほどかかるはずです。こうして、上の解法を落とすテストケースができました。提出を見てみるとかなりの数がこのケースで落ちていますね。

別解

想定解は解説に書いた通りですが、提出を眺めていると想定解と異なる方法で解いている人も見つかりました。発見した別解をまとめます。勉強になりました。

その1

跳ね返る回数$K$を固定し、最初の飛距離を$x$とします。総飛距離は$f(x)=x+\left\lfloor\frac{x}{2}\right\rfloor+\left\lfloor\frac{x}{4}\right\rfloor+\cdots+\left\lfloor\frac{x}{2 ^ K}\right\rfloor$です。床関数を外して評価すると、$f(x)\le x+\frac{x}{2}+\cdots+\frac{x}{2 ^ K}=2x\left(1-\left(\frac12\right)^{K+1}\right)$、および$f(x)\ge x+\left(\frac{x}{2}-1\right)+\cdots+\left(\frac{x}{2 ^ K}-1\right)=2x\left(1-\left(\frac12\right)^{K+1}\right)-K$となります。$f(x)=D$とすると、$\frac{D}{2\left(1-\left(\frac12\right)^{K+1}\right)}\le x\le \frac{D+K}{2\left(1-\left(\frac12\right)^{K+1}\right)}$となります。この範囲は十分小さいので全部調べても間に合います。

その2

こちらも$K$を固定して、$f(x)=D$をみたす$x$を求めます。$x$のどのビットを立てるかを考えます。$x$にビットを立てる($2 ^ i$を加える)と、$f(x)$の値は$2 ^ i+2 ^ {i-1}+\ldots+2 ^ {i-K}$増加します。上位ビットからビットを立てるか立てないかを選んでいくことで、$f(x)=D$をみたす$x$を構成します。

最後に

テスターの方、解いてくださった方、yukicoder運営の方、ありがとうございました。機会があればまた作問をしたいと思っています。次はコンテストを開きたい!