本稿はCodeIQで2016年1月28日～同年2月18日に出題された「バイバイマンを数えよう」という問題とその解法に関する記事です。

バイバイマンを数えよう【解説1】一般解法編

◆バイバイマンの数え方

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日目から順に出力するだけなら、配列を使わず省メモリで書いても良いですね。

【解説2】