マヨイドーロ問題

最近プログラミングに積極的に手を出しています。

結城先生がCodeIQで1年ぶりに出題するというので、やってみることにしました。

以下は、個人の解法の記録です。特に次のような人におすすめです。

  • プログラミングはまだまだ半人前。
  • C言語を使っている。
  • 多倍長整数演算って何ですか。

次のような方は退屈だと思うので読まないで帰ることをおすすめします。

  • C言語?そんなラテン語みたいな言語には興味ない。
  • 多倍長整数演算なんかパッパと実装できて当然。

問題の概要

​        X
        |
Y - A - B - C - Z

上のような道路がある。XとBの間は一方通行で、XからBにしか出られない。Bに出たあとは、隣の点へ進むか、各点上では向きを反転することができる。なお、最初にBに出たときの向きは、Cに向かう方向である。

最大反転回数Nが与えられたとき、XからYへ至る方法の数Pを出力せよ。

解1

「ああ、これ、苦手なやつだ。」

見た瞬間にそう思いました。いわゆる再帰関数を作る問題だと。

AtCoderでコンテストに参加していていちばん苦手なのがこういうタイプの問題なのです。

文句を言ってないでシミュレートしてみましょう。反転する回数がnのときを考えます。

  1. 現在地がA、B、Cのどこかで、nが0のとき
    もう反転できないので、次の点に進むしかありません。
  2. 現在地がA、B、Cのどこかで、反転した直後のとき
    同じ点で2度反転することはできないので、次の点に進むしかありません。
  3. 現在地がA、B、Cのどこかで、n>0かつ反転直後でないとき
    その点で反転するか、次の点に進むかの2通りが選べます。

これを関数に置き換えてみましょう。Y、A、B、C、Zをそれぞれ0、1、2、3、4に置き換えて、現在地をcur(0≦cur≦4)、向きをZ方向を正としてdir(=±1)とします。あと、反転直後かどうかの情報がいるので、flagが1なら反転直後ということにしましょう。関数は問題の名前にちなんでmayoi(cur, dir, n, flag)とでもしましょうか。

  1. curが0のとき
    Yにたどり着いたので、1を返します。
  2. curが4のとき
    Zにたどり着いてしまったので、0を返します。
  3. curが1~3のどこかで、反転直後またはnが0のとき
    いまは反転できないので次の点に進みます。mayoi(cur+dir,dir,n,0)を返します。
  4. 1.~3.のいずれでもないとき
    curが0か4にならない限り、現在地か現在地から進んだ点で反転することができます。
    mayoi(i,-dir,n-1,1)を足し上げて返します。

mayoi(2,1,n,0)を実行して返ってきた値をS[n]に格納します。N以下の最大奇数をMとして、S[i]i=1,...,Mまで足し上げた値がPですね。

このやり方では、nが小さい順に実行していくと既に数えられたシチュエーションを何度も通って非常に非効率なので、既に数えられたシチュエーションは流用することにしましょう。

Nの範囲が指定されておらず、Sをどれだけ確保すべきかわからなかったので、適当に65536個ぐらいにしておきました。

いやー、関数にmayoiなんて名前つけちゃって、シャレたプログラムができた、提出しちゃいましょう。

テストケース 実行結果 正誤
0 0
1 2
2 2
3 7
4 7
5 20
10 143
50 32951280098
100 5035488507601418375 ×
1000 9897335391534825783 ×
2015 15284611334066302400 ×
73%

…あれ?おっかしいなあ…

解2

10から50の桁数の増え方を見れば、100と1000と2015の桁数はどう考えても異常に少ないので、桁あふれなんだろうなということは容易に想像がつきますね。

上の再帰関数の方法だと、どう考えてもバッファが足りなくなるんですけど…。これ以上は思いつかなかったので、解説を読みました。なるほど、フィボナッチ数列ね。なるほどなるほど。

…多倍長整数のことは何も書いてない!

C言語には標準で多倍長整数を扱う型は用意されていないんですよね。動的リンクを使ってGMPを使う方法はあるにはあるようです。
競技プログラミングにおいて、C/C++/C#/VB/F#/NemerleでGMPを使う – Qiita

しかし、ライブラリを使うのはなんだかなというところもあったので、自分で実装してみることにしました。

  • char型の配列をメンバに持った構造体Numを作ります。配列の長さは適当に調整できるようにマクロで定めておきます。
  • intをNumに変換する関数をNum_initとします。
  • Numどうしの足し算をNum_plusNumとintの足し算をNum_plusiとします。繰り上がりの問題があるので、1の位から順に足していきます。
  • Numを表示するNum_printとします。char型を使うことにしたので、各要素に’0’を足して、先頭の’0’は表示しないようにします。

雑な作りなんですけど、今回はこれでうまくいきました。

テストケース 実行結果
0 0
1 2
2 2
3 7
4 7
5 20
10 143
50 32951280098
100 927372692193078999175
1000 113796925398360272257523782552
224175572745930353730513145086
634176691092536145985470146129
334641866902783673042322088625
863396052888690096969577173696
370562180400527049497109023054
114771394568040040412172632375
2015 244102946831713952672599454699
961270004111993337608531905355
352816811958714295103140794420
687985550594537924317720872252
451688795804691597945441709364
031495408193205108828015735969
079382229228171342887251008176
480474056085002677487667140304
680036502596854064116467872070
970505458020457360209939091542
985982187211119634269938846193
513385776308685107164634235850
209728788191989919712345967336
17320373133963970742975210614208

感想

テストケースの後半、こんなに桁数が増えると思ってませんでした。びっくり。

次があればまた挑戦してみたいですね。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です