読者です 読者をやめる 読者になる 読者になる

はむ吉(のんびり)の練習ノート

主にプログラミングについて、思いついたことや、試してみたこと、学んだことを、覚え書きを兼ねてまとめます。

yukicoder No.141 魔法少女コバ:解法および解答例

プログラミング 競技プログラミング yukicoder

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

問題の趣旨

数1に対して、以下の操作1および2を繰り返し施し、M_0 / N_0M_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
aa+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:関数名や変数名に'を用いているためか、シンタックスハイライトが乱れていますが、正常に動作します。

広告を非表示にする