[paiza×Qiita記事投稿キャンペーン] Rubyでmod7占いを解いてみた

この記事は paiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」 キャンペーンへの参加記事です。

今回キャンペーンの候補問題の中から、ランクSの「mod7占い」を解いてみました。

解いたソースコードの全体像は以下にあります。

問題分

問題文の詳細ははPaizaの記事の方を読んでいただくとして、要点は

• 最初にカード数が与えられ、その後カードの数だけ入力が与えられる
• すべて異なるカードがn枚与えられる (nは3以上)
• 与えられたカードから同時に3枚選び、3枚のカードの和が7の倍数になる組み合わせ数を出力する

の3点です。

では実際に作成していきましょう。

実装

実装は大きく分けて以下のように分割できます。

• 入力を受け取る
• 組み合わせ数を計算し出力する

入力を受け取る

まずは入力を受け取りましょう。

card_num = gets.chomp.to_i
mod7_result = {}
7.times {|i| mod7_result[i.to_s] = 0}

card_num.times { mod7_result[(gets.chomp.to_i % 7).to_s] += 1 }

1行目はカードの取得として、2~3行目で変数mod7_resultというハッシュを定義しています。
これは与えられた数の剰余の出現回数をカウントするためのものです。
今回はすべて異なる数という前提が今回は存在するため、重複を考える必要がなく、mod7の値のみの情報で完結することができます。

入力例を実際に入れてみるとmod7_resultの中身は以下のようになります。

入力

10
1
2
3
4
5
6
7
8
9
10

mod7_result

{"0"=>1, "1"=>2, "2"=>2, "3"=>2, "4"=>1, "5"=>1, "6"=>1}

組み合わせを計算する

それでは組み合わせを計算します。
mod7の値は0~6の値の範囲であるため、mod7の値を3足して生成される7の倍数は0も含めて0,7,14となります。
また、3枚のカードの組み合わせを今回以下のように分割します。

• mod7した値がすべて異なる値である
• mod7した値の同じ組が一つ存在する
• mod7した値が3枚すべて同じである

それぞれの場合についてみていきましょう。

全て異なる場合

3つのmod7された値が異なりかつ、7の倍数になるのは以下の組み合わせです。(左から小さい値)

[0,1,6]
[0,2,5]
[0,3,4]
[1,2,4]
[3,5,6]

この場合は純粋な掛け算で良いのでそれぞれの出現回数の積を計算します。

sum = 0
[[0,1,6],[0,2,5], [0,3,4] ,[1,2,4],[3,5,6]].each do |a,b,c|
  sum += mod7_result[a.to_s] * mod7_result[b.to_s] * mod7_result[c.to_s]
end

mod7した値の同じ組が一つ存在する場合

2枚が同じmod7の値かつ、1枚は違うmod7の値かつ相和が7の倍数になるのはmod7が以下のような組み合わせです。

[1,1,5]
[2,2,3]
[3,3,1]
[4,4,6]
[5,5,4]
[6,6,2]

今回は重複が1回出現するので組み合わせ数は同じ組が存在する方の出現回数をa、しない方の出現回数をbとしたとき、以下のようになります。

\frac{a * (a-1) }{2} * b

これをコードに落とし込むと以下のようになります。

[[1,5], [2,3], [3,1], [4,6], [5,4], [6,2]].each do |a,b|
  sum += (mod7_result[a.to_s] * (mod7_result[a.to_s]-1)/2) * mod7_result[b.to_s]
end

全て同じmod7の値になる場合

全てmod7で同じ値になるのは、mod7=0、つまりすべて7で割り切れる値の時のみです。
重複が2回存在する組み合わせなので、mod7が0になる数の出現回数をaとして、組み合わせ数は以下のような式になります。

\frac{a * (a-1) * (a-2)}{6}

これをコードに落とし込むと以下のようになります。

sum += mod7_result['0']*(mod7_result['0']-1)*(mod7_result['0']-2)/6

最後にここまで足してきた組み合わせ数を格納した変数sumをpやputsなどの関数を使って出力することでこの問題は完了となります。

解いてみた感想

入力された値をmod7に落とし込むことと、組み合わせを分解することに気が付けばあとはスッと解くことができました。きちんと計測はしてないですが、20分くらいで提出したかと思います。
自分はPaizaの会員でSランクも取得していたりするのですが、通常のpaizaの問題はクローズドなので、こうしてQiitaの記事を書いたりGitHubにコードを上げたりというのは不思議な体験に感じました。

今回問題なくテストケース自体は突破しましたが、もっと良い方法などがあればコメントいただけると幸いです。