体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

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

はじめに

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

【バイバイマン】

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

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

 

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

【問題】

バイバイマンのサイズを整数値で表します。
一番最初の大きさを「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型】
Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!
最初のバイバイマンはサイズが「1」です。これを『A型』のバイバイマンとします。

【B型】
Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!
A型のバイバイマンは次の日にサイズが「2」になります。これを『B型』のバイバイマンとします。

【C型】
Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!
B型のバイバイマンは次の日にサイズが「4」になります。これを『C型』のバイバイマンとします。

【D型】
Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!
C型のバイバイマンは次の日にサイズが「8」になります。これを『D型』のバイバイマンとします。

【E型】
Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!
D型のバイバイマンは次の日にサイズが「16」になり、分裂が起こります。
それぞれのサイズは「1」と「6」ですので、1体はA型で、もう1体は初めて出現します。これを『E型』のバイバイマンとします。

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

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

バイバイマンの発生条件

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

【A型】
Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!
最初から存在するもの以外では、D型とE型が成長し分裂することで出現します。

【B型】
Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!
A型が成長する場合と、E型が成長し分裂する場合に出現します。

【C型】

Ozyさん出題「バイバイマンを数えよう」問題解説と解答コード公開!
B型が成長することで出現します。

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