マヨイドーロ問題

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

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

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

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

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

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

問題の概要

        X
        |
Y - A - B - C - Z

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

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

解1

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

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

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

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

現在地がA、B、Cのどこかで、nが0のとき
もう反転できないので、次の点に進むしかありません。
現在地がA、B、Cのどこかで、反転した直後のとき
同じ点で2度反転することはできないので、次の点に進むしかありません。
現在地が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)とでもしましょうか。

curが0のとき
Yにたどり着いたので、1を返します。
curが4のとき
Zにたどり着いてしまったので、0を返します。
curが1～3のどこかで、反転直後またはnが0のとき
いまは反転できないので次の点に進みます。mayoi(cur+dir,dir,n,0)を返します。
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が小さい順に実行していくと既に数えられたシチュエーションを何度も通って非常に非効率なので、既に数えられたシチュエーションは流用することにしましょう。

#include <stdio.h>
unsigned long long mayoi(int cur, int dir, int n, int flag);
int doro(int c);

unsigned long long int S[65536];

int main() {
  int i, M, N;
  unsigned long long P=0;

  for (i=0;i<=65535;i++) S[i] = -1;

  scanf("%d%*c", &N);
  if (N%2 == 0) M = N-1;
  else M = N;
  for (i=1;i<=M;i+=2) {
    S[i] = mayoi(2, 1, i, 0);
    P += S[i];
  }

  //  for (i=0;i<=N;i++) printf("%lld\t", S[i]);
  printf("%llu\n", P);

  return 0;
}

unsigned long long mayoi(int cur, int dir, int n, int flag) {
  int i;
  unsigned long long p=0;

  //  printf("mayoi(%d, %d, %d)\n", cur, dir, n, flag);
  if (!cur) return 1;
  else if (cur == 4) return 0;
  else if (!n || flag) return mayoi(cur+dir, dir, n, 0);
  else if (cur == 2 && dir == 1 && flag == 0 && S[n] != -1) return S[n];
  else {
    for (i=cur;doro(i);i+=dir) {
      p += mayoi(i, -1*dir, n-1, 1);
    }
    return p;
  }
}

int doro(int c) {
  if (c>0 && c<4) return 1;
  else return 0;
}

#include <stdio.h>

unsigned long long mayoi(int cur, int dir, int n, int flag);

int doro(int c);

unsigned long long int S[65536];

int main() {

int i, M, N;

unsigned long long P=0;

for (i=0;i<=65535;i++) S[i] = -1;

scanf("%d%*c", &N);

if (N%2 == 0) M = N-1;

else M = N;

for (i=1;i<=M;i+=2) {

S[i] = mayoi(2, 1, i, 0);

P += S[i];

}

// for (i=0;i<=N;i++) printf("%lld\t", S[i]);

printf("%llu\n", P);

return 0;

}

unsigned long long mayoi(int cur, int dir, int n, int flag) {

int i;

unsigned long long p=0;

// printf("mayoi(%d, %d, %d)\n", cur, dir, n, flag);

if (!cur) return 1;

else if (cur == 4) return 0;

else if (!n || flag) return mayoi(cur+dir, dir, n, 0);

else if (cur == 2 && dir == 1 && flag == 0 && S[n] != -1) return S[n];

else {

for (i=cur;doro(i);i+=dir) {

p += mayoi(i, -1*dir, n-1, 1);

}

return p;

}

int doro(int c) {

if (c>0 && c<4) return 1;

else return 0;

}

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_plus、Numとintの足し算をNum_plusiとします。繰り上がりの問題があるので、1の位から順に足していきます。
Numを表示するNum_printとします。char型を使うことにしたので、各要素に’0’を足して、先頭の’0’は表示しないようにします。

#define MAX_LEN 1000

typedef struct {
	char num[MAX_LEN];
} Num;
Num Num_plus(Num A, Num B);
Num Num_plusi(Num A, int B);
Num Num_init(int X);
int Num_print(Num A);

Num Num_plus(Num A, Num B) {
 Num C;
 int i;

 C = Num_init(0);
 for (i=MAX_LEN-1;i>0;i--) {
  C.num[i] += A.num[i]+B.num[i];
  if (C.num[i]>9) {
   C.num[i-1] += C.num[i]/10;
   C.num[i] %= 10;
  }
 }

 return C;
}

Num Num_plusi(Num A, int B) {
 Num C;
 int i;

 C = Num_init(0);
 for (i=MAX_LEN-1;i>0;i--) {
  C.num[i] += A.num[i]+B%10;
  B /= 10;
  if (C.num[i]>9) {
   C.num[i-1] += C.num[i]/10;
   C.num[i] %= 10;
  } else if (C.num[i]<0) {
   C.num[i-1] += C.num[i]/10-1;
   C.num[i] = C.num[i]%10+10;
  }
 }

 return C;
}

Num Num_init(int X) {
 Num C;
 int i;

 for (i=MAX_LEN-1;i>=0;i--) {
  C.num[i] = X % 10;
  X /= 10;
 }

 return C;
}

int Num_print(Num A) {
 Num C;
 int i;

 A = Num_plusi(A, -1);
 for (i=0;i<MAX_LEN;i++) A.num[i] += '0';
 i = strspn(A.num, "0");
 if (i<MAX_LEN) for (;i<MAX_LEN;i++) printf("%c", A.num[i]);
 else printf("0");
 printf("\n");

 return 0;
}

#define MAX_LEN 1000

typedef struct {

char num[MAX_LEN];

} Num;

Num Num_plus(Num A, Num B);

Num Num_plusi(Num A, int B);

Num Num_init(int X);

int Num_print(Num A);

Num Num_plus(Num A, Num B) {

Num C;

int i;

C = Num_init(0);

for (i=MAX_LEN-1;i>0;i--) {

C.num[i] += A.num[i]+B.num[i];

if (C.num[i]>9) {

C.num[i-1] += C.num[i]/10;

C.num[i] %= 10;

}

return C;

}

Num Num_plusi(Num A, int B) {

Num C;

int i;

C = Num_init(0);

for (i=MAX_LEN-1;i>0;i--) {

C.num[i] += A.num[i]+B%10;

B /= 10;

if (C.num[i]>9) {

C.num[i-1] += C.num[i]/10;

C.num[i] %= 10;

} else if (C.num[i]<0) {

C.num[i-1] += C.num[i]/10-1;

C.num[i] = C.num[i]%10+10;

}

return C;

}

Num Num_init(int X) {

Num C;

int i;

for (i=MAX_LEN-1;i>=0;i--) {

C.num[i] = X % 10;

X /= 10;

}

return C;

}

int Num_print(Num A) {

Num C;

int i;

A = Num_plusi(A, -1);

for (i=0;i<MAX_LEN;i++) A.num[i] += '0';

i = strspn(A.num, "0");

if (i<MAX_LEN) for (;i<MAX_LEN;i++) printf("%c", A.num[i]);

else printf("0");

printf("\n");

return 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

感想

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

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

Share on Tumblr

Web being Web

マヨイドーロ問題

問題の概要

解1

解2

感想

関連記事

2024年11月
日	月	火	水	木	金	土
« 1月
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30