yukicoder No.141 魔法少女コバ：解法および解答例 - はむ吉（のんびり）の練習ノート

最近yukicoderの問題をあまり解いていなかったので、「おみくじ」機能で表示された（まだ正答していない）★2の問題に取り組むことにしました。この記事では、その一環として今日解いたNo.141 魔法少女コバ - yukicoderという問題の解き方と解答コード例（Python 3およびHaskell）を、覚え書きを兼ねて書きます。

問題の趣旨

数1に対して、以下の操作1および2を繰り返し施し、 $M_0 / N_0$ （ $M_0,N_0$ は互いに素である正の自然数）に変換する。ただし、 $M_0/N_0$ は分数 $M/N\:(M,N\in\mathbb{N}^{+})$ を既約分数にしたものである。この変換に必要な最小の操作回数を $x(\in\mathbb{Z}_{\ge 0})$ とする。入力として $M, N$ が与えられるので、 $x$ を出力せよ。もし1に操作をどのように施しても $M_0 / N_0$ を得られないならば、-1を出力せよ。

操作1: 数 $a$ を $a+1$ に変換する
操作2: 数 $a\:(\ne 0)$ を $1/a$ に変換する

方針

出題された方が書かれた解説にもあるように、一連の操作を逆から行い、操作回数を数えます。すなわち、 $M_0 / N_0$ に対して、それが数1になるまで次の操作1'および2'を繰り返し行い、その際の操作回数を求めれば、それが $x$ となります。また、いくらか実験した結果から、-1が出力となるような $M/N$ はなさそうだと予想しました。

操作1': 数 $a\:(>1)$ を数 $a-1$ に変換する
操作2': 数 $a\:(a>0,\,a<1)$ を $1/a$ に変換する

解法

愚直にシミュレーションする（遅い）

上記の方針に基づき、愚直にシミュレーションを行うPython 3コードを以下に示します。このコードに基づく処理はかなり遅く、手元の環境では、サンプル3に対する処理が制限時間の5秒以内には終わりませんでした。シミュレーションの冗長さだけではなく、分数の表現にfractions.Fractionを使用していることも、遅さの原因であると考えられます。

少し工夫してシミュレーションする（速い）

上のコードでは、数 $a:=m/n\:(>1)$ に対して、ちまちまと1回ずつ操作1'を施していました。しかし、いくつかの具体的な $a$ について実験すればわかるように、 $a$ にもはや操作1'を行えなくなるまでこの操作を行うとき、その回数は $l:=\lfloor (m-1) / n \rfloor$ に等しくなります。また、わざわざfractions.Fractionを使わなくても、2種類の操作を行うことができます。これらを踏まえたPython 3コードを以下に示します。これを提出したところ、無事にAcceptedを得ました。

また、同じ処理をHaskellで書いたものが次のコードです*1。これも同様にAcceptedとなりました。

感想

実は、1-2ヶ月ほど前にもこの問題に取り組みました。しかしながら、そのときには解答の提出に至りませんでした。それは、何かうまい方法があるに違いないと思うあまり、シミュレーションという方法を思いつかなかったためでしょう。鮮やかな方法ばかりを求めるのではなく、素朴な解法も視野に入れるべきであると実感しました。

*1:関数名や変数名に'を用いているためか、シンタックスハイライトが乱れていますが、正常に動作します。