ガジェット通信

見たことのないものを見に行こう

Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!

DATE:
  • ガジェット通信を≫

はじめに

ますは問題のおさらいです。今回の問題は以下のような内容でした。

【バイバイマン】

バイバイマンは1日毎に体の大きさが倍増します。

 

 

また、一定の大きさをこえると分裂します。

【問題】

バイバイマンのサイズを整数値で表します。
一番最初の大きさを「1」とし、1日経つと2倍の「2」、さらに1日後は「4」というように、1日毎に2倍になります。

 

また、バイバイマンは「1」→「2」→「4」→「8」→「16」と、大きさが10を超えたところで分裂します。
分裂後のサイズは、「16」なら「1」と「6」のように10の位の数と1の位の数になります。

分裂したバイバイマンは、再び大きくなります。

 

このようなルールで増えるバイバイマンの数を、1日ごとに調べて、100日目までを出力してください。

【入力】

標準入力から「100」が与えられますが、必ずしも読み込む必要はありません(ハードコーディング可ということです)。

【出力】

標準出力に、1日目から100日目までのバイバイマンの数を出力してください。

例えば20日目までなら、

 

1
1
1
1
2
3
3
3
5
8
9
9
13
21
26
27
35
55
73
80

 

と出力します。

【解答方法】

■挑戦言語は下記のプログラム言語選択で選択可能なものであれば何でもOKです!
1)自分の書いたプログラム言語を選択
2)解答欄にソースコードを記入
3)送信前に「提出前に確認」ボタンをクリック(構文エラーがないかどうかチェックできます)
4)「解答コードは正常に実行されました」というメッセージを確認の上、「解答を送信」ボタンで解答してください。

【採点について】

・採点は「ideone」を使ってプログラムを実行し、標準入力および標準出力のテストケースと照合して正誤を判定します
・各言語の標準入力と標準出力はこちらを参考にしてください
・標準入力の最終行の改行はあり/なし両方に対応してください
※なおCodeIQで使用しているideoneは企業版のため、webで公開されているコンシューマー版ideoneとは
 対応言語・バージョン・挙動が異なる場合があります。
 企業版ideoneの対応バージョンは、「提出前チェック」の結果とともに表示されます。

一般解法編

バイバイマンの数え方

Listのようなデータ構造で素直に実装したいところですが、実際にやってみるとバイバイマンの数は爆発的に増えてしまいます。バイバイマンの種類とその発生条件を確認しておきましょう。

バイバイマンの種類

バイバイマンの大きさはさまざまですが、全部で何種類存在するでしょうか。

【A型】

最初のバイバイマンはサイズが「1」です。これを『A型』のバイバイマンとします。

【B型】

A型のバイバイマンは次の日にサイズが「2」になります。これを『B型』のバイバイマンとします。

【C型】

B型のバイバイマンは次の日にサイズが「4」になります。これを『C型』のバイバイマンとします。

【D型】

C型のバイバイマンは次の日にサイズが「8」になります。これを『D型』のバイバイマンとします。

【E型】

D型のバイバイマンは次の日にサイズが「16」になり、分裂が起こります。
それぞれのサイズは「1」と「6」ですので、1体はA型で、もう1体は初めて出現します。これを『E型』のバイバイマンとします。

E型のバイバイマンは次の日にサイズが「12」になり、分裂が起こります。それぞれのサイズは「1」と「2」ですので、いずれもすでに定義されたバイバイマン(A型とB型)になり、新しいタイプのバイバイマンはこれ以上生まれないことになります。

以上から、バイバイマンは5種類ということが確認できました。

バイバイマンの発生条件

次に、各種バイバイマンの発生条件を確認します。

【A型】

最初から存在するもの以外では、D型とE型が成長し分裂することで出現します。

【B型】

A型が成長する場合と、E型が成長し分裂する場合に出現します。

【C型】


B型が成長することで出現します。

【D型】

C型が成長することで出現します。

【E型】

D型が成長し、分裂することで出現します。

アルゴリズム

バイバイマンの発生条件を元に、疑似コードを書いてみます。
バイバイマンのタイプごとに、日数を添え字とした配列を用意します。

# 1日目はA型1体のみ
A[1] = 1
B[1] = 0
C[1] = 0
D[1] = 0
E[1] = 0
loop {
print A~E[k]の和
if (k = 100) {
break
}
# バイバイマンの発生条件に従って、k日目の状態から(k+1)日目の状態を計算する
A[k+1] = D[k] + E[k]
B[k+1] = A[k] + E[k]
C[k+1] = B[k]
D[k+1] = C[k]
E[k+1] = D[k]
}

簡潔な記述で、高速なコードになります。1日目から順に出力するだけなら、配列を使わず省メモリで書いても良いですね。

コードゴルフ編

一般解法編で説明した方法で十分のように思えるかもしれませんが、コードゴルファーにとって十分ではありません。

ここからは、さらに簡潔に書く方法を簡単に説明します。少し数学の知識が必要になりますが、中学~高校1・2年生程度の知識があれば問題ありません。数学が得意な方にとっては回りくどい説明の箇所もありますが、ご了承ください。

ゴルファー的解法

ある日(k日目)のバイバイマンの数を、型毎に文字で表します。A, B, C, D, E型のバイバイマンの数を、それぞれa, b, c, d, eとすると、(K+1)日目以降のバイバイマンの数は次のように表すことができます。

足し合わせる計算を繰り返しますから、合計を表す式は常に1次式になっています。ここで、A型のバイバイマンについて注目します。

k日目はa体、(k+1)日目は(d+e)体で、(k+5)日目は(a+2d+2e)体です。a+2d+2e = a+2(d+e)ですから、k日目の数と(k+1)日目の数を2倍した数の和と等しいことがわかります。k日目のA型バイバイマンの数をA[k]とすれば、A[k] = A[k-5] + 2A[k-4]のように表すことができます。

また、他の型のバイバイマンについても同じように考えることができます。

A~E型すべてのバイバイマンの数について、同じ形で表すことができるということは、それらを合計した値も、やはり同じように表すことができます。つまり、k日目のバイバイマンの総数をS[k]とすると、S[k] = S[k-5] + 2S[k-4]のように計算できるということになります。

ただし、このような計算方法は単なる1例であって、さまざまな形に変形することができます。もう少し詳しい説明や上記とは異なる式・解法が気になる方は、以下の解説(挑戦者の方々の記事です)を参照してください。

m.ukaiさん
http://d.hatena.ne.jp/m-ukai/20160219
れのあさん
http://renor.hatenablog.jp/entry/2016/02/20/210614
eijitさん
http://qiita.com/eijit/items/36f1a72f10bd8973ef0d
あいべくうさん
http://ibeckuu.hatenablog.com/entry/2016/02/19/011840
angelさん
http://ange1.hateblo.jp/entry/2016/02/18/144326
matarilloさん
https://gist.github.com/matarillo/8c37857f974fd73fec11
Yasu.Hara.さん
http://yas.tea-nifty.com/blog/2016/02/post-8211.html

神コード集

お待たせしました!ここからは、言語別の最短コードをご紹介します。全言語通じて最短コードはなんと『29B』!とんでもない記録になりました。

Perl6(29B)

antimon2さん・rotary-oさん

(1 xx 4,*+*-*+*…7e10)>>.say

両者とも全く同じコードでした。rotary-oさんがコードについてコメントを付けてくださっています。
https://ideone.com/Mnq31t

perl6のバージョンによっては、(1,1,1,1)というリストを(1 xx 4)のように書けない場合もあるようですが、CodeIQの採点システム上では問題内容です。「*」を含んだ部分が少しわかりにくいかもしれませんが、これは

(a, b, c, d, a+b-c+d, … , 7e10)

のように、直前の4要素を用いて再帰的に計算するリストを表しています。先に紹介した計算式とは異なり、S[k] = S[k-4] + S[k-3] – S[k-2] + S[k-1]という形の計算式を用いています。

100日目のバイバイマンは62010148240体ですので、「7e10(70000000000)」という値にはなりませんが、こちらもバージョンによっては7e10を超えない範囲までのリストが得られる場合があります。

さらに、「>>」という演算子(Hyper method call operatorと言います)を用いることで、リストの各要素に「.say」を付加することができます。つまり、コードは

(1.say,1.say,1.say,1.say,2.say,3.say,…)

のように展開されます。sayはprintと異なり、自動的に改行文字が入りますので、リストの各要素を出力し、改行を入れることができます。

Ruby(37B)

chatさん

n=0;100.times{$*

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP